【正文】 遞歸的方式銷毀二叉樹，思想和前序遍歷二叉樹是一致的//若采取非遞歸的方式銷毀二叉樹和層序遍歷二叉樹的思想一致status CreateBiTNode(BiTree amp。T) { //按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個字母），39。39。字符表示空樹， //采用遞歸調(diào)用的方式構(gòu)造二叉樹鏈表表示的二叉樹為T char ch。 printf(請輸入關(guān)鍵字：\n)。 scanf(%c, amp。ch)。 getchar()。 if (ch == 39。39。) T = NULL。 else { if (!(T = (BiTNode*)malloc(sizeof(BiTNode)))) exit(OVERFLOW)。 Tdata = ch。 printf(請輸入結(jié)點(diǎn)值：\n)。 scanf(%d, amp。Tindex)。 getchar()。 CreateBiTNode(Tlchild)。 CreateBiTNode(Trchild)。 } return OK。}status ClearBiTree(BiTree amp。T) { if (T) { Tlchild = NULL。 Trchild = NULL。 } return OK。}status BiTreeEmpty(BiTree T) { if (T) return FALSE。 return TRUE。}//若T為空二叉樹返回TRUEstatus BiTreeDepth(BiTree T) { if (!T) return 0。//若T為NULL，即空二叉樹深度返回為0 else { if ((Tlchild == NULL) amp。amp。 (Trchild == NULL)) return 1。 else return 1+MAX(BiTreeDepth(Tlchild), BiTreeDepth(Trchild))。 }}//以下三個函數(shù)Pre_order,Mid_order,Post_order為遞歸方式遍歷二叉樹status Pre_order(BiTree T, status (*visit)(TElemType e)) { if (T) { if (visit(Tdata)) if (Pre_order(Tlchild, visit)) if (Pre_order(Trchild, visit)) return OK。 return ERROR。 } else return OK。}status Mid_order(BiTree T, status(*visit)(TElemType e)) { if (T) { if (Mid_order(Tlchild, visit)) if (visit(Tdata)) if (Mid_order(Trchild, visit)) return OK。 return ERROR。 } else return OK。}status Post_order(BiTree T, status(*visit)(TElemType e)) { if (T) { if (Post_order(Tlchild, visit)) if (Post_order(Trchild, visit)) if (visit(Tdata)) return OK。 return ERROR。 } else return OK。}//遍歷二叉樹的非遞歸算法,建立遞歸工作棧status Pre_order_b(BiTree T, status(*visit)(TElemType e)) { BiTNode *st[MAXSIZE], *p。 int top = 0。 //置空棧 if (T) { st[top++] = T。 while (top) { p = st[top]。 //彈出棧頂指針 if(!visit(pdata)) return ERROR。 if (prchild != NULL) st[top++] = prchild。 //將右子樹的根結(jié)點(diǎn)存入棧中 if (plchild != NULL) st[top++] = plchild。 //將左子樹的根結(jié)點(diǎn)存入棧中 } return OK。 }}//先序遍歷的另一種算法思想是直接//在第一次訪問根結(jié)點(diǎn)時對根結(jié)點(diǎn)進(jìn)行操作status Mid_order_b(BiTree T, status(*visit)(TElemType e)) { BiTree st[MAXLENG]。 //定義指針棧，并假設(shè)二叉樹的深度不超過10 int top = 0。 //置空棧,top為棧頂元素上一個單元的地址 do { while (T) //根指針T表示的為非空二叉樹 { if (top == MAXLENG) exit(OVERFLOW)。 st[top++] = T。 //根指針進(jìn)棧 T = Tlchild。 //T移向左子樹 } //循環(huán)結(jié)束表示以棧頂元素的指向為 //根結(jié)點(diǎn)的二叉樹的左子樹遍歷結(jié)束 if (top) //為非空棧 { T = st[top]。 //彈出根指針 if(!visit(Tdata)) return ERROR。 //對根結(jié)點(diǎn)進(jìn)行操作 T = Trchild。 } } while (top || T)。 //父結(jié)點(diǎn)未訪問或者右子樹未遍歷 return OK。}//用一個堆棧并設(shè)置標(biāo)志來實現(xiàn)后續(xù)非遞歸遍歷status Post_order_b(BiTree T, status(*visit)(TElemType e)) { BiTNode *st[MAXLENG], *pre。 int flag, top = 0。 if (T) { do { while (T) { if (top == MAXLENG) exit(OVERFLOW)。 st[top++] = T。 T = Tlchild。 }//循環(huán)結(jié)束時表示以棧頂元素為指向的 //根節(jié)點(diǎn)的二叉樹的左子樹遍歷完畢 pre = NULL。 flag = 1。//設(shè)置標(biāo)志位，用于結(jié)束內(nèi)層循環(huán) while (topamp。amp。flag) { T = st[top 1]。 //訪問左子樹根結(jié)點(diǎn) if (Trchild == pre) { if (!visit(Tdata)) return ERROR。 top。//彈出已訪問的根結(jié)點(diǎn) pre = T。 } else { T = Trchild。 flag = 0。//用于跳出內(nèi)層循環(huán) } } } while (top)。 }}//后序非遞歸遍歷也可以用雙堆棧來實現(xiàn)char Root(BiTree T) {//返回T的根 if (!T) return NULL。 else return Tdata。}//獲得結(jié)點(diǎn)，返回結(jié)點(diǎn)的值int Value(BiTree T, char e) { if (!T) return ERROR。 //若二叉樹為空，返回Error BiTNode *st[MAXLENG], *p。 int top = 0。 //置空棧 st[top++] = T。 while (top) { p = st[top]。 //先序遍歷，彈出棧頂元素 if (pdata == e) return pindex。 else { if(prchild!=NULL) st[top++] = prchild。 if(plchild!=NULL) st[top++] = plchild。 } } return ERROR。}status Assign(BiTree T, char e, int Value) { if (!T) return ERROR。 //若二叉樹為空，返回Error BiTNode *st[MAXLENG], *p。 int top = 0。 //置空棧 st[top++] = T。 while (top) { p = st[top]。 //先序遍歷，彈出棧頂元素 if (pdata == e) { pindex = Value。 return OK。 } else { if (prchild != NULL) st[top++] = prchild。 if (plchild != NULL) st[top++] = plchild。 } } return ERROR。}BiTNode* Parent(BiTree T, char e) { //若e是T的非根結(jié)點(diǎn)，返回它的雙親結(jié)點(diǎn)指針 //否則返回NULL BiTree T1。 if (T) { if ((Tlchild!=NULLamp。amp。Tlchilddata == e) ||(Trchild!=NULLamp。amp。 Trchilddata == e)) return T。 T1 = Parent(Tlchild, e)。 if (T1 != NULL) return T1。 T1 = Parent(Trchild, e)。 if (T1 != NULL) return T1。 } return NULL。}BiTNode* LeftSibling(BiTree T, char e) { //若e無左孩子，返回NULL BiTree T1=NULL。 if (T) { if (Trchild!=NULLamp。amp。Trchilddata == e) return Tlchild。 T1 = LeftSibling(Tlchild, e)。 //遞歸調(diào)用對左子樹進(jìn)行操作 if (T1 != NULL) return T1。 T1 = LeftSibling(Trchild, e)。 //遞歸調(diào)用對右子樹進(jìn)行操作 if (T1 != NULL) return T1。 } return NULL。}BiTNode* RightSibling(BiTree T, char e) { //若e無右孩子，返回NULL BiTree T1 = NULL。 if (T) { if (Tlchild!=NULLamp。amp。Tlchilddata == e) return Trchild。 T1 = LeftSibling(Tlchild, e)。 //遞歸調(diào)用對左子樹進(jìn)行操作 if (T1 != NULL) return T1。 T1 = LeftSibling(Trchild, e)。 //遞歸調(diào)用對右子樹進(jìn)行操作 if (T1 != NULL) return T1。 } return NULL。}BiTNode* LeftChild(BiTree T, char e) { BiTree p。 if (T) { if (Tdata == e) return Tlchild。 p = LeftChild(Tlchild, e)。 if (p != NULL) return p。 p = LeftChild(Trchild, e)。 if (p != NULL) return p。 } return NULL。}BiTNode* RightChild(BiTree T, char e) { BiTree p。 if (T) { if (Tdata == e) return Trchild。 p = RightChild(Tlchild, e)。 if (p != NULL) return p。 p = RightChild(Trchild, e)。 if (p != NULL) return p。 } return NULL。}status InsertChild(BiTree T, BiTree p, int LR, BiTree c) { if (!T) { printf(二叉樹不存在！\n)。 return ERROR。 } if (crchild != NULL) { printf(待插入二叉樹的右子樹不為空！\n)。 return ERROR。 } if (LR == 0) { crchild = plchild。 plchild = c。 }//若LR為0，插入c為T中p所指結(jié)點(diǎn)的左子樹 else { crchild = prchild。 prchild = c。 }//若LR為1，插