ch04.树--二叉树创建(前序中序与中序后序)

二叉树的创建（前序中序与中序后序）

0.引言1.单独中序序列建树不唯一2.'前+中'，'中+后' 建树3.代码实现4.完整测试代码5.指针的引用

0.引言

大话数据结构书中讲，将前序递归建树中的顺序变一下就是中序，后序，但是当我测试的时候无法成功，书中有错：

结论放前面，常用的几种建树方式：

1.前序序列可以建树，可能不唯一，但把空节点标注出来可以唯一。2.前序遍历序列和中序遍历序列，可以唯一建树。3.后序遍历序列和中序遍历序列，可以唯一建树。4.层序遍历+三种组合。

1.单独中序序列建树不唯一

前序建树不唯一，但是只要把空节点标出来，它就能构建出唯一树。这也是一些算法书上使用#来标注空节点的原因。为什么不唯一，可以参考这篇博客.

preorder: 1 2 3 4; postorder:2 4 3 1.两种序列不加空节点标志都可以建出case1、case2的情形，而且遍历出来结果也是正确的：

该图也来自参考博客，但是感觉后面没有讲清楚，可不看了。

2.‘前+中’，‘中+后’ 建树

这里参考这篇博客，讲得十分的详细。语言总结一下就是，前序序列和后序序列的根节点在最前和最后，能够知道它的位置；而中序序列无法确定哪个是根节点，所以建树不唯一。知道根节点后，从中序序列就可以知道哪部分是左儿子哪部分是右儿子了。

3.代码实现

就以上述参考博客为例子进行实现，实现过程我也画了一遍：

两种建树函数，对照着图看逻辑很清晰了！

// 中序后序建立二叉树 void InPostCraeteBiTree(BiTree *bt, char *Inorder, char *Postorder,int n) { if (n == 0) { *bt = NULL; return; } (*bt) = (BiTree)malloc(sizeof(BiTreeNode)); if (!*bt) exit(OVERFLOW); (*bt)->Element = Postorder[n - 1];//后序序列的最后一位是根节点 int i; for (i = 0; i < n; i++) if (Inorder[i] == Postorder[n - 1])//在中序序列中找到根节点Inorder[i] break; //左儿子就是Inorder[0-i],然后再深入找下一轮根节点，后序序列也传i个进入下一轮 InPostCraeteBiTree(&(*bt)->Left, Inorder, Postorder,i); //右儿子就是Inorder[（i+1）- n] ,个数就为（n-i-1）,然后再深入找下一轮根节点,后序序列也传（n-i-1）个进入下一轮,但注意i也要包含，因为最后一位才是节点 InPostCraeteBiTree(&(*bt)->Right,Inorder + i + 1, Postorder + i, n - i - 1); } // 前序中序建立二叉树 void PreInCraeteBiTree(BiTree *bt, char *Preorder, char *Inorder, int n) { if (n == 0) { *bt = NULL; return; } (*bt) = (BiTree)malloc(sizeof(BiTreeNode)); if (!*bt) exit(OVERFLOW); (*bt)->Element = Preorder[0];//前序序列的第一位是根节点 int i; for (i = 0; i < n; i++) if (Inorder[i] == Preorder[0])//在中序序列中找到根节点Inorder[i] break; //左儿子就是Inorder[0-i],然后再深入找下一轮根节点，后序序列也传i个进入下一轮，但注意前序序列第一位是节点 PreInCraeteBiTree(&(*bt)->Left, Preorder + 1, Inorder, i); //右儿子就是Inorder[（i+1）- n] ,个数就为（n-i-1）,然后再深入找下一轮根节点,前序序列也传（n-i-1）个进入下一轮 PreInCraeteBiTree(&(*bt)->Right, Preorder + i + 1, Inorder + i + 1, n - i - 1); }

4.完整测试代码

