template <class T>void BiTree<T>::Creat(BiNode<T> * root,int i1,int i2,int k){//root為當前根結點，i1，i2分別為前序和中序序列的起始下標，k為序列長度int m=0,llen=0,rlen=0;if(k<=0)root=NULL;//建立空樹else{root=new BiNode<T>;root->data=pre[i1]; //根結點為前序序列中的起始結點m=Find(pre[i1],pin,i2);//從中序序列pin的i2開始，查找值為pre[i1]的位置llen=m-i2; //求左子樹的長度rlen=k-(llen+1); //求右子樹的長度，由于下標從i2開始，因此llen要+1Creat(root->lchild,i1+1,i2,llen); //遞歸建立左子樹Creat(root->rchild,i1+llen+1,m+1,rlen);//遞歸建立右子樹}}構造函數如下：template <class T> //有參構造函數,通過前序和中序序列建立二叉樹BiTree<T>:: BiTree(int i1,int i2,int k){Creat(this->root,i1,i2,k);}
1 回答
回首憶惘然
TA貢獻1847條經驗 獲得超11個贊
二叉樹的遍歷是指按照一定次序訪問樹中所有結點，并且每個節點僅被訪問一次的過程。
1、先序遍歷（前序）
（1）訪問根節點；
（2）先序遍歷左子樹；
（3）先序遍歷右子樹。
2、中序遍歷
（1）中序遍歷左子樹；
（2）訪問根節點；
（3）中序遍歷右子樹。
3、后序遍歷
（1）后序遍歷左子樹；
（2）后序遍歷右子樹‘
（3）訪問根節點。
記住訪問根結點的時機就可以區分三種遍歷方法了。
同時知道一棵二叉樹的先序序列和中序序列，或者同時知道中序序列和后序序列，就能確定這棵二叉樹的結構。構造算法相信你已經學習過，在任一本介紹數據結構的書上應該也有描述的。由于涉及到算法細節，這里就不細說了。
下面根據你例子中給出的序列來介紹確定二叉樹結構的步驟：
（1）后序序列中最后一個為樹的根節點，即c為二叉樹的根結點；
（2）中序遍歷中根節點把序列分為左右子樹的中序遍歷序列兩個部分，在你的例子在右子樹沒有中序遍歷序列（中序遍歷序列中c右邊沒有序列），故可知二叉樹的左子樹的后序遍歷序列為dabe，中序遍歷序列為deba；
（3）應用（1）的方法，確定c的左子樹的根結點為e，并把以e為根結點的子樹的中序遍歷序列劃分為d（以e為根結點的左子樹的中序遍歷序列）和ba（以e為根結點的右子樹的中序遍歷序列）兩個部分，后序遍歷序列為dab；
（4）應用（1）的方法，可確定e的左結點為b；
（5）應用（1）的方法，可確定e的右結點為a；
（6）最后，可確定a無左結點，右結點為d。
構造的二叉樹如圖中所示。
那么可獲得前序遍歷序列為cedba
- 1 回答
- 0 關注
- 151 瀏覽
添加回答
舉報
0/150
提交
取消