擴充二叉樹是二叉樹中的一種，是指在二叉樹中出現空子樹的位置增加空樹葉，所形成的二叉樹。
基本介紹
- 中文名：擴充二叉樹
- 外文名：Extended binary tree
- 學科：程式語言
詳解,代碼實現,輸入,輸出,輸入樣例,輸出樣例,代碼,
詳解
擴充二叉樹是二叉樹中的一種，是指在二叉樹中出現空子樹的位置增加空樹葉，所形成的二叉樹。
從擴充的二叉樹的根到每個外部結點的路徑長度之和稱為外部路徑長度（E），擴充的二叉樹里從根到每個內部結點的路徑長度之和稱為內部路徑長度（I），它們之間的關係滿足E=I+2N（N為內部結點數）。
代碼實現
由於先序、中序和後序序列中的任一個都不能唯一確定一棵二叉樹，所以對二叉樹做如下處理，將二叉樹的空結點用·補齊，如圖所示。我們把這樣處理後的二叉樹稱為原二叉樹的擴展二叉樹，擴展二叉樹的先序和後序序列能唯一確定其二叉樹。
現給出擴展二叉樹的先序序列，要求輸出其中序和後序序列。
輸入
擴展二叉樹的先序序列。
輸出
輸出其中序和後序序列。
輸入樣例
ABD..EF..G..C..
輸出樣例
DBFEGACDFGEBCA
代碼
#include<iostream>#include<string>#include<cstring>#include<algorithm>using namespace std;typedef struct node;typedef node *tree;//tree相當於nodestruct node{//一個節點包括數據域，左右孩子 char data; treelchild,rchild;};tree bt;int i;string s;void build(tree &bt)//建樹{ if(s[++i]!='.') { bt=new node; bt->data=s[i]; build(bt->lchild); build(bt->rchild); } else bt=NULL;}void printzx(tree &bt)//輸出中序序列{ if(bt) { printzx(bt->lchild); cout<<bt->data; printzx(bt->rchild); } }void printhx(tree &bt)//輸出後序序列{ if(bt) { printhx(bt->lchild); printhx(bt->rchild); cout<<bt->data; }}int main(){// freopen("tree_b.in","r",stdin);// freopen("tree_b.out","w",stdout); cin>>s; i=-1; build(bt); printzx(bt);//中序 cout<<endl; printhx(bt);//後序 cout<<endl; return 0;}