根据先序和中序遍历建立二叉树

云计算 waitig 413℃ 百度已收录 0评论

#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<cstdlib>  
#include<stack>  
#include<queue>  
using namespace std;
typedef int ElemType;
typedef struct BinaryTreeNode
{
ElemType data;
BinaryTreeNode *left, *right;

}BinaryTreeNode;
//二叉树的建立3 根据先序序列和中序序列建立一个二叉树     先序:DBACEGF     中序:ABCDEFG   令pre[]="DBACEGF"   in[]="ABCDEFG"  
BinaryTreeNode * CreateBinaryTree(ElemType * pre, ElemType *in, int length)//此种建立二叉树的方法本质上是先建立根结点 再建立左子树,再建立右子树  
{
if (length <= 0 || pre == NULL || in == NULL)////递归出口:长度为0时表示建树完毕  
{
return NULL;
}
ElemType rootValue = pre[0];
BinaryTreeNode * root = new BinaryTreeNode();//建立根节点  
root->data = rootValue;
root->left = root->right = NULL;
int leftLength, rightLength, i = 0;//左子树的长度,右子树的长度  ,下面的代码就是找到左右子树的元素,建立左右子树
while (i<length&&in[i] != rootValue)
{
i++;
}
leftLength = i;
rightLength = length – leftLength – 1;//注意对个一个遍历的序列一定满足rightLength+leftLength+1=length;左子树长度加上右子树长度加一个根结点的长度等于树所有结点的长度。  
if (leftLength>0)//建立左子树  
{
root->left = CreateBinaryTree(pre + 1, in, leftLength);////此处的关键在于寻找右子树后序序列的起始地址,和右子树的中序序列的起始地址  
}
if (rightLength>0)//建立右子树  
{
root->right = CreateBinaryTree(pre + length – rightLength, in + length – rightLength, rightLength);////此处的关键在于寻找右子树后序序列的起始地址,和右子树的中序序列的起始地址  
// 上一句等价于root->right =CreateBinaryTree(pre+1+leftLength,in+1+leftLength,rightLength);  
}
return root;
}


本文由【waitig】发表在等英博客
本文固定链接:根据先序和中序遍历建立二叉树
欢迎关注本站官方公众号,每日都有干货分享!
等英博客官方公众号
点赞 (0)分享 (0)