[科普中國]-擴(kuò)充二叉樹

擴(kuò)充二叉樹是二叉樹中的一種，是指在二叉樹中出現(xiàn)空子樹的位置增加空樹葉，所形成的二叉樹。

詳解擴(kuò)充二叉樹是二叉樹中的一種，是指在二叉樹中出現(xiàn)空子樹的位置增加空樹葉，所形成的二叉樹。1

在二叉樹中出現(xiàn)空的子樹（包括樹葉）上增加空的樹葉，使子樹成為滿二叉樹（國際定義）的二叉樹稱之為擴(kuò)充二叉樹。

從擴(kuò)充的二叉樹的根到每個(gè)外部結(jié)點(diǎn)的路徑長度之和稱為外部路徑長度（E），擴(kuò)充的二叉樹里從根到每個(gè)內(nèi)部結(jié)點(diǎn)的路徑長度之和稱為內(nèi)部路徑長度（I），它們之間的關(guān)系滿足E=I+2N（N為內(nèi)部結(jié)點(diǎn)數(shù)）。

代碼實(shí)現(xiàn)由于先序、中序和后序序列中的任一個(gè)都不能唯一確定一棵二叉樹，所以對二叉樹做如下處理，將二叉樹的空結(jié)點(diǎn)用·補(bǔ)齊，如圖所示。我們把這樣處理后的二叉樹稱為原二叉樹的擴(kuò)展二叉樹，擴(kuò)展二叉樹的先序和后序序列能唯一確定其二叉樹。

現(xiàn)給出擴(kuò)展二叉樹的先序序列，要求輸出其中序和后序序列。

輸入擴(kuò)展二叉樹的先序序列。

輸出輸出其中序和后序序列。

輸入樣例ABD..EF..G..C..

輸出樣例DBFEGACDFGEBCA

代碼#include#include#include#includeusing namespace std;typedef struct node;typedef node *tree;//tree相當(dāng)于nodestruct node{//一個(gè)節(jié)點(diǎn)包括數(shù)據(jù)域，左右孩子 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); coutrchild); } }void printhx(tree &bt)//輸出后序序列{ if(bt) { printhx(bt->lchild); printhx(bt->rchild); cout>s; i=-1; build(bt); printzx(bt);//中序 cout