最重要的非线性数据结构是什么

最重要的非线性数据结构是：树。树（Tree）可以用于表示层次关系或者具有树状结构的数据。树结构有很多种常见的变体，比如二叉树、AVL树、红黑树等等，它们都有其独特的优势和应用场景。

一、最重要的非线性数据结构是什么

最重要的非线性数据结构应该是树（Tree），因为它可以用于表示层次关系或者具有树状结构的数据。树结构有很多种常见的变体，比如二叉树、AVL树、红黑树等等，它们都有其独特的优势和应用场景。在计算机科学中，树结构被广泛应用于算法设计、数据库索引、编译器、操作系统等领域。

二、树（Tree）

1、概念

树（Tree）是n(n>=0)个结点的有限集。n=0时称为空树。

在任意一颗非空树中：

• 有且仅有一个特定的称为根（Root）的结点。
• 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、…..、Tm，其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）。

树的结点：树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（Degree）。树的度是树内各结点度的最大值。

结点的层次从根开始定义起，根为名列前茅层，根的孩子为第二层，以此类推。树的深度（Depth）或高度是树中结点的最大层次。

2、二叉树

二叉树（Binary Tree）是n(n>=0)个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成（子树也为二叉树）。

特点：

• 每个结点非常多有两棵子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

五种基本形态：

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点既有左子树又有右子树

性质：

• 在二叉树的第i层上至多有2^i-1个结点（i>=1）
• 深度为k的二叉树至多有2^k-1个结点（k>=1）
• 对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀ = n₂+1
• 具有n个结点的完全二叉树的深度为[log₂n ] + 1([X]表示不大于X的最大整数)

存储结构：

• 顺序存储：根据完全二叉树的特性，可以计算出任意节点n的双亲节点及左右孩子节点的序号，因此完全二叉树的节点可以按照从上到下从左到右的顺序依次存储到一维数组中。非完全二叉树存储时应先将其改造为完全二叉树，以空替代不存在的节点，比较浪费存储空间。
• 链式存储：树结构链式存储类似线性结构链式存储，先定义包含数据域和引用域的节点(Node)，然后通过引用域存储节点之间的关系。根据二叉树的结构来看，节点Node至少包含数据域(Data)，引用域(左孩子LChild、右孩子RChild)，为了方便通过孩子节点查找父节点，引用域中可以考虑添加父节点引用(Parent)。

3、树与二叉树的转换

树转二叉树：

• 加线：所有兄弟结点之间加一条连线。
• 抹线：对树中的每个结点，只保留他与名列前茅个孩子结点之间的连线，删除它与其它孩子结点之间的连线。
• 整理：整理前两步得到的树，使之结构层次分明。

二叉树转树：

• 加线：若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来。
• 抹线：删除原二叉树中所有结点与其右孩子结点的连线。
• 整理：整理前两步得到的树，使之结构层次分明。

4、树的遍历

/// <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：非线性数据结构有哪些

• 树（Tree）：树是一种非线性的数据结构，它包含一个根节点和若干个子节点，每个节点可能同时又是父节点和子节点。
• 图（Graph）：图是由若干节点和边组成的数据结构，节点之间的连接通过边来表示，节点之间的关系可以是单向的，也可以是双向的。
• 散列表（Hash table）：散列表是根据关键字直接进行访问的数据结构，通过计算一个关键字对应的散列值，可以在O(1)时间内获取关键字对应的值。