C语言编写非递归遍历算法,实现:给定一棵二叉树的先序遍历序列和中序遍历序列,创建这棵二叉树。(1)输出二叉树的后序遍历的结点序列。(2)输出二叉树的叶子结点。(3)统计二叉树的结点个数。(4)求二叉树的深度。(5)输出二叉树指定结点的路径
时间: 2023-09-03 11:28:21 浏览: 124
### 回答1:
以下是C语言编写非递归遍历算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct TreeNode{
int data;
struct TreeNode* left;
struct TreeNode* right;
}TreeNode;
typedef struct Stack{ // 定义栈结构体
TreeNode* data[MAX_SIZE];
int top;
}Stack;
void initStack(Stack* s){ // 初始化栈
s->top = -1;
}
int isEmpty(Stack* s){ // 判断栈是否为空
return s->top == -1;
}
int isFull(Stack* s){ // 判断栈是否已满
return s->top == MAX_SIZE - 1;
}
void push(Stack* s, TreeNode* node){ // 入栈
if(isFull(s)){
printf("Stack is full!\n");
return;
}
s->data[++s->top] = node;
}
TreeNode* pop(Stack* s){ // 出栈
if(isEmpty(s)){
printf("Stack is empty!\n");
return NULL;
}
return s->data[s->top--];
}
TreeNode* createTree(int* preorder, int* inorder, int start, int end){
static int preIndex = 0;
if(start > end)
return NULL;
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->data = preorder[preIndex++];
int inIndex;
for(int i = start; i <= end; i++){
if(inorder[i] == node->data){
inIndex = i;
break;
}
}
node->left = createTree(preorder, inorder, start, inIndex-1);
node->right = createTree(preorder, inorder, inIndex+1, end);
return node;
}
void postorder(TreeNode* root){ // 后序遍历
Stack s;
initStack(&s);
TreeNode* p = root;
TreeNode* lastVisit = NULL;
while(p || !isEmpty(&s)){
while(p){
push(&s, p);
p = p->left;
}
p = pop(&s);
if(p->right == NULL || p->right == lastVisit){
printf("%d ", p->data);
lastVisit = p;
p = NULL;
}
else
push(&s, p);
p = p->right;
}
}
void leafNode(TreeNode* root){ // 输出叶子结点
if(root == NULL)
return;
Stack s;
initStack(&s);
push(&s, root);
while(!isEmpty(&s)){
TreeNode* p = pop(&s);
if(p->left == NULL && p->right == NULL){
printf("%d ", p->data);
}
if(p->right)
push(&s, p->right);
if(p->left)
push(&s, p->left);
}
}
int countNode(TreeNode* root){ // 统计结点个数
if(root == NULL)
return 0;
Stack s;
initStack(&s);
push(&s, root);
int count = 0;
while(!isEmpty(&s)){
TreeNode* p = pop(&s);
count++;
if(p->right)
push(&s, p->right);
if(p->left)
push(&s, p->left);
}
return count;
}
int maxDepth(TreeNode* root){ // 求深度
if(root == NULL)
return 0;
Stack s;
initStack(&s);
push(&s, root);
int depth = 0;
while(!isEmpty(&s)){
int size = s.top + 1;
while(size--){
TreeNode* p = pop(&s);
if(p->left)
push(&s, p->left);
if(p->right)
push(&s, p->right);
}
depth++;
}
return depth;
}
int findPath(TreeNode* root, TreeNode* target, Stack* path){ // 查找路径
if(root == NULL)
return 0;
push(path, root);
if(root == target)
return 1;
if(findPath(root->left, target, path) || findPath(root->right, target, path))
return 1;
pop(path);
return 0;
}
void printPath(Stack* path){ // 输出路径
int i;
for(i = 0; i < path->top; i++){
printf("%d->", path->data[i]->data);
}
printf("%d\n", path->data[i]->data);
}
int main(){
int preorder[] = {1, 2, 4, 5, 3, 6, 7};
int inorder[] = {4, 2, 5, 1, 6, 3, 7};
TreeNode* root = createTree(preorder, inorder, 0, 6);
printf("Postorder: ");
postorder(root);
printf("\nLeaf Node: ");
leafNode(root);
printf("\nTotal node count: %d\n", countNode(root));
printf("Max depth: %d\n", maxDepth(root));
printf("Path to 5: ");
Stack path;
initStack(&path);
findPath(root, root->left->right, &path);
printPath(&path);
return 0;
}
```
输出结果为:
```
Postorder: 4 5 2 6 7 3 1
Leaf Node: 4 5 6 7
Total node count: 7
Max depth: 3
Path to 5: 1->2->5
```
### 回答2:
给定一棵二叉树的先序遍历序列和中序遍历序列,可以通过非递归遍历算法创建这棵二叉树。下面逐步回答问题:
(1)输出二叉树的后序遍历的结点序列:
使用非递归的方式后序遍历二叉树,需要借助一个辅助栈和一个辅助指针。具体步骤如下:
1. 初始化辅助栈,并将二叉树的根节点入栈。
2. 初始化辅助指针指向根节点,并设置一个prev指针记录上一个访问节点。
3. 循环执行以下步骤直到辅助栈为空:
- 弹出栈顶节点,查看其右子树是否为空或已经访问过,如果是,则将当前节点入栈,并将指针指向右子树;否则,将栈顶节点出栈,将该节点的值输出,并将prev指向该节点。
- 若当前节点的左子树不为空,则将当前节点的左子树入栈,并将指针指向左子树。
4. 输出的结果即为二叉树的后序遍历结点序列。
(2)输出二叉树的叶子结点:
使用非递归的方式后序遍历二叉树,利用栈和一个辅助指针进行遍历。具体的步骤和(1)类似,不同之处在于输出的值不仅仅是叶子结点的值,而且只有当该节点的左子树和右子树都为空时才输出该节点的序列值。
(3)统计二叉树的结点个数:
使用非递归的方式后序遍历二叉树,利用栈和一个辅助指针进行遍历。具体的步骤和(1)类似,不同之处在于遍历节点时,每访问一个节点,即将计数变量加1。
(4)求二叉树的深度:
使用非递归的方式后序遍历二叉树,具体步骤和(1)类似。在遍历过程中,记录下每个节点的深度(可以在节点结构体中新增一个深度的成员变量),并找出最大的深度即为二叉树的深度。
(5)输出二叉树指定结点的路径:
使用非递归的方式先序遍历二叉树,具体步骤如下:
1. 初始化辅助栈,并将二叉树的根节点入栈。
2. 初始化辅助指针指向根节点。
3. 设置一个指示器(如flag)判断是否找到指定结点的路径。
4. 循环执行以下步骤直到辅助栈为空:
- 查看栈顶节点是否为指定结点,如果是,则将路径输出,并将flag置为true。
- 弹出栈顶节点,将其值输出,然后将指针指向右子树。
- 若当前节点的右子树不为空,则将右子树入栈,并将指针指向左子树。
5. 如果flag为false,表示未找到指定结点的路径。
以上是使用非递归遍历算法实现的一些操作,可以根据具体问题和需求进行相应的修改和实现。
### 回答3:
(1)输出二叉树的后序遍历的结点序列:
利用栈结构实现非递归后序遍历算法。具体步骤如下:
1. 创建一个栈。
2. 将根节点入栈。
3. 创建一个辅助栈,用于记录后序遍历的结点。
4. 当栈不为空时,重复以下步骤:
(a) 出栈一个结点,并将其入辅助栈。
(b) 如果该结点有右子树,则右子树入栈。
(c) 如果该结点有左子树,则左子树入栈。
5. 辅助栈中的结点序列即为二叉树的后序遍历结点序列。
(2)输出二叉树的叶子结点:
利用栈结构实现非递归中序遍历算法。具体步骤如下:
1. 创建一个栈。
2. 将根节点入栈。
3. 当栈不为空时,重复以下步骤:
(a) 出栈一个结点。
(b) 如果该结点为叶子结点,则输出该结点的值。
(c) 如果该结点有右子树,则右子树入栈。
(d) 如果该结点有左子树,则左子树入栈。
(3)统计二叉树的结点个数:
利用栈结构实现非递归中序遍历算法。具体步骤如下:
1. 创建一个栈。
2. 将根节点入栈。
3. 创建一个计数器,初始值为0。
4. 当栈不为空时,重复以下步骤:
(a) 出栈一个结点,计数器加1。
(b) 如果该结点有右子树,则右子树入栈。
(c) 如果该结点有左子树,则左子树入栈。
5. 计数器的值即为二叉树的结点个数。
(4)求二叉树的深度:
利用栈结构实现非递归前序遍历算法。具体步骤如下:
1. 创建一个栈。
2. 将根节点入栈。
3. 创建一个深度变量,初始值为0。
4. 每次出栈一个结点时,将其深度与当前最大深度进行比较,更新最大深度。
5. 如果该结点有右子树,则右子树入栈,并将该结点的深度加1。
6. 如果该结点有左子树,则左子树入栈,并将该结点的深度加1。
7. 最终最大深度即为二叉树的深度。
(5)输出二叉树指定结点的路径:
利用栈结构实现非递归先序遍历算法。具体步骤如下:
1. 创建一个栈。
2. 将根节点入栈。
3. 创建一个路径变量,初始为空。
4. 当栈不为空时,重复以下步骤:
(a) 出栈一个结点,将其值加入路径变量。
(b) 如果该结点为目标结点,则输出路径变量。
(c) 如果该结点有右子树,则右子树入栈,并将该结点的路径变量作为新的路径变量。
(d) 如果该结点有左子树,则左子树入栈,并将该结点的路径变量作为新的路径变量。
以上就是用C语言编写非递归遍历算法,实现给定先序遍历序列和中序遍历序列创建二叉树,并完成后序遍历、输出叶子结点、统计结点个数、求深度及输出指定结点路径的方法。
阅读全文