编写非递归遍历算法,C语言实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树 1输出二叉树的后序遍历的结点序列 2输出二叉树的叶子结点 3统计二叉树的结点个数 4求二叉树的深度 5输出二叉树指定结点的路径
时间: 2023-06-20 19:09:03 浏览: 104
以下是非递归遍历算法的C语言实现,包括先序遍历、中序遍历和后序遍历:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结点
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 定义栈结构体
typedef struct Stack {
int top;
int size;
TreeNode** data;
} Stack;
// 初始化栈
Stack* initStack(int size) {
Stack* s = (Stack*)malloc(sizeof(Stack));
s->top = -1;
s->size = size;
s->data = (TreeNode**)malloc(sizeof(TreeNode*) * size);
return s;
}
// 判断栈是否为空
int isEmpty(Stack* s) {
return s->top == -1;
}
// 入栈
void push(Stack* s, TreeNode* t) {
if (s->top == s->size - 1) return;
s->data[++(s->top)] = t;
}
// 出栈
TreeNode* pop(Stack* s) {
if (isEmpty(s)) return NULL;
return s->data[(s->top)--];
}
// 非递归先序遍历
void preOrder(TreeNode* root) {
if (!root) return;
Stack* s = initStack(100);
push(s, root);
while (!isEmpty(s)) {
TreeNode* t = pop(s);
printf("%d ", t->val);
if (t->right) push(s, t->right);
if (t->left) push(s, t->left);
}
}
// 非递归中序遍历
void inOrder(TreeNode* root) {
if (!root) return;
Stack* s = initStack(100);
TreeNode* t = root;
while (!isEmpty(s) || t) {
if (t) {
push(s, t);
t = t->left;
} else {
t = pop(s);
printf("%d ", t->val);
t = t->right;
}
}
}
// 非递归后序遍历
void postOrder(TreeNode* root) {
if (!root) return;
Stack* s1 = initStack(100);
Stack* s2 = initStack(100);
push(s1, root);
while (!isEmpty(s1)) {
TreeNode* t = pop(s1);
push(s2, t);
if (t->left) push(s1, t->left);
if (t->right) push(s1, t->right);
}
while (!isEmpty(s2)) {
TreeNode* t = pop(s2);
printf("%d ", t->val);
}
}
```
接下来是创建二叉树、输出叶子结点、统计结点个数、求深度和输出指定结点路径等功能的实现:
```c
// 根据先序遍历序列和中序遍历序列创建二叉树
TreeNode* buildTree(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[preStart];
int i;
for (i = inStart; i <= inEnd; i++) {
if (inorder[i] == root->val) break;
}
int leftLen = i - inStart;
root->left = buildTree(preorder, preStart + 1, preStart + leftLen, inorder, inStart, i - 1);
root->right = buildTree(preorder, preStart + leftLen + 1, preEnd, inorder, i + 1, inEnd);
return root;
}
// 输出二叉树的叶子结点
void printLeaves(TreeNode* root) {
if (!root) return;
if (!root->left && !root->right) printf("%d ", root->val);
printLeaves(root->left);
printLeaves(root->right);
}
// 统计二叉树的结点个数
int countNodes(TreeNode* root) {
if (!root) return 0;
return 1 + countNodes(root->left) + countNodes(root->right);
}
// 求二叉树的深度
int maxDepth(TreeNode* root) {
if (!root) return 0;
int leftDepth = maxDepth(root->left);
int rightDepth = maxDepth(root->right);
return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
// 输出二叉树指定结点的路径
int findPath(TreeNode* root, int val, int* path, int index) {
if (!root) return 0;
path[index++] = root->val;
if (root->val == val) return 1;
if (findPath(root->left, val, path, index) || findPath(root->right, val, path, index)) {
return 1;
}
return 0;
}
```
以上就是给定先序遍历序列和中序遍历序列创建二叉树,并实现一些二叉树操作的C语言代码。