作者:译林hy_774 | 来源:互联网 | 2023-10-11 21:42
1类定义代码2structTreeNode3{4charval;5TreeNode*left;6TreeNode*right;7TreeNode(charx):val(x),lef
1 // 类定义代码
2 struct TreeNode
3 {
4 char val;
5 TreeNode* left;
6 TreeNode* right;
7 TreeNode(char x) : val(x), left(NULL), right(NULL) {}
8 };
9 int main()
10 {
11 char* pre = "ACDEBF";
12 char* vin = "DCEABF";
13 char* post = "DECFBA";
14 return 0;
15 }
1. 前序遍历和中序遍历还原二叉树
算法思想:描述如下:
- 根据 前序遍历 结果,第一个元素为二叉树的根节点;
- 观察 中序遍历 结果,根节点左侧的为左子树,若左子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;根节点右侧的为右子树,若右子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;
- 通过以上递归过程。先找到当前树的根节点,然后划分为左右子树,再进入左子树重复上面的过程,最后再进入右子树重复上面的过程,最终还原一棵树。
递归代码:
1 TreeNode* BinaryTreeFromOrderings(char* pre, char* vin, int length)
2 {
3 if( length == 0 ) return NULL;
4
5 int rootIndex = 0;
6 // 寻找当前根节点,记录子树元素个数
7 for(; rootIndex )
8 if( vin[rootIndex] == pre[0] ) break;
9
10 TreeNode* tree = new TreeNode( vin[rootIndex] );
11 // 返回当前左子树
12 tree ->left = BinaryTreeFromOrderings(pre + 1, vin, rootIndex );
13 // 返回当前右子树
14 tree ->right = BinaryTreeFromOrderings(pre + rootIndex + 1, vin + rootIndex + 1, length - (rootIndex + 1));
15
16 return tree;
17 }
2. 中序遍历和后序遍历还原二叉树
算法思想:描述如下:
- 根据后序遍历结果,最后一个元素为二叉树的根节点;
- 观察中序遍历结果,其中根节点左侧为左子树,若左子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;其中根节点右侧为右子树,若右子树根节点前(后)再无任何元素,则左(右)子树的左分支为空;
- 上面描述的过程是递归的。现根据后续遍历结果找根节点,根节点左侧为左子树,右侧为右子树,再进入左子树重复上面的过程,最后进入右子树重复上面的过程,最终还原一棵树。
递归代码:
TreeNode* BinaryTreeFromPostings(char* vin, char* post, int length)
{
if( length == 0 ) return NULL;
int rootIndex = 0;
// 寻找当前根节点,记录子树元素个数
for(; rootIndex )
if( vin[rootIndex] == post[length - 1]) break;
TreeNode* tree = new TreeNode( vin[rootIndex] );
// 返回当前右子树
tree ->right = BinaryTreeFromPostings(vin + rootIndex + 1, post + rootIndex, length - (rootIndex + 1) );
// 返回当前左子树
tree ->left = BinaryTreeFromPostings(vin, post, rootIndex );
return tree;
}
3. 前序遍历和后序遍历还原二叉树
已知前序和中序,后序和中序遍历序列之后,可以唯一确定一棵二叉树。但是,只知道前序和后序遍历序列,是无法分辨哪个结点是左子树或右子树。