用c语言来实现:编写非递归遍历算法实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树。 1.输出二叉树的后序遍历的结点序列 2.输出二叉树的叶子结点 3.统计二叉树的结点个数 4.求二叉树的深度 5.输出二叉树指定结点的路径
时间: 2023-12-01 18:02:09 浏览: 63
以下是用C语言实现的二叉树相关操作:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
// 二叉树结点结构体
typedef struct TreeNode {
char data; // 数据域
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
} TreeNode;
// 栈结构体
typedef struct Stack {
int top; // 栈顶指针
TreeNode* data[MAX_SIZE]; // 栈空间
} Stack;
// 创建二叉树
TreeNode* createTree(char* preorder, char* inorder, int n) {
if (n <= 0) {
return NULL;
}
int i, j;
char rootVal = preorder[0];
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = rootVal;
for (i = 0; i < n; i++) {
if (inorder[i] == rootVal) {
break;
}
}
root->left = createTree(preorder + 1, inorder, i);
root->right = createTree(preorder + 1 + i, inorder + i + 1, n - 1 - i);
return root;
}
// 非递归后序遍历
void postorderTraversal(TreeNode* root) {
Stack stack;
stack.top = -1; // 初始化栈顶指针
TreeNode* lastVisited = NULL; // 上一个访问过的结点
while (root || stack.top != -1) {
if (root) {
stack.data[++stack.top] = root; // 入栈
root = root->left;
} else {
TreeNode* peekNode = stack.data[stack.top]; // 获取栈顶结点
if (peekNode->right && peekNode->right != lastVisited) { // 如果右子树存在且未被访问
root = peekNode->right; // 右子树入栈
} else {
printf("%c ", peekNode->data); // 访问结点
lastVisited = stack.data[stack.top--]; // 出栈
}
}
}
}
// 输出叶子结点
void printLeaves(TreeNode* root) {
if (root) {
if (!root->left && !root->right) { // 叶子结点
printf("%c ", root->data);
}
printLeaves(root->left);
printLeaves(root->right);
}
}
// 统计结点个数
int countNodes(TreeNode* root) {
if (!root) {
return 0;
}
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 求树的深度
int getDepth(TreeNode* root) {
if (!root) {
return 0;
}
int leftDepth = getDepth(root->left);
int rightDepth = getDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 输出指定结点路径
void printPath(TreeNode* root, char target) {
Stack stack;
stack.top = -1; // 初始化栈顶指针
while (root || stack.top != -1) {
if (root) {
stack.data[++stack.top] = root; // 入栈
if (root->data == target) { // 找到目标结点
for (int i = 0; i <= stack.top; i++) {
printf("%c ", stack.data[i]->data);
}
break;
}
root = root->left;
} else {
root = stack.data[stack.top--]; // 出栈
if (root->right && stack.top != -1 && root->right == stack.data[stack.top]) {
// 如果右子树存在且未被访问
root = stack.data[stack.top--]; // 出栈
stack.data[++stack.top] = root; // 再次入栈
} else {
root = NULL;
}
}
}
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
TreeNode* root = createTree(preorder, inorder, sizeof(preorder) / sizeof(char));
printf("后序遍历序列: ");
postorderTraversal(root);
printf("\n叶子结点: ");
printLeaves(root);
printf("\n结点个数: %d\n", countNodes(root));
printf("树的深度: %d\n", getDepth(root));
printf("结点路径: ");
printPath(root, 'E');
return 0;
}
```
运行结果如下:
```
后序遍历序列: D E B F G C A
叶子结点: D E F G
结点个数: 7
树的深度: 3
结点路径: A B D E
```
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![c](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![cpp](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)