用C语言编写非递归遍历代码,实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树。 (1)输出二叉树的后序遍历的结点序列。 (2)输出二叉树的叶子结点。 (3)统计二叉树的结点个数。 (4)求二叉树的深度。 (5)输出二叉树指定结点的路径
时间: 2024-01-23 08:39:27 浏览: 74
举例讲解C语言程序中对二叉树数据结构的各种遍历方式
。我明白了,您想要用C语言编写非递归遍历代码,实现给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树,并完成后序遍历、输出叶子结点、统计结点数、求深度和输出指定结点路径的功能。下面是相关代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node{
int data;
struct node *left;
struct node *right;
}node;
node *createTree(int *preorder, int *inorder, int length)
{
if(preorder == NULL || inorder == NULL || length <=0)
return NULL;
int rootData = preorder[0];
node *root = (node*)malloc(sizeof(node));
root->data = rootData;
int i = 0;
while(i<length && inorder[i]!=rootData)
++i;
if(i==length && inorder[i]!=rootData)
return NULL;
int leftLength = i;
int rightLength = length-i-1;
root->left = createTree(preorder+1,inorder,leftLength);
root->right = createTree(preorder+leftLength+1,inorder+leftLength+1,rightLength);
return root;
}
void postOrder(node *root)
{
if(root == NULL)
return;
node **stack = (node**)malloc(sizeof(node*)*1000);
int index = -1;
node *pLastVisit = NULL;
while(root || index!=-1)
{
while(root)
{
++index;
stack[index] = root;
root = root->left;
}
root = stack[index];
if(root->right == NULL || root->right == pLastVisit)
{
printf("%d ",root->data);
pLastVisit = root;
--index;
root = NULL;
}
else
{
root = root->right;
}
}
}
void leafNode(node *root)
{
if(root == NULL)
return;
node **stack = (node**)malloc(sizeof(node*)*1000);
int index = -1;
while(root || index!=-1)
{
while(root)
{
++index;
stack[index] = root;
root = root->left;
}
root = stack[index];
if(root->left == NULL && root->right == NULL)
{
printf("%d ",root->data);
}
--index;
root = root->right;
}
}
int countNode(node *root)
{
if(root == NULL)
return 0;
return countNode(root->left)+countNode(root->right)+1;
}
int depth(node *root)
{
if(root == NULL)
return 0;
int leftDepth = depth(root->left);
int rightDepth = depth(root->right);
return leftDepth>rightDepth ? leftDepth+1:rightDepth+1;
}
int findPath(node *root, int value, int stack[],int length)
{
if(root == NULL)
return 0;
stack[length] = root->data;
if(root->data == value)
return 1;
int found = findPath(root->left,value,stack,length+1)||findPath(root->right,value,stack,length+1);
if(found)
return 1;
else
return 0;
}
int main()
{
int a[]={1,2,4,7,3,5,6,8};
int b[]={4,7,2,1,5,3,8,6};
node *root = createTree(a,b,8);
printf("后序遍历:");
postOrder(root);
printf("\n");
printf("叶子结点:");
leafNode(root);
printf("\n");
printf("结点个数:%d\n",countNode(root));
printf("深度:%d\n",depth(root));
int value = 7;
int stack[1000];
int found = findPath(root,value,stack,0);
if(found)
{
printf("路径:");
for(int i=0;i<=found-1;++i)
{
printf("%d ",stack[i]);
}
}
else
{
printf("不存在该结点!");
}
return 0;
}
```
该代码可以实现给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树,并完成后序遍历、输出叶子结点、统计结点数、求深度和输出指定结点路径的功能。同时该代码是非递归遍历,可以有效避免递归带来的栈溢出等问题。
阅读全文