#include <iostream> using namespace std; typedef char ElementType; typedef struct BiTreeNode *PtrToTree; typedef PtrToTree BiTree; struct BiTreeNode { ElementType Element; BiTree Left; BiTree Right; }; //这种方法也行，但是必须得一个函数外的全局变量来实现，不如全部用指针得了 //int N = 0;//全局变量 //void PreorderCraeteBiTree(BiTree *bt, char* Preorder) //{ // if (*(Preorder + N) == '#')//递归出口 // { // N++; // *bt = NULL; // } // else // { // *bt = (BiTree)malloc(sizeof(BiTreeNode)); // if (!*bt) // exit(OVERFLOW); // // (*bt)->Element = *(Preorder + N); // N++; // PreorderCraeteBiTree(&(*bt)->Left, Preorder); // PreorderCraeteBiTree(&(*bt)->Right, Preorder); // } //} //前序生成二叉树，但必须将空节点标注出来，注意这里是用了指针的引用 void PreorderCraeteBiTree(BiTree *bt,char* &Preorder) { if (*Preorder == '#')//递归出口 { *bt = NULL; return; } else { *bt = (BiTree)malloc(sizeof(BiTreeNode)); if (!*bt) exit(OVERFLOW); (*bt)->Element = *Preorder; PreorderCraeteBiTree(&(*bt)->Left,++Preorder); PreorderCraeteBiTree(&(*bt)->Right,++Preorder); } } // 中序后序建立二叉树 void InPostCraeteBiTree(BiTree *bt, char *Inorder, char *Postorder,int n) { if (n == 0) { *bt = NULL; return; } (*bt) = (BiTree)malloc(sizeof(BiTreeNode)); if (!*bt) exit(OVERFLOW); (*bt)->Element = Postorder[n - 1];//后序序列的最后一位是根节点 int i; for (i = 0; i < n; i++) if (Inorder[i] == Postorder[n - 1])//在中序序列中找到根节点Inorder[i] break; //左儿子就是Inorder[0-i],然后再深入找下一轮根节点，后序序列也传i个进入下一轮 InPostCraeteBiTree(&(*bt)->Left, Inorder, Postorder,i); //右儿子就是Inorder[（i+1）- n] ,个数就为（n-i-1）,然后再深入找下一轮根节点,后序序列也传（n-i-1）个进入下一轮,但注意i也要包含，因为最后一位才是节点 InPostCraeteBiTree(&(*bt)->Right,Inorder + i + 1, Postorder + i, n - i - 1); } // 前序中序建立二叉树 void PreInCraeteBiTree(BiTree *bt, char *Preorder, char *Inorder, int n) { if (n == 0) { *bt = NULL; return; } (*bt) = (BiTree)malloc(sizeof(BiTreeNode)); if (!*bt) exit(OVERFLOW); (*bt)->Element = Preorder[0];//前序序列的第一位是根节点 int i; for (i = 0; i < n; i++) if (Inorder[i] == Preorder[0])//在中序序列中找到根节点Inorder[i] break; //左儿子就是Inorder[0-i],然后再深入找下一轮根节点，后序序列也传i个进入下一轮，但注意前序序列第一位是节点 PreInCraeteBiTree(&(*bt)->Left, Preorder + 1, Inorder, i); //右儿子就是Inorder[（i+1）- n] ,个数就为（n-i-1）,然后再深入找下一轮根节点,前序序列也传（n-i-1）个进入下一轮 PreInCraeteBiTree(&(*bt)->Right, Preorder + i + 1, Inorder + i + 1, n - i - 1); } //前序遍历：节点+左+右 void PreorderTraversal(BiTree *bt) { if (*bt == NULL) return; cout << (*bt)->Element; PreorderTraversal(&(*bt)->Left); PreorderTraversal(&(*bt)->Right); } //中序遍历：左+节点+右 void InorderTraversal(BiTree *bt) { if (*bt == NULL) return; InorderTraversal(&(*bt)->Left); cout << (*bt)->Element; InorderTraversal(&(*bt)->Right); } //后序遍历: 左+右+节点 void PostorderTraversal(BiTree *bt) { if (*bt == NULL) return; PostorderTraversal(&(*bt)->Left); PostorderTraversal(&(*bt)->Right); cout << (*bt)->Element; } void BiTreeTest() { char PreorderStr[] = "EACBDGF"; char InorderStr[] = "ABCDEFG"; char PostOrderStr[] = "BDCAFGE"; int N = sizeof(PreorderStr) / sizeof(PreorderStr[0]); cout << "Source PreorderStr: " << PreorderStr << endl << "Source InorderStr: " << InorderStr << endl << "Source PostOrderStr: " << PostOrderStr << endl<<endl; /****************中序+后序建树测试***********************/ BiTree BT; InPostCraeteBiTree(&BT, InorderStr, PostOrderStr, N-1);//最后一位'\0'也被sizeof进去了，所以使用N-1 cout << "Result of the tree build with Inorder + Postorder: "<<endl; cout << "PreorderTraversal: "; PreorderTraversal(&BT); cout << endl; cout << "InorderTraversal: "; InorderTraversal(&BT); cout << endl; cout << "PostorderTraversal: "; PostorderTraversal(&BT); cout << endl<<endl<<endl; /****************前序+中序建树测试***********************/ BiTree BT1; PreInCraeteBiTree(&BT1, PreorderStr, InorderStr, N - 1); cout << "Result of the tree build with Preorder + Inorder : "<<endl; cout << "PreorderTraversal: "; PreorderTraversal(&BT1); cout << endl; cout << "InorderTraversal: "; InorderTraversal(&BT1); cout << endl; cout << "PostorderTraversal: "; PostorderTraversal(&BT1); cout << endl<<endl; /***********************前序建树测试************************/ char PreorderStr2[] = "EA#CB##D##GF###";//前序建树必须标注出空节点 BiTree BT2; char *Preorderstr = PreorderStr2; char *&Preorder = Preorderstr;//指针的引用 PreorderCraeteBiTree(&BT2, Preorder); cout << "Result of the tree build with Preorder : " << endl; cout << "PreorderTraversal: "; PreorderTraversal(&BT2); cout << endl; cout << "InorderTraversal: "; InorderTraversal(&BT2); cout << endl; cout << "PostorderTraversal: "; PostorderTraversal(&BT2); cout << endl << endl; } int main(int argc, char** argv) { BiTreeTest(); system("pause"); return 0; }

测试结果：

5.指针的引用

指针的引用参考.

在前序建树时，参数使用指针的引用，因为要让数组一直++下去，值传递，导致只能在前几个循环。如下图所示，使用指针做形参无法完全的递归下去。特别注意这一点。

我突然发现一个问题，要是有重复的元素呢？那种粗暴的找节点方式可能行不通，需要键值对解决