? ? ? ? 事先聲明,本文不適合對數據結構完全不懂的小白 請至少學會鏈表再閱讀

????????c# 數據結構 鏈表篇 有關單鏈表的一切_c# 鏈表-CSDN博客

數據結構理論先導:《數據結構（C 語言描述）》也許是全站最良心最通俗易懂最好看的數據結構課（最遲每周五更新~~）_嗶哩嗶哩_bilibili

代碼隨想錄:

關于二叉樹，你該了解這些！| 二叉樹理論基礎一網打盡，二叉樹的種類、二叉樹的存儲方式、二叉樹節點定義、二叉樹的遍歷順序_嗶哩嗶哩_bilibili

????????

目錄

0.樹基礎概念

1.二叉樹基礎概念 BT B:Binary?

?編輯

2.普通二叉樹存儲/遍歷/缺點

?存儲方式

順序存儲:

?鏈式存儲:

遍歷方式

順序存儲遍歷(遞歸)

鏈式存儲遍歷(遞歸)

插入方式及其缺點

? ? ? ? 鏈式存儲插入

? ? ? ? 缺點

3.二叉搜索樹 BST S:Search

? ? ? ? 鏈式構建及其增刪查改

? ? ? ? 測試用例以及全部代碼

4.平衡二叉樹(AVL) BBT:? ?B:Balanced

? ? ? ? 構建和插入

? ? ? ? 刪除

5.二叉樹的線索化? ? ?

5.1設計線索化結構

5.2 線索化構建樹?

5.3 線索化后中序遍歷方法舉例

? ?關于紅黑樹和b+樹 下一篇數據結構 樹篇 將會做出徹底詳解?

---

0.樹基礎概念

????????0和1是基礎概念和一些性質 可以看個大概 知道有這么回事就行了 后面用到再回來想想是不是這么回事即可?

?葉子節點也算是子樹?

樹的性質

?解釋:

結點的度 = 該節點下最大子樹個數,也就是看有幾個孩子

比如:A結點 有三個子樹 即為三個孩子 ,B有兩個孩子,K無孩子

解釋:?

還是這棵樹 i =1開始?

樹的度 = 最大結點的度,也就是有最多孩子的結點的度

還是上面這棵樹 最多孩子的度為A||D 所以 m = 3

第一層就是3的0次方 =1

第二層就是3的1次方 =3

第三層就是3的二次方 =9 (最大值)

1.二叉樹基礎概念 BT B:Binary?

?解釋:

對于這個性質的解釋:

?

2.普通二叉樹存儲/遍歷/缺點

?存儲方式

順序存儲:

????????順序存儲需要注意的是讓索引 i 從0

????????

? ? ? ? 特點是:依據其索引的特點 通過線性結構存儲起來

????????我用的是List(i=0開始)

public class Tree<T> : MonoBehaviour
{private List<T> bitTree = new List<T>();public void AddTree(T[] values){for(int i = 0; i < values.Length; i++){bitTree.Add(values[i]);}}
}

     Tree<char> tree = new Tree<char>();char[] values = { 'A', 'B', 'C', 'D' };tree.AddTree(values);

?鏈式存儲:

特點為 =左右孩子指針 + 數據存儲位

//節點暫時定義為char
public class TreeNode {public char Date;public TreeNode LeftNode;public TreeNode RightNode;public TreeNode(char Date, TreeNode LeftNode=null, TreeNode RightNode=null) {this.Date = Date;this.LeftNode =LeftNode;this.RightNode = RightNode;}

遍歷方式

有三種分為前中后序

?前序特點：

就是先當前節點（如果從根節點開始），再左節點再右節點

中序特點：

先左，再當前，最后右

后序特點：

先左，再右，最后當前

順序存儲遍歷(遞歸)

以前序為例 先構造樹

再做遞歸

