C#数据结构-二叉树-链式存储结构

对比上一篇文章“顺序存储二叉树”，链式存储二叉树的优点是节省空间。

二叉树的性质：

1、在二叉树的第i层上至多有2^i-1个节点(i>=1)。

2、深度为k的二叉树至多有2^k-1个节点(k>=1)。

3、对任何一棵二叉树T，如果其终结点数为n₀,度为2的节点数为n₂,则n₀=n₂+1。

4、具有n个节点的完全二叉树的深度为log₂n+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 && 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 是叶子节点