6.27
[問題]
假設一棵二叉樹的先序序列為ebadcfhgikj和中序序列為abcdefghijk。請畫出該樹。
[解答]
6.29
[問題]
假設一棵二叉樹的層序序列為abcdefghij和中序序列為dbgehjacif。請畫出該樹。
6.37
[問題]
試利用棧的基本操作寫出先序遍歷二叉樹的非遞迴演算法。
[解答提示]
改寫教材p.130-131演算法6.2或6.3。
將if (!visit(p->data)) return error;提前。
6.43
[問題]
編寫遞迴演算法，將二叉樹中所有結點的左、右子樹相互交換。
status exchange-lr(bitree bt)
return ok;
}//exchange-lr
6.45
[問題]
編寫遞迴演算法，對於二叉樹中每乙個元素值為x的結點，刪去以它為根的子樹，並釋放相應的空間。
[解答]
status del-subtree(bitree bt)
return ok;
}//del-subtree
status search-del(bitree bt, telemtype x)
} return ok;
}//search-del
第六章樹和二叉樹
6.33
int is_descendant_c(int u,int v)//在孩子儲存結構上判斷u是否v的子孫,是則返回1,否則返回0
return 0;
}//is_descendant_c
6.34
int is_descendant_p(int u,int v)//在雙親儲存結構上判斷u是否v的子孫,是則返回1,否則返回0
//is_descendant_p
6.35
這一題根本不需要寫什麼演算法,見書後注釋:兩個整數的值是相等的.
6.36
int bitree_sim(bitree b1,bitree b2)//判斷兩棵樹是否相似的遞迴演算法
//bitree_sim
6.37
void preorder_notrecurve(bitree t)//先序遍歷二叉樹的非遞迴演算法
//向左走到盡頭
pop(s,p);
if(!stackempty(s))
}//while
}//preorder_notrecurve
6.38
typedef struct mark;
} pmtype; //有mark域的結點指標型別
void postorder_stack(bitree t)//後續遍歷二叉樹的非遞迴演算法,用棧
); //根結點入棧
while(!stackempty(s))
); //訪問左子樹
break;
case 1:
push(a.ptr,2); //修改mark域
if(a.ptr->rchild) push(); //訪問右子樹
break;
case 2:
visit(a.ptr); //訪問結點,返回
}}//while
}//postorder_stack
分析:為了區分兩次過棧的不同處理方式,在堆疊中增加乙個mark域,mark=0表示剛剛訪問此結點,mark=1表示左子樹處理結束返回,mark=2表示右子樹處理結束返回.每次根據棧頂元素的mark域值決定做何種動作.
6.39
typedef struct mark;
} ebtnode,ebitree; //有mark域和雙親指標域的二叉樹結點型別
void postorder_notrecurve(ebitree t)//後序遍歷二叉樹的非遞迴演算法,不用棧
}//postorder_notrecurve
分析:本題思路與上一題完全相同,只不過結點的mark值是儲存在結點中的,而不是暫存在堆疊中,所以訪問完畢後要將mark域恢復為0,以備下一次遍歷.
6.40
typedef struct pbtnode,pbitree; //有雙親指標域的二叉樹結點型別
void inorder_notrecurve(pbitree t)//不設棧非遞迴遍歷有雙親指標的二叉樹
else if(p->parent->lchild==p) p=p->parent; //當自己是雙親的左孩子時後繼就是雙親
else
//當自己是雙親的右孩子時後繼就是向上返回直到遇到自己是在其左子樹中的祖先
}//while
}//inorder_notrecurve
6.41
int c,k; //這裡把k和計數器c作為全域性變數處理
void get_preseq(bitree t)//求先序序列為k的結點的值
else
}//if
}//get_preseq
main()
//main
6.42
int leafcount_bitree(bitree t)//求二叉樹中葉子結點的數目
//leafcount_bitree
6.43
void bitree_revolute(bitree t)//交換所有結點的左右子樹
//bitree_revolute
資料結構C語言描述耿國華習題及答案
第一章習題答案 2 3 1 包含改變量定義的最小範圍 2 資料抽象 資訊隱蔽 3 資料物件 物件間的關係 一組處理資料的操作 4 指標型別 5 集合結構 線性結構 樹形結構 圖狀結構 6 順序儲存 非順序儲存 7 一對 一 一對多 多對多 8 一系列的操作 9 有限性 輸入 可行性 4 1 a 2 ...
資料結構C語言描述耿國華習題及答案
第一章習題答案 2 3 1 包含改變量定義的最小範圍 2 資料抽象 資訊隱蔽 3 資料物件 物件間的關係 一組處理資料的操作 4 指標型別 5 集合結構 線性結構 樹形結構 圖狀結構 6 順序儲存 非順序儲存 7 一對 一 一對多 多對多 8 一系列的操作 9 有限性 輸入 可行性 4 1 a 2 ...
《資料結構》習題答案
習題1一 選擇題 1 c 2 b 3 b 4 b d 5 c 6 a 7 c b 8 d 9 b 10 d 二 填空題 1 相互關係 2 一對 一 一對多 多對多 3 線性結構 集合 圖 樹 4 有窮性 確定性 可行性 輸入 輸出 5 o n 6 o n2 7 物理 8 1 log2n n n2 2...