C#數據結構-二叉樹-鏈式存儲結構
對比上一篇文章「順序存儲二叉樹」，鏈式存儲二叉樹的優點是節省空間。
二叉樹的性質：
1、在二叉樹的第i層上至多有2i-1個節點(i>=1)。
2、深度為k的二叉樹至多有2k-1個節點(k>=1)。
3、對任何一棵二叉樹T，如果其終結點數為n0,度為2的節點數為n2,則n0=n2+1。
4、具有n個節點的完全二叉樹的深度為log2n+1。
5、對於一棵有n個節點的完全二叉樹的節點按層序編號，若完全二叉樹中的某節點編號為i，則若有左孩子編號為2i，若有右孩子編號為2i+1，母親節點為i/2。
在此記錄下鏈式二叉樹的實現方式 ：
/// <summary> /// 樹節點 /// </summary> /// <typeparam name="T"></typeparam> public class TreeNode<T> { /// <summary> /// 節點數據 /// </summary> public T data { get; set; } /// <summary> /// 左節點 /// </summary> public TreeNode<T> leftChild { get; set; } /// <summary> /// 右節點 /// </summary> public TreeNode<T> rightChild { get; set; } public TreeNode() { data = default(T); leftChild = null; rightChild = null; } public TreeNode(T item) { data = item; leftChild = null; rightChild = null; } }
/// <summary> /// 二叉樹 鏈表存儲結構 /// </summary> /// <typeparam name="T"></typeparam> public class LinkStorageBinaryTree<T> { /// <summary> /// 樹根節 /// </summary> private TreeNode<T> head { get; set; } public LinkStorageBinaryTree() { head = null; } public LinkStorageBinaryTree(T val) { head = new TreeNode<T>(val); } /// <summary> /// 獲取左節點 /// </summary> /// <param name="treeNode"></param> /// <returns></returns> public TreeNode<T> GetLeftNode(TreeNode<T> treeNode) { if (treeNode == null) return null; return treeNode.leftChild; } /// <summary> /// 獲取右節點 /// </summary> /// <param name="treeNode"></param> /// <returns></returns> public TreeNode<T> GetRightNode(TreeNode<T> treeNode) { if (treeNode == null) return null; return treeNode.rightChild; } /// <summary> /// 獲取根節點 /// </summary> /// <returns></returns> public TreeNode<T> GetRoot() { return head; } /// <summary> /// 插入左節點 /// </summary> /// <param name="val"></param> /// <param name="node"></param> /// <returns></returns> public TreeNode<T> AddLeftNode(T val,TreeNode<T> node) { if (node == null) throw new ArgumentNullException("參數錯誤"); TreeNode<T> treeNode = new TreeNode<T>(val); TreeNode<T> childNode = node.leftChild; treeNode.leftChild = childNode; node.leftChild = treeNode; return treeNode; } /// <summary> /// 插入右節點 /// </summary> /// <param name="val"></param> /// <param name="node"></param> /// <returns></returns> public TreeNode<T> AddRightNode(T val, TreeNode<T> node) { if (node == null) throw new ArgumentNullException("參數錯誤"); TreeNode<T> treeNode = new TreeNode<T>(val); TreeNode<T> childNode = node.rightChild; treeNode.rightChild = childNode; node.rightChild = treeNode; return treeNode; } /// <summary> /// 刪除當前節點的 左節點 /// </summary> /// <param name="node"></param> /// <returns></returns> public TreeNode<T> DeleteLeftNode(TreeNode<T> node) { if (node == null || node.leftChild == null) throw new ArgumentNullException("參數錯誤"); TreeNode<T> leftChild = node.leftChild; node.leftChild = null; return leftChild; } /// <summary> /// 刪除當前節點的 右節點 /// </summary> /// <param name="node"></param> /// <returns></returns> public TreeNode<T> DeleteRightNode(TreeNode<T> node) { if (node == null || node.leftChild == null) throw new ArgumentNullException("參數錯誤"); TreeNode<T> rightChild = node.rightChild; node.rightChild = null; return rightChild; } /// <summary> /// 先序遍歷 /// </summary> /// <param name="index"></param> public void PreorderTraversal(TreeNode<T> node) { //遞歸的終止條件 if (head == null) { Console.WriteLine("當前樹為空"); return; } if (node != null) { Console.Write(node.data+ " "); PreorderTraversal(node.leftChild); PreorderTraversal(node.rightChild); } } /// <summary> /// 中序遍歷 /// </summary> /// <param name="index"></param> public void MiddlePrefaceTraversal(TreeNode<T> node) { //遞歸的終止條件 if (head == null) { Console.WriteLine("當前樹為空"); return; } if (node != null) { MiddlePrefaceTraversal(node.leftChild); Console.Write(node.data + " "); MiddlePrefaceTraversal(node.rightChild); } } /// <summary> /// 後序遍歷 /// </summary> /// <param name="index"></param> public void AfterwordTraversal(TreeNode<T> node) { //遞歸的終止條件 if (head == null) { Console.WriteLine("當前樹為空"); return; } if (node != null) { AfterwordTraversal(node.leftChild); AfterwordTraversal(node.rightChild); Console.Write(node.data + " "); } } public void LevelTraversal() { if (head == null) return; //使用隊列先入先出 Queue<TreeNode<T>> queue = new Queue<TreeNode<T>>(); queue.Enqueue(head); while (queue.Any()) { TreeNode<T> item = queue.Dequeue(); Console.Write(item.data +" "); if (item.leftChild != null) queue.Enqueue(item.leftChild); if (item.rightChild != null) queue.Enqueue(item.rightChild); } } /// <summary> /// 校驗節點是否是葉子節點 /// </summary> /// <param name="node"></param> /// <returns></returns> public bool ValidLeafNode(TreeNode<T> node) { if (node == null) throw new ArgumentNullException("參數錯誤"); if (node.leftChild != null && node.rightChild != null) { Console.WriteLine($"節點 {node.data} 不是葉子節點"); return false; } Console.WriteLine($"節點 {node.data} 是葉子節點"); return true; } }
遍歷方式在順序存儲一文中已經用圖表示過，在此不做重複說明。
現在測試下：
LinkStorageBinaryTree<string> linkStorageBinary = new LinkStorageBinaryTree<string>("A"); TreeNode<string> tree1 = linkStorageBinary.AddLeftNode("B", linkStorageBinary.GetRoot()); TreeNode<string> tree2 = linkStorageBinary.AddRightNode("C", linkStorageBinary.GetRoot()); TreeNode<string> tree3 =linkStorageBinary.AddLeftNode("D", tree1); linkStorageBinary.AddRightNode("E",tree1); linkStorageBinary.AddLeftNode("F", tree2); linkStorageBinary.AddRightNode("G", tree2); //先序遍歷 Console.Write("先序遍歷："); linkStorageBinary.PreorderTraversal(linkStorageBinary.GetRoot()); Console.WriteLine(); //中序遍歷 Console.Write("中序遍歷："); linkStorageBinary.MiddlePrefaceTraversal(linkStorageBinary.GetRoot()); Console.WriteLine(); //中序遍歷 Console.Write("後序遍歷："); linkStorageBinary.AfterwordTraversal(linkStorageBinary.GetRoot()); Console.WriteLine(); //層次遍歷 Console.Write("層次遍歷："); linkStorageBinary.LevelTraversal(); linkStorageBinary.ValidLeafNode(tree1); linkStorageBinary.ValidLeafNode(tree3); Console.ReadKey();
輸出：
先序遍歷：A B D E C F G
中序遍歷：D B E A F C G
後序遍歷：D E B F G C A
層次遍歷：A B C D E F G 節點 B 不是葉子節點
節點 D 是葉子節點
