第6章樹與二叉樹-在線瀏覽
2024-12-27 15:07本頁面
【正文】 ee) 創(chuàng)建一棵樹 tree 銷毀一棵已有的樹tree 創(chuàng)建一棵樹 tree 判樹是否為空 求樹的度 treeDepth(tree) treeRoot(tree) treeInsert(amp。tree,elem) 求樹的高度 (深度 ) 求樹的根 在樹 tree中 ,按照某種規(guī)則將元素 elem插入到樹中合適位置 在樹 tree中 ,按照某種規(guī)則將樹中元素 elem刪除 treeTraverse(tree, visit) treeGetParent(tree,elem,amp。child) 遍歷樹 tree各元素，并用visit代表的操作處理元素數(shù)據(jù) 在樹 tree中求節(jié)點 elem的父節(jié)點，并將結果放入parent中 說明 :在樹 tree中求節(jié)點 parent的第 order個子節(jié)點，并將結果放入 child中 treeSetChild(tree,parent,order,child) } 在樹 tree中設置節(jié)點parent的第 order個子節(jié)點，待設置的值已經(jīng)放入 child中 二叉樹 二叉樹的定義與基本運算 二叉樹是一個集合 T；它可以是空集 ， 也可以是一個由節(jié)點組成的有限集 。 (2) 如果 T是有限集 ， 則 T由一個特定的 、 稱之為根 的節(jié)點 ， 以及稱為該根的兩個互不相交的 左子樹 和 右子樹 構成 ， 同時這兩棵子樹亦是 二叉樹 。 ?性質(zhì) (2)：深度為 k的二叉樹至多有 2k1個節(jié)點（ k ≥ 1）。 特殊形態(tài)的二叉樹： 完全二叉樹和滿二叉樹。 特點：每一層上的節(jié)點數(shù)都達到了最大節(jié)點數(shù)。 滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。 性質(zhì) (5)：如果對一棵有 n個節(jié)點的完全二叉樹 （ 其深度為 ?log2n? +1） 的節(jié)點按層序編號 （ 從第 1層到第 ?log2n? +1層 ， 每層從左到右 ） ， 則對任一節(jié)點 i（ 1≤ i≤ n） ， 有： ① 如果 i = 1， 則節(jié)點 i是二叉樹的根 ， 無雙親；如果 i 1， 則其雙親 PARENT (i) 是節(jié)點 ?i/2? 。 ③ 如果 2i+1n，則節(jié)點 i無右孩子；否則其右孩子 RCHILD(i) 是節(jié)點 2i+1。 不足：一般的二叉樹也必須按完全二叉樹的形式來存儲，勢必會造成存儲的浪費。 中序遍歷：若二叉樹為空 ， 則空操作；否則 (1)中序遍歷左子樹； (2)訪問根節(jié)點； (3)中序遍歷右子樹 。 二叉樹遍歷的典型應用－－表達式樹 cba*cba*cba*cba*(a)a*(bc)的 表達式樹T ( b ) 先序遍歷表達式樹T ( c ) 中序遍歷表達式樹T ( d ) 后序遍歷表達式樹T圖6 . 7 表達式樹與三種遍歷 先序遍歷此二叉樹 ， 得到的二叉樹的先序序列為： *abc； 中序遍歷此二叉樹 ， 得到該二叉樹的中序序列為： a*bc； 后序遍歷此二叉樹，得到該二叉樹的后序序列為： abc*； 前綴表示（波蘭式） 后綴表示（逆波蘭式） 中綴表示（中綴式） 非遞歸實現(xiàn)樹的深度優(yōu)先遍歷 利用棧 非遞歸實現(xiàn)樹的廣度優(yōu)先遍歷 利用隊列 ?遍歷算法 時間 復雜度： O(N) ?遍歷算法 空間 復雜度：至多為 O(N) 樹和森林 ? 樹的存儲結構 三種典型的表示法： 第一種是 雙親表示法 。 第三種是孩子兄弟表示法 。 ① 若 F為空 ， 即 m=0， 則 B為空二叉樹； ② 若 F非空，即 m?0，則 B的根 root即為森林中第一棵樹的根 root(T1)； B的左子樹 lb是從T1中根節(jié)點的子樹森林 F1={T11,T12
教學課件相關推薦
鄂ICP備17016276號-1