這里寫目錄標題
- 樹
- 二叉樹的原理精講
- 二叉搜索樹插入節點
- 二叉搜索樹洗掉節點
- 二叉樹的遍歷
樹
- 樹狀圖是一種資料結構，它是由 n（n>=1）個有限結點組成一個具有層次關系的集合，把它叫做“樹”是因 為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的，
- 每個結點有零個或多個子結點；沒有父結點的結點稱為根結點；每一個非根結點有且只有一個父結點；除 了根結點外，每個子結點可以分為多個不相交的子樹；
二叉樹的原理精講
二叉樹是一個每個結點最多只能有兩個分支的樹，左邊的分支稱之為左子樹，右邊的分支稱之為右子樹.
二叉樹一般采用鏈式存盤方式：每個結點包含兩個指標域，指向兩個孩子結點，還包含一個資料域，存盤結點資訊，
- 完全二叉樹:若設二叉樹的高度為 h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層有葉 子節點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹（堆就是完全二叉樹），
- 滿二叉樹:除了葉結點外每一個結點都有左右子節點且葉子結點都處在最底層的二叉樹，
- 平衡二叉樹:又被稱為 AVL 樹，它是一顆空樹或左右兩個子樹的高度差的絕對值不超過 1，并且左右兩個子樹都 是一棵平衡二叉樹
- 二叉搜索樹:又稱二叉查找樹、二叉排序樹（Binary Sort Tree），它是一顆空樹或是滿足下列性質的二叉樹： (1）若左子樹不空，則左子樹上所有節點的值均小于或等于它的根節點的值；(2）若右子樹不空，則右子樹上所有節點的值均大于或等于它的根節點的值； (3）左、右子樹也分別為二叉排序樹，
- 紅黑樹:是每個節點都帶有顏色屬性（顏色為紅色或黑色）的自平衡二叉查找樹，滿足下列性質： (1）節點是紅色或黑色； (2）根節點是黑色； (3）所有葉子節點都是黑色； (4）每個紅色節點必須有兩個黑色的子節點，(從每個葉子到根的所有路徑上不能有兩個連續的紅色節 點，(5）從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點，
二叉搜索樹插入節點
將要插入的結點 e，與節點 root 節點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復以上 操作直到找到一個空位置用于放置該新節點，
二叉搜索樹洗掉節點
將要洗掉的節點的值，與節點 root 節點進行比較，若小于則去到左子樹進行比較，若大于則去到右子樹進行比較，重復以 上操作直到找到一個節點的值等于洗掉的值，則將此節點洗掉，洗掉時有 4 中情況須分別處理：
- 洗掉節點不存在左右子節點，即為葉子節點，直接洗掉
- 洗掉節點存在左子節點，不存在右子節點，直接把左子節點替代洗掉節點
- 洗掉節點存在右子節點，不存在左子節點，直接把右子節點替代洗掉節點
- 洗掉節點存在左右子節點，則取左子樹上的最大節點或右子樹上的最小節點替換洗掉節點，
二叉樹的遍歷
二叉樹的遍歷是指從根結點出發，按照某種次序依次訪問所有結點，使得每個結點被當且訪問一次，共分為四種方式：
- 前序遍歷 - 先訪問根節點，然后前序遍歷左子樹，再前序遍歷右子樹
- 中序遍歷 - 先訪問根節點的左子樹，然后訪問根節點，最后遍歷右子樹
- 后序遍歷 - 從左到右，先葉子后節點的方式遍歷訪問左右子樹，最后訪問根節點
- 層序遍歷 - 從根節點從上往下逐層遍歷，在同一層，按從左到右的順序對節點逐個訪問
前序遍歷示意圖:
中序遍歷示意圖:
后序遍歷示意圖:
層次遍歷示意圖:
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/277353.html
標籤：其他