输入二叉树的按层次遍历的结点序列创建二叉树
时间: 2024-05-10 10:13:13 浏览: 15
按层次遍历的结点序列创建二叉树可以采用队列来实现,具体步骤如下:
1. 将根节点入队。
2. 取出队首元素作为当前节点。
3. 读取下一个输入元素,若该元素不为空,则创建一个节点,将该节点作为当前节点的左儿子,并将该节点入队。
4. 读取下一个输入元素,若该元素不为空,则创建一个节点,将该节点作为当前节点的右儿子,并将该节点入队。
5. 将队首元素出队,重复2~4步,直到队列为空。
以下是按层次遍历序列{1,2,3,4,5,6,7}创建的二叉树示意图:
```
1
/ \
2 3
/ \ / \
4 5 6 7
```
相关问题
画出和下列已知结点序列对应的二叉树 (1)该二叉树的中序遍历结点序列为DCBGEAHFIJK (2)该二叉树的后序遍历结点序列为DCEGBFHKJIA
根据中序遍历和后序遍历的特点,可以确定该二叉树的根节点为J,然后根据根节点在中序遍历中的位置,将中序遍历序列划分为左右子树的中序遍历序列DCBGEA和HFIK。同样地,根据后序遍历中根节点的位置,将后序遍历序列划分为左右子树的后序遍历序列DCEGBFHK和IA。接下来,递归处理左右子树即可得到完整的二叉树。
```
J
/ \
/ \
G I
/ \ / \
B E F K
/ / \
D C H
```
注:该二叉树不唯一,可能存在其他形态。
C语言实现编写二叉树的递归遍历算法,实现:给定一棵二叉树的扩展先序遍历序列,创建这棵二叉树 1输出二叉树的先序遍历的结点序列 2输出二叉树的先序遍历的结点序列 3输出二叉树的先序遍历的结点序列 4输出二叉树的叶子结点 5统计二叉树的结点个数
下面是C语言实现二叉树的递归遍历算法的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
//创建二叉树
TreeNode *createTree(char *str, int *index) {
if (str[*index] == '#' || str[*index] == '\0') {
return NULL;
}
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = str[*index];
(*index)++;
root->left = createTree(str, index);
(*index)++;
root->right = createTree(str, index);
return root;
}
//先序遍历
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->data);
preOrder(root->left);
preOrder(root->right);
}
//中序遍历
void inOrder(TreeNode *root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%c ", root->data);
inOrder(root->right);
}
//后序遍历
void postOrder(TreeNode *root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c ", root->data);
}
//输出叶子结点
void printLeaves(TreeNode *root) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c ", root->data);
}
printLeaves(root->left);
printLeaves(root->right);
}
//统计结点个数
int countNodes(TreeNode *root) {
if (root == NULL) {
return 0;
}
return countNodes(root->left) + countNodes(root->right) + 1;
}
int main() {
char str[] = "ABD##E##CF#H##G##";
int index = 0;
TreeNode *root = createTree(str, &index);
printf("先序遍历:");
preOrder(root);
printf("\n");
printf("中序遍历:");
inOrder(root);
printf("\n");
printf("后序遍历:");
postOrder(root);
printf("\n");
printf("叶子结点:");
printLeaves(root);
printf("\n");
printf("结点个数:%d\n", countNodes(root));
return 0;
}
```
程序的输出结果如下:
```
先序遍历:A B D E C F H G
中序遍历:D B E A F C H G
后序遍历:D E B H G F C A
叶子结点:D E H G
结点个数:7
```
其中,二叉树的扩展先序遍历序列为"ABD##E##CF#H##G##",其中"#"表示空结点。在程序中,我们首先根据扩展先序遍历序列创建了二叉树,然后分别进行了先序、中序、后序遍历,并输出了叶子结点和结点个数。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)