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

概述对比上一篇文章“顺序存储二叉树”，链式存储二叉树的优点是节省空间。 二叉树的性质： 1、在二叉树的第i层上至多有2i-1个节点(i>=1)。 2、深度为k的二叉树至多有2k-1个节点(k>

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

 

二叉树的性质：

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。

 

在此记录下链式二叉树的实现方式 ：

/// <summary>    /// 树节点    </summary>    <typeparam name="T"></typeparam>    public class TreeNode<T>    {        <summary>         节点数据        </summary>        public T data { get; set; }         左节点        public TreeNode<T> leftChild {  右节点        public TreeNode<T> rightChild { ; }        public TreeNode()        {            data = default(T);            leftChild = null;            rightChild = ;        }         TreeNode(T item)        {            data = item;            leftChild = ;        }    }

     二叉树 链表存储结构    class linkStorageBinaryTree<T> 树根节        private TreeNode<T> head {  linkStorageBinaryTree()        {            head =  linkStorageBinaryTree(T val)        {            head = new TreeNode<T>(val);        }         获取左节点        </summary>        <param name="treeNode"></param>        <returns></returns>        public TreeNode<T> GetleftNode(TreeNode<T> treeNode)        {            if (treeNode == )                return ;            return treeNode.leftChild;        }         获取右节点        public TreeNode<T> GetRightNode(TreeNode<T> treeNode.rightChild;        }         获取根节点        public TreeNode<T> GetRoot()        {             head;        }         插入左节点        <param name="val"></param>        <param name="node"></param>        public TreeNode<T> AddleftNode(T val,TreeNode<T> node)        {            if (node == throw new ArgumentNullException("参数错误");            TreeNode<T> treeNode = (val);            TreeNode<T> childNode = node.leftChild;            treeNode.leftChild = childNode;            node.leftChild = treeNode;             treeNode;        }         插入右节点        public TreeNode<T> AddRightNode(T val,1)"> node.rightChild;            treeNode.rightChild = childNode;            node.rightChild = treeNode;        }         删除当前节点的 左节点        public TreeNode<T> DeleteleftNode(TreeNode<T>null || node.leftChild == );            TreeNode<T> leftChild = node.leftChild;            node.leftChild =  leftChild;        }         删除当前节点的 右节点        public TreeNode<T> DeleteRightNode(TreeNode<T>);            TreeNode<T> rightChild = node.rightChild;            node.rightChild =  rightChild;        }         先序遍历        <param name="index"></param>        voID PreorderTraversal(TreeNode<T>//递归的终止条件            if (head == )            {                Console.Writeline(当前树为空);                ;            }            if (node != )            {                Console.Write(node.data+ " );                PreorderTraversal(node.leftChild);                PreorderTraversal(node.rightChild);            }        }         中序遍历        voID MIDdlePrefaceTraversal(TreeNode<T>)            {                MIDdlePrefaceTraversal(node.leftChild);                Console.Write(node.data + );                MIDdlePrefaceTraversal(node.rightChild);            }        }         后序遍历        voID AfterwordTraversal(TreeNode<T>)            {                AfterwordTraversal(node.leftChild);                AfterwordTraversal(node.rightChild);                Console.Write(node.data + );            }        }        voID LevelTraversal()        {            使用队列先入先出            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 != )                    queue.Enqueue(item.leftChild);                if (item.rightChild != )                    queue.Enqueue(item.rightChild);            }        }         校验节点是否是叶子节点        bool ValIDLeafNode(TreeNode<T>);            if (node.leftChild != null && node.rightChild != )            {                Console.Writeline($节点 {node.data} 不是叶子节点false;            }            Console.Writeline($节点 {node.data} 是叶子节点true;        }    }

遍历方式在顺序存储一文中已经用图表示过，在此不做重复说明。

现在测试下：

linkStorageBinaryTree<string> linkStorageBinary = new linkStorageBinaryTree<string>(A);TreeNode<string> tree1 = linkStorageBinary.AddleftNode(B,linkStorageBinary.GetRoot());TreeNode<string> tree2 = linkStorageBinary.AddRightNode(Cstring> tree3 =linkStorageBinary.AddleftNode(DEFG先序遍历Console.Write(先序遍历：);linkStorageBinary.PreorderTraversal(linkStorageBinary.GetRoot());Console.Writeline();中序遍历Console.Write(中序遍历：);linkStorageBinary.MIDdlePrefaceTraversal(linkStorageBinary.GetRoot());Console.Writeline();后序遍历：);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 是叶子节点

 

总结

以上是内存溢出为你收集整理的C#数据结构-二叉树-链式存储结构全部内容，希望文章能够帮你解决C#数据结构-二叉树-链式存储结构所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。