万丈高楼平地起,【万丈高楼平地起 第三季 C#实现二叉树操作】

本文接上一篇【万丈高楼平地起 第二季 队列和栈】继续说明如何用C#语言实现二叉树的操作。
四、树 链表、堆栈和队列都是线性结构(即序列)。树是一种特殊的非线性二维数据机构。树节点包含两个或两个以上的链接。工作中主要应用的二叉树——每个节点都有两个链接（其中可有一个或两个链接为null）。根节点是树的第一个节点。左孩子（left child）是左子树的第一个节点，右孩子（right child ）是右子树的第一个节点。属于相同节点的子节点成为兄弟节点（siblings）。没有子节点的节点成为叶子节点。计算机科学家常常用根节点在上、叶子节点的方式画出一棵树——同树的自然生长方向恰好相反。

特殊二叉树——二叉查找树 二叉查找树（没有重复的节点值）的特征是：左子树中任何值都小于父节点的值，右子树中任何值都大于父节点的值。

构建二叉树、前序、中序、后序遍历二叉树 BinaryTreeLibrary.cs
View Code 1 using System; 2 3 namespace BinaryTreeLibrary 4 { 5 ///

6 /// 定义TreeNode类 7 ///

8 class TreeNode 9 { 10 private TreeNode leftNode; 11 private int data; 12 private TreeNode rightNode; 13 14 ///

15 /// 初始化数据，构造一个叶子节点 16 ///

17 ///
18 public TreeNode(int nodeData) 19 { 20 data = nodeData; 21 leftNode = rightNode = null; 22 } 23 24 ///

25 /// 左节点 26 ///

27 public TreeNode LeftNode 28 { 29 get 30 { 31 return leftNode; 32 } 33 set 34 { 35 leftNode = value; 36 } 37 } 38 39 ///

40 /// Data数据节点 41 ///

42 public int Data 43 { 44 get 45 { 46 return data; 47 } 48 set 49 { 50 data = value; 51 } 52 } 53 54 public TreeNode RightNode 55 { 56 get 57 { 58 return rightNode; 59 } 60 set 61 { 62 rightNode = value; 63 } 64 } 65 66 ///

67 /// 在包含节点的二叉树中插入TreeNode 68 ///

69 ///
70 public void Insert(int insertValue) 71 { 72 // 在左子树中插入数据 73 if (insertValue < data) 74 { 75 // 如果没有左子树就构建一个叶子节点 76 if (leftNode == null) 77 { 78 leftNode = new TreeNode(insertValue); 79 } 80 else 81 { 82 // 遍历左子树 83 leftNode.Insert(insertValue); 84 } 85 } 86 // 在右子树中插入数据 87 else if (insertValue > data) 88 { 89 // 如果没有右子树就构建一个叶子节点 90 if (rightNode == null) 91 { 92 rightNode = new TreeNode(insertValue); 93 } 94 else 95 { 96 // 遍历右子树 97 rightNode.Insert(insertValue); 98 } 99 } 100 }// end insert method 101 102 }// end class TreeNode 103 104 ///

105 /// 类Tree定义 106 ///

107 public class Tree 108 { 109 // 整个类操作的是 TreeNode 类的对象 110 private TreeNode root; 111 112 ///

113 /// 构建一颗空树 114 ///

115 public Tree() 116 { 117 root = null; 118 } 119 120 ///

121 /// 将新节点插入到二叉树 122 /// 如果根节点是空的，就创建根节点 123 /// 否则，调用insert方法 124 ///

125 ///
126 public void InsertNode(int insertValue) 127 { 128 lock (this) 129 { 130 if (root == null) 131 { 132 root = new TreeNode(insertValue); 133 } 134 else 135 { 136 root.Insert(insertValue); 137 } 138 } 139 } 140 141 ///

142 /// 前序遍历 143 ///

144 public void PreorderTraverse() 145 { 146 lock (this) 147 { 148 PreorderHelper(root); 149 } 150 } 151 152 153 ///

154 /// 递归进行前序遍历 155 ///

156 ///
157 private void PreorderHelper(TreeNode node) 158 { 159 if (node == null) 160 { 161 return; 162 } 163 164 // 输出 节点 数据 165 Console.Write(node.Data + " "); 166 167 // 遍历左子树 168 PreorderHelper(node.LeftNode); 169 170 // 遍历右子树 171 PreorderHelper(node.RightNode); 172 } 173 174 ///

175 /// 中序遍历 176 ///

177 public void InorderTravese() 178 { 179 lock (this) 180 { 181 InorderHelper(root); 182 } 183 } 184 185 ///

186 /// 递归进行中序遍历 187 ///

188 ///
189 private void InorderHelper(TreeNode node) 190 { 191 if (node == null) 192 { 193 return; 194 } 195 196 // 先 遍历左子树 197 InorderHelper(node.LeftNode); 198 199 // 输出 数据 节点 200 Console.Write(node.Data + " "); 201 202 // 后 遍历右子树 203 InorderHelper(node.RightNode); 204 205 } 206 207 ///

208 /// 后序遍历 209 ///

210 public void PostorderTravese() 211 { 212 lock (this) 213 { 214 PostorderHelper(root); 215 } 216 } 217 218 ///

219 /// 递归进行后序遍历 220 ///

221 ///
222 private void PostorderHelper(TreeNode node) 223 { 224 if (node == null) 225 { 226 return; 227 } 228 229 // 先 遍历左子树 230 PostorderHelper(node.LeftNode); 231 232 // 再 遍历右子树 233 PostorderHelper(node.RightNode); 234 235 // 输出 数据 节点 236 Console.Write(node.Data + " "); 237 } 238 }// end class Tree 239 }

Tree类操作TreeNode类的对象。Tree类有一个私有数据成员——root，这是对根节点的引用。
为保证线程的安全性，Tree类的InsertNode方法首先锁定Tree对象，然后再进行后序是否为空、插入节点等操作。 方法PreorderTraverse()、InorderTraverse()和PostorderTraverse()分别调用辅助方法PreorderHelper、InorderHelper和PostorderHelper方法。
测试代码，Program.cs
using System; using BinaryTreeLibrary; namespace TreeTest { class Program { static void Main(string[] args) { Tree tree = new Tree(); int insertValue; Console.WriteLine("Inserting values: "); Random random = new Random(); for (int i = 0; i <= 10; i++) { insertValue = random.Next(100); Console.Write(insertValue + " "); tree.InsertNode(insertValue); } // 前序遍历 Console.Write("\n\n 前序遍历："); tree.PreorderTraverse(); // 中序遍历 Console.Write("\n\n 中序遍历："); tree.InorderTravese(); // 后序遍历 Console.Write("\n\n 后序遍历："); tree.PostorderTravese(); Console.ReadKey(); } } }

至此，二叉查找树测试完毕！

延伸阅读