C语言树的基础知识(必看篇)

什么是树

树是一种非线性数据结构，它由n个节点组成，这些节点通过边连接起来，形成一个分层结构。树的顶部节点称为根节点，没有子节点的节点称为叶子节点，其他节点则称为分支节点。

树的基本术语

节点(Node)

表示树中的元素，包含两个元素：数据和指向其子节点的指针。

边(Edge)

连接两个节点的线，表示节点之间的关系。

根节点(Root)

一棵树的顶端节点，它没有父节点，用来表示一棵树的开始。

叶子节点(Leaf)

没有子节点的节点，位于树的最底端。

分支节点(Branch)

至少有一个子节点的节点。

子节点(Child)

连接到一个父节点的节点。

父节点(Parent)

有至少一个子节点的节点。

层数（Level）

从根节点开始，一层一层向下并将相同的节点算作一层。根节点的层数为第一层，依次向下递增。

深度（Depth）

树中某个节点到根节点的路径长度。

树的常见类型

二叉树(Binary Tree)

每个节点最多有两个子节点的树，分别是左子节点和右子节点。

示例：

     1
   /   \
  2     3
 / \   / \
4   5 6   7

二叉查找树(Binary Search Tree)

一种特殊的二叉树，它的左子树中所有节点的值都小于根节点的值，右子树中所有节点的值都大于根节点的值。

示例：

     8
   /   \
  3     10
 / \      \
1   6     14
   / \    /
  4   7  13

平衡二叉树(AVL Tree)

一种二叉查找树，它的任意节点的左右子树的高度差不超过1。

示例：

      5
    /   \
   2     8
  / \   / \
 1   3 6  10
        / \
       9   11

红黑树(Red-Black Tree)

一种特殊的二叉查找树，它的每个节点要么是红色，要么是黑色。并且满足以下几个条件：

1. 根节点是黑色的。
2. 每个叶子节点都是黑色的空节点。
3. 不能有两个相邻的红色节点。
4. 从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

示例：

        11(黑)
      /       \
    7(红)     15(红)
   / \       /    \
  5(黑)  9(黑)  13(黑)  20(黑)

总结

本篇攻略是针对C语言中树的基础知识进行讲解，重点介绍了树的概念及基本术语、二叉树、二叉查找树、平衡二叉树、红黑树等常用树结构。了解树的基本概念及常见类型对于理解树结构的操作及应用十分重要。