    //順序遍歷二叉樹//前序public void Preorder(int index){if (index >= bitTree.Count)return;Debug.Log(bitTree[index]);int LeftNode = 2*index+1;int  RightNode = 2*index+2;Preorder(LeftNode);Preorder(RightNode);}//中序public void MiddleOrder(int index){if (index >= bitTree.Count)return;int LeftNode = 2 * index + 1;int RightNode = 2 * index + 2;MiddleOrder(LeftNode);Debug.Log(bitTree[index]);MiddleOrder(RightNode);}//后序public void AfterOrder(int index) {if (index >= bitTree.Count)return;int LeftNode = 2 * index + 1;int RightNode = 2 * index + 2;AfterOrder(LeftNode);AfterOrder(RightNode);Debug.Log(bitTree[index]);}

鏈式存儲遍歷(遞歸)

還是以前序遍歷為例:

TreeNode rootNode = new TreeNode('A',new TreeNode('B',new TreeNode('D'), new TreeNode('E')),new TreeNode('C', new TreeNode('F')));rootNode.FirstRoot(rootNode);
Console.WriteLine();rootNode.MiddleRoot(rootNode);
Console.WriteLine();rootNode.AfterRoot(rootNode);
//節點暫時定義為char
public class TreeNode {public char Date;public TreeNode LeftNode;public TreeNode RightNode;public TreeNode(char Date, TreeNode LeftNode=null, TreeNode RightNode=null) {this.Date = Date;this.LeftNode =LeftNode;this.RightNode = RightNode;}//遍歷方法 前public void FirstRoot(TreeNode treeNode){if (treeNode == null) return;Console.Write(treeNode.Date);FirstRoot(treeNode.LeftNode);FirstRoot(treeNode.RightNode);}//遍歷方法 中public void MiddleRoot(TreeNode treeNode){if (treeNode == null) return;Console.Write(treeNode.Date);MiddleRoot(treeNode.LeftNode);MiddleRoot(treeNode.RightNode);}  //遍歷方法 后public void AfterRoot(TreeNode treeNode){if (treeNode == null) return;AfterRoot(treeNode.LeftNode);AfterRoot(treeNode.RightNode);Console.Write(treeNode.Date);}
}

插入方式及其缺點

? ? ? ? 鏈式存儲插入

? ? ? ? 我想給原來的二叉樹的 2 6之間插入一個4

TreeNode root = new TreeNode(1);
root.LeftNode = new TreeNode(2);
root.RightNode = new TreeNode(3);
root.LeftNode.LeftNode = new TreeNode(6);
root.LeftNode.RightNode = new TreeNode(7);//節點暫時定義為char
public class TreeNode
{public int Date;public TreeNode LeftNode;public TreeNode RightNode;public TreeNode(int Date, TreeNode LeftNode = null, TreeNode RightNode = null){this.Date = Date;this.LeftNode = LeftNode;this.RightNode = RightNode;} 

我需要做的

// 創建新節點
TreeNode newNode = new TreeNode(4);// 在節點 2 的左子節點位置插入新節點 4
BinaryTree.InsertNode(root.LeftNode, true, newNode);

