树:与数组、链表、堆栈和队列(它们是线性数据结构)不同,树是分层数据结构。

术语

  • 节点的度:一个节点含有的子树的个数称为该节点的度
  • 树的度:一棵树中,最大的节点的度称为树的度
  • 叶节点或终端节点:度为零的节点
  • 非终端节点或分支节点:度不为零的节点
  • 父亲节点或父节点:若一个节点含有子节点,则这个节点称为其子节点的父节点
  • 孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点
  • 兄弟节点:具有相同父节点的节点互称为兄弟节点
  • 节点的层次:从根开始定义起,根为第1层,根的子节点为第2层,以此类推
  • 深度:对于任意节点n,n的深度为从根到n的唯一路径长,根的深度为0
  • 高度:对于任意节点n,n的高度为从n到一片树叶的最长路径长,所有树叶的高度为0
  • 堂兄弟节点:父节点在同一层的节点互为堂兄弟
  • 节点的祖先:从根到该节点所经分支上的所有节点
  • 子孙:以某节点为根的子树中任一节点都称为该节点的子孙
  • 森林:由m(m>=0)棵互不相交的树的集合称为森林

树的种类

  • 无序树:树中任意节点的子节点之间没有顺序关系,这种树称为无序树,也称为自由树
  • 有序树:树中任意节点的子节点之间有顺序关系,这种树称为有序树

树的作用

  • 存储自然形成层次结构的信息。例如,计算机上的文件系统
  • 树(有一些排序,例如BST)提供适度的访问/搜索(比链表快,比数组慢)
  • 树提供适当的插入/删除(比数组快,比无序链表慢)
  • 与链表和数组不同,树对节点的数量没有上限,因为节点是使用指针链接的
  • 路由算法
  • 多阶段决策的算法

最常用的就是二叉树

二叉树及性质

二叉树是最多有两个子节点的树

  • 树的根:指向树的最顶端节点以及树的一些其他信息
  • 树的节点

    1. 数据
    2. 指向左孩子的指针
    3. 指向右孩子的指针
  • 二叉树第 $i$ 层的最大节点数是: $2^{i-1}$
  • 高度为 $h$ 的二叉树最大节点数是: $2^{h} - 1$
  • $n$ 个节点的二叉树,最小高度是:$log_{2}(n + 1)$
  • 有 $l$ 个叶子节点的二叉树,至少有:$log_{2}l + 1$ 层
  • 在二叉树中,每个节点有0或2个子节点,叶节点的数目总是比有2个子节点的多一个。

二叉树的种类

  1. 满二叉树

    如果每个节点有0或2个子节点,那么二叉树就是满的。我们也可以说满二叉树中除了叶子以外的所有节点都有两个子节点。

             18
           /     \  
          15       30  
         /  \     /  \
       40   50  100   40
    
            18
          /    \   
        15     20    
       /  \       
     40  50   
      / \
    30  50
  2. 完整的二叉树

    所有的层都被完全填满,除了最后一层,最后一层有尽可能多的键

            18
          /     \  
         15      30  
        /  \     /  \
      40    50 100   40
    
    
            18
          /     \  
        15       30  
       /  \      /  \
      40    50  100   40
     /  \   /
     8   7  9
  3. 完美二叉树

    所有内部节点都有两个子节点,所有的叶子都在同一层

            18
          /     \  
         15      30  
        /  \     /  \
       40    50 100  40
    
    
          18
        /    \  
      15      30  
  4. 平衡二叉树

如果二叉树的高度是$ O(log_{2} n) $, 其中n是节点数,则二叉树是平衡的

平衡二叉搜索树的性能很好,因为它们提供了 $ O(log_{2} n) $ 时间进行搜索、插入和删除

  • AVL树通过确保左子树和右子树的高度差为 1 来保持 $ O(log_{2} n) $ 高度
  • 红黑树确保每个根到叶路径上的黑节点数量相同,并且没有相邻的红节点来保持 $ O(log_{2} n) $ 的高度

5.病态树

每个内部节点都有一个子节点的树。这些树与链表在性能方面是相同的。

10
/
20
\
30
\
40     
文章目录