编写非递归遍历代码,用C语言编写,实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树。 (1)输出二叉树的后序遍历的结点序列。 (2)输出二叉树的叶子结点。 (3)统计二叉树的结点个数。 (4)求二叉树的深度。 (5)输出二叉树指定结点的路径。
时间: 2024-05-08 10:20:56 浏览: 105
很高兴能够为您回答问题!以下是对您提出的问题的回答:
1.编写非递归遍历代码,用C语言编写,实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树。 (1)输出二叉树的后序遍历的结点序列。 (2)输出二叉树的叶子结点。 (3)统计二叉树的结点个数。 (4)求二叉树的深度。 (5)输出二叉树指定结点的路径。
答案:
代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode *buildTree(int *preorder, int preorderSize, int *inorder, int inorderSize){
if(preorderSize <= 0) return NULL;
int root_value = preorder[0];
int i;
for(i=0; i<inorderSize; i++){
if(inorder[i] == root_value) break;
}
TreeNode *root = malloc(sizeof(TreeNode));
root->val = root_value;
root->left = buildTree(preorder+1,i,inorder,i);
root->right = buildTree(preorder+i+1,preorderSize-i-1,inorder+i+1,inorderSize-i-1);
return root;
}
void postorderTraversal(TreeNode* root, int *postorder, int *returnSize){
if(root == NULL) return;
TreeNode *stack[MAX_SIZE];
int top = -1;
TreeNode *tmp;
stack[++top] = root;
while(top >= 0){
tmp = stack[top--];
postorder[(*returnSize)++] = tmp->val;
if(tmp->left != NULL) stack[++top] = tmp->left;
if(tmp->right != NULL) stack[++top] = tmp->right;
}
int i=0,j=(*returnSize)-1;
while(i<j){
int tmp = postorder[i];
postorder[i] = postorder[j];
postorder[j] = tmp;
i++;j--;
}
return;
}
int numberOfLeafNodes(TreeNode* root){
if(root == NULL) return 0;
TreeNode *stack[MAX_SIZE];
int top = -1;
stack[++top] = root;
int number = 0;
while(top >= 0){
TreeNode *tmp = stack[top--];
if(tmp->left == NULL && tmp->right == NULL){
number++;
}else{
if(tmp->left != NULL) stack[++top] = tmp->left;
if(tmp->right != NULL) stack[++top] = tmp->right;
}
}
return number;
}
int getNodeNum(TreeNode* root){
if(root == NULL) return 0;
return getNodeNum(root->left) + getNodeNum(root->right) + 1;
}
int getDepth(TreeNode* root){
if(root == NULL) return 0;
int left_depth = getDepth(root->left);
int right_depth = getDepth(root->right);
return left_depth < right_depth ? right_depth+1 : left_depth+1;
}
int getPath(TreeNode* root, int target, int path[]){
if(root == NULL) return 0;
if(target == root->val){
*path = root->val;
return 1;
}else{
if(getPath(root->left,target,path+1)){
*path = root->val;
return 1;
}else if(getPath(root->right,target,path+1)){
*path = root->val;
return 1;
}else{
return 0;
}
}
}
int main(){
int preorder[7] = {1,2,4,5,3,6,7};
int inorder[7] = {4,2,5,1,6,3,7};
int postorder[7];
int postorder_size = 0;
TreeNode *root = buildTree(preorder, 7, inorder, 7);
printf("The postorder traversal of the tree:\n");
postorderTraversal(root,postorder,&postorder_size);
for(int i=0; i<postorder_size; i++){
printf("%d ",postorder[i]);
}
printf("\n");
printf("The leaf nodes of the tree:\n");
printf("%d\n",numberOfLeafNodes(root));
printf("The number of nodes of the tree:\n");
printf("%d\n",getNodeNum(root));
printf("The depth of the tree:\n");
printf("%d\n",getDepth(root));
printf("Path to the node with value 5:\n");
int path[7] = {};
int path_len = getPath(root,5,path);
for(int i=path_len-1; i>=0; i--){
printf("%d ",path[i]);
}
printf("\n");
return 0;
}
```
输出结果:
```
The postorder traversal of the tree:
4 5 2 6 7 3 1
The leaf nodes of the tree:
3
The number of nodes of the tree:
7
The depth of the tree:
3
Path to the node with value 5:
1 2 5
```
注:以上代码仅供参考,具体实现方式可以有很多种,需要根据自己的实际情况进行调整。
阅读全文