 public class BinaryTree{/// <summary>/// 值插入/// </summary>/// <param name="parent"></param>/// <param name="isLeft">是否是左子節點</param>/// <param name="newNode"></param>public static void InsertNode(TreeNode parent, bool isLeft, TreeNode newNode){if (isLeft){newNode.LeftNode = parent.LeftNode;parent.LeftNode = newNode;}else{newNode.RightNode = parent.RightNode;parent.RightNode = newNode;}}}

? ? ? ? 缺點

????????發現了沒有和他娘的鏈表似的:?

????????無法利用 “值的順序” 進行高效操作??

????????比如搜索某個值（如查找?4）時，只能從根節點開始遍歷整個樹（如廣度優先或深度優先搜索），時間復雜度為?O(n)，和鏈表無異

?????????插入邏輯不通用：插入節點?4?到節點?2?的左子節點，依賴于手動指定父子關系，沒有統一的規則,如果樹結構復雜，插入位置的選擇會非常隨意，導致樹的高度不平衡（如退化成鏈表）

? ? ? ? 于是有了下面這個玩意 二叉搜索樹

3.二叉搜索樹 BST S:Search

????????數據結構合集 - 二叉搜索樹(二叉排序樹)(二叉查找樹)_嗶哩嗶哩_bilibili

? ? ? ? 特點 左子樹Data小于根Data?? 右子樹Data 大于根Data

操作	最好時間復雜度	最壞時間復雜度
查找（Search）	O(log n)	O(n)
插入（Insert）	O(log n)	O(n)
刪除（Delete）	O(log n)	O(n)
空間復雜度	O(n)	{O (n)（存儲所有節點，與樹的形態無關）}

? ? ? ? 存儲方式還是有鏈式和順序 我傾向于鏈式 因為比較簡單和清晰 所以拿此舉例

? ? ? ? 鏈式構建及其增刪查改

? ? ? ? ? ? 構建

public class TreeNode { public int value; public TreeNode Left; public TreeNode Right;public TreeNode(int value, TreeNode left = null, TreeNode right = null) {this.value = value;this.Left = left;this.Right = right;}
}public class BinarySearchTree
{public TreeNode root;public BinarySearchTree(){root = null;}

? ? ? ? 增加?

    //增加節點public void Insert(int value) { InsertTrueMethod(root, value);}/// <summary>/// 遞歸查找插入位置/// </summary>/// <param name="node">插入的節點</param>/// <param name="val">插入的值</param>private TreeNode InsertTrueMethod(TreeNode node, int value){if (node == null){return new TreeNode(value);}//如果插入值 小于 節點值，則在左子樹中插入if (value < node.value){node.Left = InsertTrueMethod(node.Left, value);}//如果插入值 大于 節點值，則在右子樹中插入else if (value > node.value){node.Right = InsertTrueMethod(node.Right, value);}//如果找到了相同的值，則不插入return node;}

? ? ? ? 刪除

    private TreeNode DeleteTrueMethod(TreeNode node, int value){//如果樹為空，則直接返回空if (node == null){return null;}//如果刪除值 小于 節點值，則在左子樹找if (value < node.value){node.Left = DeleteTrueMethod(node.Left, value);}//如果刪除值 大于 節點值，則在右子樹else if (value > node.value){node.Right = DeleteTrueMethod(node.Right, value);}//如果找到了相同的值，則刪除該節點else{//如果該節點沒有子節點，則直接刪除該節點if (node.Left == null && node.Right == null){node = null;}//如果該節點只有一個子節點，則直接用該節點的子節點替換該節點else if (node.Left == null){node = node.Right;}else if (node.Right == null){node = node.Left;}// 如果該節點有兩個子節點，此時有兩種常見的替換策略：// 可以選擇該節點右子樹中的最小節點，也可以選擇左子樹中的最大節點。// 這里我們采用選擇右子樹中最小節點的策略。選擇右子樹最小節點（或者左子樹最大節點）的目的是// 為了保證替換后仍然滿足二叉搜索樹的性質：左子樹所有節點值小于根節點值，右子樹所有節點值大于根節點值。// 步驟為：先找到右子樹的最小節點，用其值替換當前要刪除節點的值，// 然后再遞歸地從右子樹中刪除這個最小節點。else{TreeNode minNode = GetMinNode(node.Right);node.value = minNode.value;node.Right = DeleteTrueMethod(node.Right, minNode.value);}}return node;}//獲取節點方法private TreeNode GetMinNode(TreeNode node){while (node.Left != null){node = node.Left;}return node;}

? ? ? ? 測試用例以及全部代碼

? ? ? ? 注釋進行了簡單的修改

using System;
BinarySearchTree bst = new BinarySearchTree();// 測試用例 1：刪除葉子節點
int[] values1 = { 50, 30, 20, 40, 70, 60, 80 };
foreach (var val in values1) bst.Insert(val);
//Console.WriteLine("刪除前（用例1）:");
//bst.InOrderTraversal(bst.root); // 輸出：20 30 40 50 60 70 80 
//bst.Delete(20);
//Console.WriteLine("刪除后（用例1-葉子節點）:");
//bst.InOrderTraversal(bst.root); // 預期：30 40 50 60 70 80 測試用例 2：刪除單子節點
//BinarySearchTree bst2 = new BinarySearchTree();
//int[] values2 = { 50, 30, 40 };
//foreach (var val in values2) bst2.Insert(val);
//bst2.Delete(30);
//Console.WriteLine("刪除后（用例2-單子節點）:");
//bst2.InOrderTraversal(bst2.root); // 預期：40 50 測試用例 3：刪除雙子節點
BinarySearchTree bst3 = new BinarySearchTree();
int[] values3 = { 50, 30, 20, 40, 70, 60, 80 };
foreach (var val in values3) bst3.Insert(val);
bst3.Delete(50);
Console.WriteLine("刪除后（用例3-雙子節點）:");
bst3.InOrderTraversal(bst3.root); // 預期：20 30 40 60 70 80 
public class TreeNode
{public int value;public TreeNode Left;public TreeNode Right;public TreeNode(int value, TreeNode left = null, TreeNode right = null){this.value = value;this.Left = left;this.Right = right;}
}public class BinarySearchTree
{public TreeNode root;public BinarySearchTree(){root = null;}// 增加節點public void Insert(int value){root = InsertTrueMethod(root, value); }private TreeNode InsertTrueMethod(TreeNode node, int value){if (node == null)return new TreeNode(value);if (value < node.value)node.Left = InsertTrueMethod(node.Left, value);else if (value > node.value)node.Right = InsertTrueMethod(node.Right, value);return node;}public void Delete(int value){root = DeleteTrueMethod(root, value);}private TreeNode DeleteTrueMethod(TreeNode node, int value){//先找到待刪除節點if (node == null) return null;if (value < node.value)node.Left = DeleteTrueMethod(node.Left, value);else if (value > node.value)node.Right = DeleteTrueMethod(node.Right, value);else {//找到以后分為三種情況//1. 葉子節點if (node.Left == null && node.Right == null)node = null;//2. 單子節點else if (node.Left == null)node = node.Right;else if (node.Right == null)node = node.Left;else{//3. 雙子節點 找到右子樹最小節點(或者左子樹最大節點 替換待刪除節點 然后遞歸刪除右子樹最小節點, 或者左子樹最大節點)TreeNode minNode = GetRightMinNode(node.Right);node.value = minNode.value;node.Right = DeleteTrueMethod(node.Right, minNode.value);}}return node;}private TreeNode GetRightMinNode(TreeNode node){while (node.Left != null) node = node.Left;return node;}public void InOrderTraversal(TreeNode node){if (node == null) return;InOrderTraversal(node.Left);Console.Write(node.value + " "); InOrderTraversal(node.Right);if (node == root) Console.WriteLine(); }
}

? ? ? ? 但是還是有一個問題 如果數據本來就有序 那構建二叉搜索樹會成為一條線

?????????

? ? ? ? 所以為了解決這個問題 有了下面這個平衡二叉樹

4.平衡二叉樹(AVL) BBT:? ?B:Balanced

? ? ? ? 建議直接看視頻?平衡二叉樹(AVL樹)_嗶哩嗶哩_bilibili

? ? ? ? 這個東西是比較抽象的 而且情況也比較多 下圖來自 b站 @帕拉迪克

????????平衡因子:Balanced Factor

? ? ? ? 上代碼

? ? ? ? 構建和插入

using System;//測試結果
AVLTree tree = new AVLTree();
int[] values = { 5,3,4};foreach (int value in values) {tree.Insert(value);
}tree.InOrderTraversal(tree.root);
// 定義 AVL 樹節點類
public class TreeNode
{public int Value;       public TreeNode Left;     public TreeNode Right;    public int Height;        public TreeNode(int value){Value = value;Height = 1; // 新節點初始高度為1}
}public class AVLTree
{public TreeNode root;//獲取傳入節點的高度 private int GetHight(TreeNode node) { return node == null? 0 : node.Height;}//計算平衡因子 讓傳入節點的左子樹 - 右子樹高度 private int ComputeBalanceFactor(TreeNode node) { if(node == null ) return 0;int BalanceFactor = GetHight(node.Left) - GetHight(node.Right);return BalanceFactor;}//右旋 右旋父節點,然后將沖突的右放在旋轉后的父節點的左子樹private TreeNode RightRotate(TreeNode father) { //找到左子樹節點和新插入節點TreeNode leftChild = father.Left;TreeNode conflict = leftChild.Right;//旋轉leftChild.Right =  father; //原父節點弄到左子樹的右邊father.Left = conflict; //沖突的弄到原父節點的左邊//更新高度 先更新一下原來的父節點的高度 再更新一下現在的父節點的高度father.Height = Math.Max(GetHight(father.Left), GetHight(father.Right)) + 1;leftChild.Height = Math.Max(GetHight(leftChild.Left), GetHight(leftChild.Right)) + 1;//返回旋轉后的父節點return leftChild;}//左旋 左旋父節點,然后將沖突的左放在旋轉后的父節點的右子樹private TreeNode LeftRotate(TreeNode father){//找到右子樹節點和新插入節點TreeNode rightChild = father.Right;TreeNode conflict = rightChild.Left;//旋轉rightChild.Left = father; //原父節點弄到右子樹的左邊father.Right = conflict; //沖突的弄到原父節點的右邊//更新高度 先更新一下原來的父節點的高度 再更新一下現在的父節點的高度father.Height = Math.Max(GetHight(father.Left), GetHight(father.Right)) + 1;rightChild.Height = Math.Max(GetHight(rightChild.Left), GetHight(rightChild.Right)) + 1;//返回旋轉后的父節點return rightChild;}public void Insert(int value){root = InsertTrueMethod(root, value);}private TreeNode InsertTrueMethod(TreeNode root, int value){//BST插入 空創建 左右遞歸插入 重復值不插入if (root == null)return new TreeNode(value);if (value < root.Value)root.Left = InsertTrueMethod(root.Left, value); //遞歸+更新+平衡else if (value > root.Value)root.Right = InsertTrueMethod(root.Right, value);//遞歸+更新+平衡else return root;//更新高度root.Height = Math.Max(GetHight(root.Left), GetHight(root.Right)) + 1;//計算平衡因子int balanceFactor = ComputeBalanceFactor(root);//根據平衡因子判斷怎么轉//LL型 右旋  value < root.Left.Value:驗證新節點確實插入在左子樹的左側if (balanceFactor > 1 && value < root.Left.Value)return RightRotate(root);//RR型 左旋if (balanceFactor < -1 && value > root.Right.Value)return LeftRotate(root);//LR型 先左旋再右旋if (balanceFactor > 1 && value > root.Left.Value){root.Left = LeftRotate(root.Left);return RightRotate(root);}//RL型 先右旋再左旋if (balanceFactor < -1 && value < root.Right.Value){root.Right = RightRotate(root.Right);return LeftRotate(root);}//不用旋返回根節點return root;}//中序遍歷public void InOrderTraversal(TreeNode root){if (root == null)return;InOrderTraversal(root.Left);Console.WriteLine(root.Value);InOrderTraversal(root.Right);}
}

? ? ? ? 刪除

    // 刪除指定值的節點public void Delete(int value){root = DeleteNode(root, value);}private TreeNode DeleteNode(TreeNode root, int value){// 如果根節點為空，直接返回 nullif (root == null)return root;// 如果要刪除的值小于當前節點的值，遞歸刪除左子樹中的節點if (value < root.Value)root.Left = DeleteNode(root.Left, value);// 如果要刪除的值大于當前節點的值，遞歸刪除右子樹中的節點else if (value > root.Value)root.Right = DeleteNode(root.Right, value);// 找到要刪除的節點else{// 情況 1: 節點沒有子節點或只有一個子節點if (root.Left == null || root.Right == null){TreeNode temp = root.Left ?? root.Right;// 如果沒有子節點，直接刪除該節點if (temp == null){root = null;}else{// 用子節點替換當前節點root = temp;}}// 情況 2: 節點有兩個子節點else{// 找到右子樹中的最小節點TreeNode temp = MinValueNode(root.Right);// 用最小節點的值替換當前節點的值root.Value = temp.Value;// 遞歸刪除右子樹中的最小節點root.Right = DeleteNode(root.Right, temp.Value);}}// 如果刪除后樹為空，直接返回 nullif (root == null)return root;// 更新節點高度root.Height = Math.Max(GetHight(root.Left), GetHight(root.Right)) + 1;// 計算平衡因子int balanceFactor = ComputeBalanceFactor(root);// LL 型失衡，進行右旋操作if (balanceFactor > 1 && ComputeBalanceFactor(root.Left) >= 0)return RightRotate(root);// LR 型失衡，先對左子樹進行左旋，再對根節點進行右旋if (balanceFactor > 1 && ComputeBalanceFactor(root.Left) < 0){root.Left = LeftRotate(root.Left);return RightRotate(root);}// RR 型失衡，進行左旋操作if (balanceFactor < -1 && ComputeBalanceFactor(root.Right) <= 0)return LeftRotate(root);// RL 型失衡，先對右子樹進行右旋，再對根節點進行左旋if (balanceFactor < -1 && ComputeBalanceFactor(root.Right) > 0){root.Right = RightRotate(root.Right);return LeftRotate(root);}return root;}// 找到以給定節點為根的子樹中的最小節點private TreeNode MinValueNode(TreeNode node){TreeNode current = node;// 不斷向左遍歷，直到找到最左邊的節點while (current.Left != null)current = current.Left;return current;}

????????看起來有點難度實際上熟悉以后你會發現其編寫都是套路 多讀幾遍就好了

? ? ? ? 遞歸遞歸遞歸,你會發現二叉樹一直在做這個動作 那么有沒有一種方式脫離它呢?

????????有的兄弟 有的 :線索化二叉樹

5.二叉樹的線索化? ? ?

????????線索化二叉樹的設計思想是：

????????將空的指針（Left?或?Right）利用起來，不再指向子樹（因為子樹為空），而是指向該節點在中序遍歷中的前驅或后繼節點

????????這樣做可以在后續遍歷中，不依賴遞歸或棧，直接通過線索找到前后節點

? ? ? ? 畫圖,邏輯思想

? ? ? ? 下為代碼解釋

5.1設計線索化結構

????????其中LeftIsThread 和?RightIsThread 是指當前Left和Right是否為空

public class ThreadedNode<T>
{public T Data { get; set; }public ThreadedNode<T> Left { get; set; }public ThreadedNode<T> Right { get; set; }// 標志位：false表示指向子節點，true表示線索public bool LeftIsThread { get; set; }public bool RightIsThread { get; set; }public ThreadedNode(T data){this.Data = data;this.Left = null;this.Right = null;this.LeftIsThread = false;this.RightIsThread = false;}
}

5.2 線索化構建樹?

public class ThreadedBinaryTree<T>
{private ThreadedNode<T> _root;private ThreadedNode<T> _pre; // 記錄前驅節點// 線索化核心邏輯（中序）private void ThreadNodes(ThreadedNode<T> node){if (node == null) return;// 遞歸線索化左子樹ThreadNodes(node.Left);// 處理當前節點的前驅if (node.Left == null){node.Left = _pre;node.LeftIsThread = true; // 標記為線索}// 處理前驅節點的后繼if (_pre != null && _pre.Right == null){_pre.Right = node;_pre.RightIsThread = true;}_pre = node; // 更新前驅// 遞歸線索化右子樹ThreadNodes(node.Right);}public void BuildThreadedTree(ThreadedNode<T> root){_root = root;_pre = null;ThreadNodes(root);}}

5.3 線索化后中序遍歷方法舉例

// 中序遍歷（利用線索）public void InOrderTraversal(){ThreadedNode<T> current = _root;while (current != null){// 找到最左節點while (!current.LeftIsThread){current = current.Left;}Console.Write(current.Data + " ");// 根據后繼線索遍歷while (current.RightIsThread){current = current.Right;Console.Write(current.Data + " ");}current = current.Right;}

? ?關于紅黑樹和b+樹 下一篇數據結構 樹篇 將會做出徹底詳解?