先序和中序能建立二叉树吗
时间: 2024-04-05 11:34:19 浏览: 25
是的,先序遍历序列和中序遍历序列可以唯一地确定一棵二叉树。具体构建方法如下:
1. 先序遍历序列的第一个结点为根节点;
2. 在中序遍历序列中找到根节点,可以将中序遍历序列分为左子树和右子树两个部分;
3. 根据左子树和右子树的长度,可以将先序遍历序列分为左子树和右子树两个部分;
4. 递归处理左子树和右子树,即可构建整棵二叉树。
需要注意的是,如果先序遍历序列和中序遍历序列不合法,即无法构建成二叉树,那么上述方法也无法构建正确的二叉树。此外,如果一棵二叉树中存在相同的结点值,那么就无法唯一地确定这棵二叉树。
相关问题
c++代码实现:通过先序和中序遍历建立二叉树
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
char val;
struct TreeNode *left;
struct TreeNode *right;
}TreeNode;
TreeNode* buildTree(char* preorder, int prestart, int preend, char* inorder, int instart, int inend){
if(prestart > preend || instart > inend) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[prestart];
int index = instart;
while(index <= inend && inorder[index] != preorder[prestart]){
index++;
}
root->left = buildTree(preorder, prestart+1, prestart+index-instart, inorder, instart, index-1);
root->right = buildTree(preorder, prestart+index-instart+1, preend, inorder, index+1, inend);
return root;
}
void inorderTraversal(TreeNode* root){
if(root == NULL) return;
inorderTraversal(root->left);
printf("%c ", root->val);
inorderTraversal(root->right);
}
int main(){
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F', 'G'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C', 'G'};
TreeNode* root = buildTree(preorder, 0, 6, inorder, 0, 6);
inorderTraversal(root);
return 0;
}
先序后序中序建立二叉树
二叉树是一种非常重要的数据结构,它在计算机科学中有着广泛的应用。建立二叉树的过程可以通过先序、中序或后序遍历序列来实现。下面是先序、中序和后序建立二叉树的方法:
1. 先序建立二叉树
先序建立二叉树的过程是:先读入根节点,然后递归读入左子树和右子树。具体步骤如下:
1)读入根节点;
2)如果当前节点的值不为空,则递归读入左子树;
3)如果当前节点的值不为空,则递归读入右子树。
2. 中序建立二叉树
中序建立二叉树的过程是:先递归读入左子树,然后读入根节点,最后递归读入右子树。具体步骤如下:
1)如果当前节点的值不为空,则递归读入左子树;
2)读入根节点;
3)如果当前节点的值不为空,则递归读入右子树。
3. 后序建立二叉树
后序建立二叉树的过程是:先递归读入左子树,然后递归读入右子树,最后读入根节点。具体步骤如下:
1)如果当前节点的值不为空,则递归读入左子树;
2)如果当前节点的值不为空,则递归读入右子树;
3)读入根节点。
以上是三种建立二叉树的方法,根据不同的遍历序列可以选择不同的方法。在建立二叉树后,可以通过先序、中序和后序遍历来输出二叉树的遍历序列。此外,可以通过遍历二叉树来计算二叉树的叶子数。
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)