最重要的非线性数据结构是:树。树(Tree)可以用于表示层次关系或者具有树状结构的数据。树结构有很多种常见的变体,比如二叉树、AVL树、红黑树等等,它们都有其独特的优势和应用场景。
最重要的非线性数据结构应该是树(Tree),因为它可以用于表示层次关系或者具有树状结构的数据。树结构有很多种常见的变体,比如二叉树、AVL树、红黑树等等,它们都有其独特的优势和应用场景。在计算机科学中,树结构被广泛应用于算法设计、数据库索引、编译器、操作系统等领域。
树(Tree)是n(n>=0)个结点的有限集。n=0时称为空树。
在任意一颗非空树中:
树的结点:树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。树的度是树内各结点度的最大值。
结点的层次从根开始定义起,根为名列前茅层,根的孩子为第二层,以此类推。树的深度(Depth)或高度是树中结点的最大层次。
二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成(子树也为二叉树)。
特点:
五种基本形态:
性质:
存储结构:
树转二叉树:
二叉树转树:
/// <summary>
/// 先序遍历(DLR)
/// </summary>
/// <![CDATA[首先访问跟节点,然后遍历左子树,最后右子树]]>
static void PreOrder(Node<char> root)
{
if (root == null)
{
return;
}
Print(root);
PreOrder(root.LChild);
PreOrder(root.RChild);
}
/// <summary>
/// 中序遍历(LDR)
/// </summary>
/// <![CDATA[先遍历左子树,然后根节点,最后遍历右子树]]>
static void InOrder(Node<char> root)
{
if (root == null)
{
return;
}
InOrder(root.LChild);
Print(root);
InOrder(root.RChild);
}
/// <summary>
/// 后序遍历(LRD)
/// </summary>
/// <![CDATA[先遍历左子树,然后遍历右子树,最后遍历根节点]]>
static void PostOrder(Node<char> root)
{
if (root == null)
{
return;
}
PostOrder(root.LChild);
PostOrder(root.RChild);
Print(root);
}
/// <summary>
/// 层序遍历
/// </summary>
/// <![CDATA[从上向下从左到右]]>
static void LevelOrder(Node<char> root)
{
if (root == null)
{
return;
}
CSeqQueue<Node<char>> sq = new CSeqQueue<Node<char>>(50);
sq.In(root);
while (!sq.IsEmpty())
{
Node<char> tmp = sq.Out();
Print(tmp);
if (tmp.LChild != null)
{
sq.In(tmp.LChild);
}
if (tmp.RChild != null)
{
sq.In(tmp.RChild);
}
}
}
延伸阅读1:非线性数据结构有哪些
版权声明:本文内容由网络用户投稿,版权归原作者所有,本站不拥有其著作权,亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容,请联系邮箱:hopper@cornerstone365.cn 处理,核实后本网站将在24小时内删除。