Hexo
0%

二叉树

Posted on Edited on In

前言:学习数据结构中的二叉树，很重要

树的定义

树:是具有n(n ≥ 0)个结点的有限集合T，n = 0时称为空树，否则:

  1. 有且只有一个特殊的称为树的根节点(ROOT)；
  2. 若n > 1时，其余的结点被分为m(m > 0)个互不相交的子集T1，T2，T3，……，Tm，其中每个子集Ti本身又是一棵树，称其为根的子树(Subtree)

树的基本术语

  1. 结点(node)：

    一个数据元素及其若干指向其子树的分支

  2. 结点的度(degree)、树的度:

    结点所拥有的子树的棵数称为结点的度

    树中结点度最大值称为树的度

    image-20240506101223509

  3. 叶子(left)结点、非叶子结点:

    树中度为0的结点称为叶子结点(或终端结点)

    相应的，度不为0的结点称为非叶子结点(或非终端结点、分支结点)

    ——除根结点外的分支结点称为内部结点

  4. 孩子结点、双亲结点、兄弟结点

    一个结点的子树的根称为该结点的孩子结点(child)/子结点

    相应的，该结点是其孩子结点的双亲结点(parent)或父结点

    同一双亲结点的所有子结点互称为兄弟结点

    image-20240506101743522

  5. 层次、堂兄弟结点

    规定:树中根结点的层次为1，其余结点的层次 = 其双亲结点的层次 + 1

    双亲结点在同意层上的所有结点互称为堂兄弟结点(兄弟结点是特殊的堂兄弟结点)

  6. 树的深度(depth)/树的高度(height)，结点的高度

    树中结点的最大层次值，称为树的深度，又称为树的高度

    树中的结点的高度为:以该结点为根的子树的高度

    ——根结点(A)的高度，即为整棵树的高度

    image-20240506102557255

  7. 结点的层次路径、祖先、子孙:

    从根结点开始，到达某结点X所经过的所有结点称为结点X的层次路径(有且只有一条)

    结点X的层次路径上的所有结点(X除外)称为X的祖先(ancestor)

    以某一结点为根的子树中的任意结点称为该结点的子孙结点(descent)

    image-20240506103141969

  8. 有序树和无序树:

    如果树T的每一个结点的子树(若有)具有一定的次序，则该子树称为有序树，否则称为无序树

    如果树中的结点的个子树看成从左到右是有次序的(即:不能互换)，则称为该树为有序树，否则为无序树

  9. 森林(forest):是m(m ≥ 0)棵互不相交的树的集合

    image-20240506103614399

二叉树(Binary Tree)

二叉树的定义

对于二叉树T来说，若n > 1时，其余的结点被分为两个互不相交的子集T1，T2，分别称为左、右子树、并且左右子树都是二叉树

二叉树的基本形态

image-20240506103900990

二叉树的性质

  1. 在非空二叉树中，第i层上至多有2^i-1^个结点(i ≥ 1)

  2. 深度为k的二叉树至多有2^k^-1个结点(k ≥ 1)

  3. 满&完全二叉树

    一棵深度为k且有2^k^-1个结点的二叉树称为”满二叉树”

    如果深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1到h的结点一一对应，该二叉树称为完全二叉树

    image-20240506104450820

  4. 对任何一棵非空二叉树，若其叶子结点数为n0，度为2的节点数为n2，则n0 = n2 + 1

    任一二叉树中，0度结点比2度结点多一个

  5. n个结点的完全二叉树深度为:n个结点的完全二叉树深度为:image-20240506105007195

    image-20240506105304086

  6. 对一棵有n个结点的完全二叉树(深度为log₂(n) + 1向下取整)，结点按层序(从第一层到第[log₂(n) + 1向下取整])自左至右进行编号，则对于编号为i(1 ≤ i ≤ n)的结点:

    • 若i = 1，则结点i是二叉树的根，无双亲结点；否则若i > 1，则其双亲结点编号是(i/2向下取整)
    • 若2i > n，则结点i为叶子结点，无左孩子；否则，其左孩子结点编号为2i
    • 若2i + 1 > n，则结点i无右孩子；否则，其右孩子结点编号是2i + 1

二叉树的存储结构

顺序存储结构——基于完全二叉树实现

用一组地址连续的存储单元依次”自上而下，自左向右”存储数据元素

顺序存储结构的类型定义

1
2
#define MAX_SIZE 100
typedef elemtype sqbitree[MAX_SIZE];

最坏情况下，一个深度为k且只有k个结点的单支树，需要长度为2^k^-1的一维数组

链式存储结构——基于2&3叉链表实现

image-20240506115150403

  • 二叉链表结点:

    有三个域:数据域，两个分别指向左右子结点的指针域；

    1
    2
    3
    4
    typedef struct btnode{
        ElemType data;
        struct btnode *Lchild,*Rchild;
    }BTNode;

  • 三叉链表结点:

    除二叉链表的三个域外，再增加一个指向父结点的指针域

    1
    2
    3
    4
    typedef struct btnode3{
        ElemType data;
        dtruct btnode3 *Lchild, *Rchild, *parent;
    }BTNode3;

二叉树的遍历及其应用

遍历二叉树(TBT):是指按指定的规律对二叉树中的每个结点”访问且有且访问一次”

若以L、D、R分别表示遍历左子树、根结点和右子树，则有六种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD

若规定先左后右，则只有三种情况：

image-20240507101529426

无论是哪种次序的遍历，其时间复杂度均为O(n)

先序遍历——递归实现

(1)：访问根节点

(2)：先序遍历左子树

(3)：先序遍历右子树

中序遍历——递归实现

(1)：中序遍历左子树

(2)：访问根结点

(3)：中序遍历右子树

后序遍历——递归实现

(1)：后序遍历左子树

(2)：后序遍历右子树

(3)：访问根结点

层(次)序遍历——队列实现

从根结点开始，按层次次序”自上下从左至右”

a)若二叉树T为空，则返回；否则，令p = T，入队

b)然后，循环执行一下过程，直到队空为止

  1. 队首元素p出队，并访问
  2. 将p结点的左右儿子一次入队

先序遍历——非递归实现

若二叉树T为空，则返回；否则，令p = T

  1. 访问p所指向的结点
  2. q = p ->Rchild，若q不为空，则q进栈
  3. p = p -> Lchild，若p不为空，，转(1.)；否则退栈到p，转(1.)
  4. 循环执行，直到栈为空为止

中序遍历——非递归实现

若二叉树T为空，则返回；否则，令p = T

  1. 循环：若p不为空，p进栈，且p = p -> Lchild；

    直到最左结点(p == null)，退栈到p，且访问p所指向的结点

  2. 进入右子树，(p = p -> Rchild)，后转1，即中序遍历p的右子树

  3. 循环执行直到栈空

后序遍历——非递归调用

在后序遍历中，根结点时最后访问的

  • 在遍历过程中，当搜索指针指向某一结点时，不能立即访问，而要先遍历其左子树，此时根结点进栈
  • 当其左子树遍历完后再搜索到该根节点时，还是不能访问，还需遍历其右子树
  • 所以，此根结点还需再次进栈，当其右子树遍历完后再退栈到该根结点时，才能被访问

因此，设立一个标志状态变量tag：

image-20240507105612381