[計算機軟件及應用]ch-文庫吧資料
2024-10-22 23:09本頁面
【正文】 ? （ 1）若 F為空，則 B為空； ? （ 2）若 F非空，則森林中第一棵樹 T1的根結點為二叉樹 B的根結點， B的左子樹 LB由樹 T1根結點下的子樹森林轉換而成。 樹和森林 ? 2. 森林轉換成二叉樹 ? 對于森林 F中的每一棵樹 Ti，樹根結點下的若干棵子樹可看成是樹根結點下的子樹森林；對于二叉樹 B，根結點下的左右子樹 LB， RB仍是一棵二叉樹。 ? （ 2）對樹中的每個結點，只保留它與第一個孩子 結點之間的連線，刪去它與其它孩子結點之 間的連線。鏈表中每個結點的結構相同，都有三個域：數(shù)據(jù)域存放樹中結點的信息，孩子域存放該結點的第一個孩子結點（從左算起）的地址，兄弟域存放該結點的下一個兄弟結點（從左向右）的地址。與雙親表示法相反，孩子表示法便于查找樹中某結點的孩子，由表中某結點的指針域 headptr即可得到該結點的孩子結點。 樹和森林 ? 2. 孩子表示法 ? 孩子表示法是把每個結點的孩子結點鏈接形成單鏈表，n個結點有 n個孩子鏈表（葉子結點的孩子鏈表為空）。這樣的存儲結構稱之為靜態(tài)鏈表結構。 ? 此過程不斷進行，當隊列為空時，二叉樹的層次遍歷結束。由層次遍歷的定義可以推知，在進行層次遍歷時，對一層結點訪問完后，再按照它們的訪問次序?qū)Ω鱾€結點的左孩子和右孩子順序訪問，這樣一層一層進行，先遇到的結點先訪問，這與隊列的操作原則比較吻合。首先將 T和 tag（為 0）入棧，遍歷左子樹；返回后，修改棧頂 tag為 1，遍歷右子樹；最后訪問根結點。 二叉樹 ? （ 2）中序遍歷非遞歸實現(xiàn) ? 思路：先將 bt入棧，遍歷左子樹；遍歷完左子樹返回時，棧頂元素應為 bt，出棧，訪問 btdata，再中序遍歷 bt的右子樹。 二叉樹 ? 2. 二叉樹遍歷的非遞歸實現(xiàn) ? 對于非遞歸算法，引入棧模擬遞歸形式，初始時棧為空。 二叉樹 ? （ 2）中序遍歷二叉樹 ? 若二叉樹非空，則依次進行如下操作： ? ① 中序遍歷左子樹； ? ② 訪問根結點； ? ③ 中序遍歷右子樹。這種存儲結構既便于查找孩子結點，又便于查找雙親結點；但是，相對于二叉鏈表存儲結構而言，它增加了空間開銷。 二叉樹 其中， data域存放某結點的數(shù)據(jù)信息； lchild與 rchild分別存放指向左孩子和右孩子的指針，當左孩子或右孩子不存在時，相應指針域值為空（用符號 ∧ 或NULL表示）。通常有下面兩種形式。一般是按照二叉樹結點從上至下、從左到右的順序存儲。編號的結點可能只有左孩子結點，可能是既有左孩子結點又有右孩子結點。 ? 性質(zhì) 5 對一棵有 n個結點的完全二叉樹的結點按層自 左向右編號，則對任一編號為 i(1≤i≤n)的結 點有下列性質(zhì)： ? （ 1）若 i=1，則結點 i是二叉樹的根，若 i1，則結 點 i的雙親結點是； ? （ 2）若 2i≤n，則結點 i有左孩子，左孩子的編號 是 2i，否則結點 i無左孩子，并且是葉子結點； ? （ 3）若 2i+1≤n，則結點 i有右孩子，右孩子的編號 是 2i+1，否則結點 i無右孩子。 ? 性質(zhì) 2 深度為 k的二叉樹至多有 2k1個結點 (k≥1)。 （ 8） SEARCH(BT,X) 在二叉樹 BT中查找數(shù)據(jù)元素 X。 （ 6） DELETEL(BT,PARENT) 在二叉樹 BT中刪除結點PARENT的左子樹。 （ 5） TREEDEPTH(BT) 求二叉樹的深度。 ? 二叉樹 （ 4） INSERTR(BT,X,PARENT) 將數(shù)據(jù)域信息為
教學課件相關推薦
鄂ICP備17016276號-1