．設一棵二叉樹的結點定義為
struct BinTreeNode{ElemType data; BinTreeNode *leftchild*rightchild;}
現采用輸入廣義表表示建立二叉樹具體規定如下
()樹的根結點作為由子樹構成的表的表名放在表的最前面
()每個結點的左子樹和右子樹用逗號隔開若僅有右子樹沒有左子樹逗號不能省略
()在整個廣義表輸入的結尾加上一個特殊的符號(例如#)表示輸入結束
例如對於如圖所示的二叉樹其廣義表表示為A(B(DE(G))C(F))
此算法的基本思路是依次從保存廣義表的字符串ls中輸入每個字符若遇到的是字母(假設以字母作為結點的值)則表示是結點的值應為它建立一個新的結點並把該結點作為左子女(當k=)或右子女(當k=)鏈接到其雙親結點上若遇到的是左括號(則表明子表的開始將k置為若遇到的是右括號)則表明子表結束若遇到的是逗號則表示以左子女為根的子樹處理完畢接著處理以右子女為根的子樹將K置為在算法中使用了一個棧s在進入子表之前將根結點指針進棧以便括號內的子女鏈接之用在子表處理結束時退棧相關的棧操作如下
MakeEmpty(s) 置空棧 Push(sp) 元素p入棧
Pop(s) 退棧 Top(s) 存取棧頂元素的函數
下面給出了建立二叉樹的算法其中有個語句缺失請閱讀此算法並把缺失的語句補上(每空分)
void CreatBinTree(BinTreeNode *&BTchar ls){
Stack<BinTreeNode*>s; MakeEmpty(s);
BT=NULL; //置空二叉樹
BinTreeNode *p;
int k; istream ins(ls) //把串ls定義為輸入字符串流對象ins ;
char ch; ins>>ch; //從ins順序讀入一個字符
while (ch != #){ //逐個字符處理直到遇到#為止
switch(ch){
case (: ()______k=; break;
case ): pop(s); break;
case : ()______ break;
default :p=new BinTreeNode; ()_______;p>leftChild=NULL;p>rightChild=NULL;
if(BT==NULL) ()______else if (k==) top(s)>leftChild=p;
else top(s)>rightChild=p;
}
()______; }
}【清華大學 六 (分)】
[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []
From:http://tw.wingwit.com/Article/program/sjjg/201311/23470.html
