对比上一篇文章“顺序存储二叉树”，链式存储二叉树的优点是节省空间。
二叉树的性质：
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。
在此记录下链式二叉树的实现方式 ：
/// /// 树节点 /// /// public class TreeNode { /// /// 节点数据 /// public T data { get; set; } /// /// 左节点 /// public TreeNode leftChild { get; set; } /// /// 右节点 /// public TreeNode rightChild { get; set; } public TreeNode() { data = default(T); leftChild = null; rightChild = null; } public TreeNode(T item) { data = item; leftChild = null; rightChild = null; } }
/// /// 二叉树 链表存储结构/// /// public class LinkStorageBinaryTree{/// /// 树根节/// private TreeNode head { get; set; }public LinkStorageBinaryTree(){head = null;}public LinkStorageBinaryTree(T val){head = new TreeNode(val);}/// /// 获取左节点/// ///
/// public TreeNode GetLeftNode(TreeNode treeNode){if (treeNode == null)return null;return treeNode.leftChild;}/// /// 获取右节点/// ///
/// public TreeNode GetRightNode(TreeNode treeNode){if (treeNode == null)return null;return treeNode.rightChild;}/// /// 获取根节点/// /// public TreeNode GetRoot(){return head;}/// /// 插入左节点/// ///
///
/// public TreeNode AddLeftNode(T val,TreeNode node){if (node == null)throw new ArgumentNullException("参数错误");TreeNode treeNode = new TreeNode(val);TreeNode childNode = node.leftChild;treeNode.leftChild = childNode;node.leftChild = treeNode;return treeNode;}/// /// 插入右节点/// ///
///
/// public TreeNode AddRightNode(T val, TreeNode node){if (node == null)throw new ArgumentNullException("参数错误");TreeNode treeNode = new TreeNode(val);TreeNode childNode = node.rightChild;treeNode.rightChild = childNode;node.rightChild = treeNode;return treeNode;}/// /// 删除当前节点的 左节点/// ///
/// public TreeNode DeleteLeftNode(TreeNode node){if (node == null || node.leftChild == null)throw new ArgumentNullException("参数错误");TreeNode leftChild = node.leftChild;node.leftChild = null;return leftChild;}/// /// 删除当前节点的 右节点/// ///
/// public TreeNode DeleteRightNode(TreeNode node){if (node == null || node.leftChild == null)throw new ArgumentNullException("参数错误");TreeNode rightChild = node.rightChild;node.rightChild = null;return rightChild;}/// /// 先序遍历/// ///
public void PreorderTraversal(TreeNode node){//递归的终止条件if (head == null){Console.WriteLine("当前树为空");return;}if (node != null){Console.Write(node.data+ " ");PreorderTraversal(node.leftChild);PreorderTraversal(node.rightChild);}}/// /// 中序遍历/// ///
public void MiddlePrefaceTraversal(TreeNode node){//递归的终止条件if (head == null){Console.WriteLine("当前树为空");return;}if (node != null){MiddlePrefaceTraversal(node.leftChild);Console.Write(node.data + " ");MiddlePrefaceTraversal(node.rightChild);}}/// /// 后序遍历/// ///
public void AfterwordTraversal(TreeNode 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> queue = new Queue>();queue.Enqueue(head);while (queue.Any()){TreeNode item = queue.Dequeue();Console.Write(item.data +" ");if (item.leftChild != null)queue.Enqueue(item.leftChild);if (item.rightChild != null)queue.Enqueue(item.rightChild);}}/// /// 校验节点是否是叶子节点/// ///
/// public bool ValidLeafNode(TreeNode node){if (node == null)throw new ArgumentNullException("参数错误");if (node.leftChild != null return false;}Console.WriteLine($"节点 {node.data} 是叶子节点");return true;}}
遍历方式在顺序存储一文中已经用图表示过，在此不做重复说明。
现在测试下：
LinkStorageBinaryTree linkStorageBinary = new LinkStorageBinaryTree("A");TreeNode tree1 = linkStorageBinary.AddLeftNode("B", linkStorageBinary.GetRoot());TreeNode tree2 = linkStorageBinary.AddRightNode("C", linkStorageBinary.GetRoot());TreeNode 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 是叶子节点
