本题要求给定二叉树的4种遍历。\n\n函数接口定义:\nvoid inordertraversal( bintree bt );\nvoid preordertraversal( bintree bt );
时间: 2023-05-02 14:04:33 浏览: 53
本题要求给定二叉树的4种遍历。
void inordertraversal( bintree bt ); // 中序遍历
void preordertraversal( bintree bt ); // 前序遍历
void postordertraversal( bintree bt ); // 后序遍历
void levelordertraversal( bintree bt ); // 层序遍历
相关问题
本题要求按照先序遍历的顺序输出给定二叉树的叶结点。\n\n函数接口定义:\nvoid preorderprintleaves( bintree bt );\n其中bintree结构定义如下:\n\ntypedef
题目要求按照先序遍历的顺序输出给定二叉树的叶结点。
函数接口定义:
void preorderprintleaves( bintree bt );
其中,bintree结构体定义如下:
typedef struct TreeNode *bintree;
struct TreeNode {
int data;
bintree left;
bintree right;
};
解释说明:
题目要求按照先序遍历的顺序输出给定二叉树的叶结点。先序遍历是指先遍历根节点,再遍历左子树,最后遍历右子树。对于每个遍历到的结点,判断它是否为叶结点,若是,则输出它的值。具体实现可以采用递归的方式进行,详细过程如下:
1. 判断当前结点是否为空,如果是,则直接返回;
2. 判断当前结点的左右子树是否为空,如果都为空,则说明当前结点为叶结点,输出它的值;
3. 如果当前结点的左子树不为空,则递归遍历左子树;
4. 如果当前结点的右子树不为空,则递归遍历右子树。
这样,就可以按照先序遍历的顺序输出给定二叉树的叶结点。
void LevelorderTraversal ( BinTree BT ) /* 输出二叉树层序遍历序列 */
这是一个输出二叉树层序遍历序列的函数,具体实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
int Data;
BinTree Left;
BinTree Right;
};
typedef struct {
Position Data[MAXSIZE];
int front, rear;
} Queue;
Queue* CreateQueue() {
Queue* Q = (Queue*)malloc(sizeof(Queue));
Q->front = Q->rear = 0;
return Q;
}
int IsEmpty(Queue* Q) {
return Q->front == Q->rear;
}
void Enqueue(Queue* Q, Position X) {
if ((Q->rear + 1) % MAXSIZE == Q->front) {
printf("队列已满\n");
return;
}
Q->Data[Q->rear++] = X;
}
Position Dequeue(Queue* Q) {
if (IsEmpty(Q)) {
printf("队列已空\n");
return NULL;
}
Position X = Q->Data[Q->front++];
return X;
}
void LevelorderTraversal(BinTree BT) {
if (!BT) return;
Queue* Q = CreateQueue();
Enqueue(Q, BT);
while (!IsEmpty(Q)) {
Position T = Dequeue(Q);
printf("%d ", T->Data);
if (T->Left) Enqueue(Q, T->Left);
if (T->Right) Enqueue(Q, T->Right);
}
}
```
该函数先创建一个队列,将根节点入队。之后进入循环,每次出队一个节点,并输出其值。如果该节点有左子树,则将其左子树入队;如果该节点有右子树,则将其右子树入队。循环继续,直到队列为空,即所有节点都已经访问过。