王道數(shù)據(jù)結(jié)構(gòu)第八章課件XX有限公司20XX匯報人：XX目錄01樹的概念與性質(zhì)02二叉樹的定義與性質(zhì)03二叉樹的遍歷算法04二叉樹的存儲結(jié)構(gòu)05二叉搜索樹06平衡二叉樹樹的概念與性質(zhì)01樹的定義樹由節(jié)點和連接節(jié)點的邊組成，形成層次結(jié)構(gòu)。節(jié)點與邊樹中有一個特殊的節(jié)點稱為根，其他節(jié)點從根節(jié)點派生。根節(jié)點樹的術(shù)語樹的深度為根到葉子最長路徑長度。深度與層次根節(jié)點無前驅(qū)，葉子節(jié)點無后繼。根與葉子節(jié)點代表數(shù)據(jù)元素，邊表示節(jié)點間的關(guān)系。節(jié)點與邊樹的性質(zhì)層次性結(jié)構(gòu)樹具有明確的層次結(jié)構(gòu)，根節(jié)點在最上層，葉子節(jié)點在最下層。遞歸定義樹的定義具有遞歸性，子樹也是樹，體現(xiàn)了結(jié)構(gòu)的自相似性。二叉樹的定義與性質(zhì)02二叉樹的定義01節(jié)點構(gòu)成二叉樹由根節(jié)點及左右子樹構(gòu)成，左右子樹也分別為二叉樹。02節(jié)點關(guān)系每個節(jié)點最多有兩子節(jié)點，分別稱為左孩子和右孩子。二叉樹的性質(zhì)每個節(jié)點最多兩子節(jié)點關(guān)系01層次序遍歷唯一層次特性02節(jié)點全滿為滿二叉滿二叉樹03完全二叉樹與滿二叉樹01完全二叉樹節(jié)點按層序排列，除最后一層外節(jié)點均滿，且最后一層節(jié)點從左到右連續(xù)。02滿二叉樹除葉子節(jié)點外，每個節(jié)點都有兩個子節(jié)點，所有葉子節(jié)點在同一層。二叉樹的遍歷算法03前序遍歷先訪問根節(jié)點，再遍歷左子樹，最后遍歷右子樹。訪問根節(jié)點通過遞歸函數(shù)實現(xiàn)前序遍歷，先處理當(dāng)前節(jié)點，再遞歸處理左子樹和右子樹。遞歸實現(xiàn)中序遍歷右子樹遍歷最后遍歷右子樹節(jié)點左子樹遍歷先遍歷左子樹節(jié)點訪問根節(jié)點再訪問根節(jié)點后序遍歷左子樹-右子樹-根節(jié)點訪問順序0102用于表達式樹的求值和中綴表達式轉(zhuǎn)后綴表達式應(yīng)用場景03遞歸與非遞歸兩種方式實現(xiàn)后序遍歷實現(xiàn)方式二叉樹的存儲結(jié)構(gòu)04順序存儲結(jié)構(gòu)用數(shù)組按層次順序存儲二叉樹節(jié)點。數(shù)組存儲通過節(jié)點位置關(guān)系，快速計算數(shù)組中節(jié)點存儲地址。地址計算鏈?zhǔn)酱鎯Y(jié)構(gòu)指針域作用指針域指向左右孩子或父節(jié)點，靈活構(gòu)建二叉樹。節(jié)點結(jié)構(gòu)每個節(jié)點含數(shù)據(jù)域和指針域。0102存儲結(jié)構(gòu)的選擇數(shù)組存儲適用于完全二叉樹，空間利用率高。鏈表存儲靈活，適用于任意形態(tài)二叉樹，節(jié)省空間。二叉搜索樹05二叉搜索樹定義節(jié)點特性左小右大有序根節(jié)點意義根節(jié)點值居中分隔二叉搜索樹的性質(zhì)左子樹節(jié)點值小于根節(jié)點，右子樹節(jié)點值大于根節(jié)點。01左小右大所有節(jié)點值唯一，樹中無重復(fù)值。02無重復(fù)值中序遍歷二叉搜索樹，節(jié)點值按升序排列。03中序有序二叉搜索樹的操作插入操作刪除操作01在樹中合適位置插入新節(jié)點，保持二叉搜索樹性質(zhì)。02刪除節(jié)點并調(diào)整樹結(jié)構(gòu)，維持二叉搜索樹特性。平衡二叉樹06平衡二叉樹概念保持樹的高效性作用節(jié)點左子樹高-右子樹高平衡因子左右子樹高度差小定義與特點AVL樹的旋轉(zhuǎn)操作01單旋轉(zhuǎn)調(diào)整LL旋轉(zhuǎn)：左子樹過高，右旋調(diào)整。02雙旋轉(zhuǎn)調(diào)整LR旋轉(zhuǎn)：左子樹右孩子過高，先左旋后右旋。AVL樹的平衡化處理通過左旋或右旋調(diào)整節(jié)