數據結構之樹學習筆記
一.樹中的節點關係和一些概念
1.基本概念
樹中節點數可以使用n來表示
空樹：n為0的樹
節點的度：指節點的子節點數目，如上圖中B節點為一度，D節點為三度
父子兄弟關係：如上圖中D是G的父節點，H是D的子節點，G是H的兄弟節點，I是J的堂兄弟節點（這個概念不重要）
樹的層次：還是如上圖，A節點為第一層，B、C節點為第二層，D、E、F節點為第三層，G、H、I、J節點為第四層
樹的深度：還是上圖中，總共有四個層次的節點，稱樹的深度為4
樹中的一些注意事項：1）一個子節點只能有一個父節點，但是一個父節點的子節點數目沒有限制
2）子樹之間不能相交
3）樹只能有一個根節點
2.樹的存儲
樹可以採用鏈式存儲，可以採用以下的一些方式存儲：
1）在節點中記錄父節點的位置，即父節點存儲法。這個方式可以很方便找到父節點甚至父節點的父節點，但是尋找子節點時卻需要遍歷查找；
2）在節點中記錄所有子節點的位置，即子節點存儲法。這個方式同樣方便找子節點，但是尋找父節點同樣需要遍歷；
3）在節點中記錄第一個子節點和其他兄弟節點的位置，即孩子兄弟存儲法。這個方法找子節點和兄弟節點很方便，但是找父節點同樣要遍歷。
二.二叉樹
二叉樹中每個節點的子節點最多只能有兩個，稱為左右子節點，左右子節點下方的樹稱為左右子樹。
1.一些特殊的二叉樹
左斜樹：所有節點只有左子節點的樹。
右斜樹：所有節點只有右子節點的樹。
滿二叉樹：對於一個k層的二叉樹，k-1層的節點都有兩個子節點，第k層的節點都有0個子節點，這樣的二叉樹稱為滿二叉樹。
完全二叉樹：對一個有k層的滿二叉樹，第k層的節點有2k-1個，如果將這些節點從右向左連續刪除0-2k-1個後就得到一個完全二叉樹。滿二叉樹是特殊的完全二叉樹。下圖分別是4層的滿樹從右向左連續刪除6個節點和3個節點得到的兩個完全二叉樹。
2.二叉樹的存儲
對一個k層的滿二叉樹，每一層的節點數分別是20、21、......、2k-1，總節點數是2k-1。如下圖，將這個滿二叉樹的所有節點一層一層從左到右編號，可以發現一個有趣的現象：每個節點的父節點編號都是這個節點編號除以2的商，每個節點的子節點編號都是這個節點編號乘以2的積（左子節點）或者乘以2加1的和（右子節點）。
根據這個特性可以使用順序的方式存儲二叉樹，給每個節點編號，每個節點的子節點和父節點都可以通過編號運算得到。對於非完全二叉樹，編號時將空缺的位置一同編號即可。下面是三個非完全二叉樹的編號方式：
因此二叉樹的存儲可以使用數組進行順序存儲，空缺的節點置為空即可。同時也由於空缺的節點都置為空，因此像右斜樹等不完全二叉樹會造成嚴重的空間浪費，因此鏈表存儲的方式也可以採用。
3.二叉樹的遍歷
1）前序遍歷：從根節點開始，先輸出當前節點的數據，再依次遍歷輸出左節點和右節點。
2）中序遍歷：從根節點開始，先輸出當前左節點的數據，再輸出當前節點的數據，最後輸出當前的右節點的數據。
3）後序遍歷：從根節點開始，先輸出當前節點左節點的數據，再輸出當前節點右節點的數據，最後輸出當前節點的數據。
4）層序遍歷：從樹的第一層開始，從上到下逐層遍歷，每一層從左到右依次輸出。
4.二叉樹的程式碼實現（C#），這裡使用順序存儲實現了二叉樹的數值添加和幾種遍歷，沒有實現刪除的方法。
class BiTree<T> { private T[] data; private int count = 0; //當前二叉樹存儲的數據量 public BiTree(int capacity) //當前二叉樹的數據容量 { data = new T[capacity]; } /// <summary> /// 向二叉樹中添加數據或者修改二叉樹中的數據 /// </summary> /// <param name="item"></param>需要存儲的數據 /// <param name="index"></param>需要存儲的數據的編號 /// <returns></returns> public bool Add(T item,int index) { //校驗二叉樹是否存滿 if (count >= data.Length) return false; data[index - 1] = item; count++; return true; } public void Traversal() { FirstTravalsal(1); Console.WriteLine(); MiddleTravalsal(1); Console.WriteLine(); LastTravalsal(1); Console.WriteLine(); LayerTravalsal(); } /// <summary> /// 前序遍歷 /// </summary> /// <param name="index"></param>遍歷的數據的編號 private void FirstTravalsal(int index) { //校驗編號是否存在 if (index > data.Length) return; //校驗數據是否存在，當前位置沒有數據則存儲為-1 if (data[index - 1].Equals(-1)) return; //輸出當前數據 Console.Write(data[index - 1] + " "); //計算左右子節點的下標 int leftNumber = index * 2; int rightNumber = index * 2 + 1; //遞歸遍歷左右子節點 FirstTravalsal(leftNumber); FirstTravalsal(rightNumber); } /// <summary> /// 中序遍歷 /// </summary> /// <param name="index"></param>遍歷的數據的編號 private void MiddleTravalsal(int index) { //校驗編號是否存在 if (index > data.Length) return; //校驗數據是否存在，當前位置沒有數據則存儲為-1 if (data[index - 1].Equals(-1)) return; //計算左右子節點的下標 int leftNumber = index * 2; int rightNumber = index * 2 + 1; //遞歸遍歷左子節點 FirstTravalsal(leftNumber); //輸出當前數據 Console.Write(data[index - 1] + " "); //遞歸遍歷右子節點 FirstTravalsal(rightNumber); } /// <summary> /// 後序遍歷 /// </summary> /// <param name="index"></param>遍歷的數據的編號 private void LastTravalsal(int index) { //校驗編號是否存在 if (index > data.Length) return; //校驗數據是否存在，當前位置沒有數據則存儲為-1 if (data[index - 1].Equals(-1)) return; //計算左右子節點的下標 int leftNumber = index * 2; int rightNumber = index * 2 + 1; //遞歸遍歷左子節點 FirstTravalsal(leftNumber); //遞歸遍歷右子節點 FirstTravalsal(rightNumber); //輸出當前數據 Console.Write(data[index - 1] + " "); } /// <summary> /// 層序遍歷 /// </summary> private void LayerTravalsal() { for(int i = 0;i < data.Length;i++) { //校驗當前數據是否為空 if (data[i].Equals(-1)) continue; //輸出遍歷的數據 Console.Write(data[i] + " "); } } }
三.二叉排序樹
二叉排序樹的節點位置和節點的大小有關，從根節點開始判斷，比當前節點小就往當前節點的左子樹上移動，反之往當前節點的右子樹上移動，一直判斷直到移動到的位置沒有節點，這個位置就是節點的放置位置。如下圖所示，連接線上的數字是節點的放置順序：
可以看到，同樣的數據，最後存儲出來的二叉樹形狀和數據的放置順序有關。
下面是二叉排序樹的實現（C#），這裡使用鏈表實現了二叉排序樹的節點添、查找和刪除。
class BSNode { public BSNode LeftChild{get;set;} public BSNode RightChild { get; set; } public BSNode Parent { get; set; } public int Data { get; set; } public BSNode() { } public BSNode(int item) { this.Data = item; } }
class BSTree { //記錄根節點位置 public BSNode Root { get; set; } /// <summary> /// 添加數據 /// </summary> /// <param name="item"></param>要添加的數據，以int為例，也可以拓展為一個泛型 public void AddNode(int item) { //新建一個node BSNode newNode = new BSNode(item); //判斷樹中有沒有節點，沒有節點當前節點作為根節點，有節點將數據放入節點中 if (Root == null) Root = newNode; else { //定義一個臨時節點記錄當前正在訪問的節點位置 BSNode temp = Root; //死循環，需要不斷判斷節點應該往當前節點左邊還是右邊放置，且不知道要循環判斷多少次 while (true) { //如果要放置的數據大於當前節點，說明要放置的節點應該往右邊放 if(item >= temp.Data) { //判斷當前節點的右邊子節點位置是否已經有節點，如果沒有直接放置然後跳出循環 if (temp.RightChild == null) { temp.RightChild = newNode; newNode.Parent = temp; break; } //當前節點右節點位置有數據的情況下，將臨時節點置為當前節點的右節點，繼續循環判斷應該往這個節點的哪一邊放置 else { temp = temp.RightChild; } } //如果要放置的數據不是大於當前節點，說明要放置的節點應該往左邊放 else { if (temp.LeftChild == null) { temp.LeftChild = newNode; newNode.Parent = temp; break; } else { temp = temp.LeftChild; } } } } } /// <summary> /// 採用中序遍歷可以實現數據由小到大輸出 /// </summary> /// <param name="node"></param>遍歷輸出node節點及其子節點 public void MiddleTraversal(BSNode node) { if (node == null) return; MiddleTraversal(node.LeftChild); Console.Write(node.Data + " "); MiddleTraversal(node.RightChild); } /// <summary> /// 查找數據是否在樹中（遞歸方式） /// </summary> /// <param name="item"></param>要查找的數據 /// <param name="node"></param>在node節點及其子孫節點中查找 /// <returns></returns> public bool Find1(int item,BSNode node) { //校驗當前節點是否為空 if (node == null) return false; //判斷節點的數據是否和要查找的數據相同 else if (item == node.Data) return true; //判斷要查找的數據和當前數據的大小，決定是繼續在左子樹中查找還是在右子樹中查找 else if (item > node.Data) return Find1(item, node.RightChild); else return Find1(item, node.LeftChild); } /// <summary> /// 查找數據是否在樹中（循環方式） /// </summary> /// <param name="item"></param>要查找的數據 /// <param name="node"></param>在node節點及其子孫節點中查找 /// <returns></returns> public bool Find2(int item, BSNode node) { BSNode temp = node; while (true) { //校驗當前節點是否為空 if (temp == null) return false; //判斷節點的數據是否和要查找的數據相同 else if (item == temp.Data) return true; //判斷要查找的數據和當前數據的大小，決定是繼續在左子樹中查找還是在右子樹中查找 else if (item > temp.Data) temp = temp.RightChild; else temp = temp.LeftChild; } } /// <summary> /// 根據數據查找並刪除存儲數據的節點 /// </summary> /// <param name="item"></param>要刪除的數據 /// <returns></returns> public bool DeleteNode(int item) { //首先需要查找要刪除的節點是否存在，使用臨時節點temp記錄，如果存在才能刪除，否則不能刪除 BSNode temp = Root; while (true) { //校驗當前節點是否為空 if (temp == null) return false; //判斷節點的數據是否和要查找的數據相同，相同就需要刪除這個節點 else if (item == temp.Data) { DeleteNode(temp); return true; } //判斷要查找的數據和當前數據的大小，決定是繼續在左子樹中查找還是在右子樹中查找 else if (item > temp.Data) temp = temp.RightChild; else temp = temp.LeftChild; } } /// <summary> /// 刪除指定的節點 /// </summary> /// <param name="node"></param>要刪除的節點 private void DeleteNode(BSNode node) { //判斷當前節點是否為根節點，不是根節點刪除時需要修改當前節點的父節點的引用指向，是根節點需要修改Root的值 if (node.Parent != null) { //分為四種情況，分別是這個節點沒有子節點、只用左子節點、只有右子節點和有左右兩個子節點 //沒有子節點直接修改父節點的引用，並刪除節點 if (node.LeftChild == null && node.RightChild == null) { if (node.Parent.RightChild == node) node.Parent.RightChild = null; else node.Parent.LeftChild = null; node = null; } //只有左子節點或者右子節點需要更改父節點的引用，並更改相應子節點的父節點引用 else if (node.LeftChild == null && node.RightChild != null) { if (node.Parent.RightChild == node) node.Parent.RightChild = node.RightChild; else node.Parent.LeftChild = node.RightChild; node.RightChild.Parent = node.Parent; node = null; } else if (node.LeftChild != null && node.RightChild == null) { if (node.Parent.RightChild == node) node.Parent.RightChild = node.LeftChild; else node.Parent.LeftChild = node.LeftChild; node.LeftChild.Parent = node.Parent; node = null; } //左右子節點都有的情況下將右子樹的最小值的數據複製到當前節點，然後去刪除右子樹的最小值 else { BSNode temp = node.RightChild; while (true) { if (temp.LeftChild != null) temp = temp.LeftChild; else break; } node.Data = temp.Data; DeleteNode(temp); } } //當前節點是根節點的情況下和不是根節點的刪除類似，也是四種情況，不過需要修改的是Root的引用和子節點的父節點引用，不用管父節點 else { if (node.LeftChild == null && node.RightChild == null) { node = null; Root = null; } else if (node.LeftChild == null && node.RightChild != null) { node.RightChild.Parent = null; Root = node.RightChild; node = null; } else if (node.LeftChild != null && node.RightChild == null) { node.LeftChild.Parent = null; Root = node.LeftChild; node = null; } else { BSNode temp = node.RightChild; while (true) { if (temp.LeftChild != null) temp = temp.LeftChild; else break; } node.Data = temp.Data; DeleteNode(temp); } } } }
