跳到主要内容

树与二叉树

Start from ‎2024‎年‎4‎月‎10‎日，‏‎8:12:01

树的基本概念​

祖先、子孙、双亲、孩子、兄弟、堂兄弟​

  1. 祖先：头上的全部。比如说K的，EBA全是他祖先
  2. 子孙：地下的全部。比如说B的，EFKL全是子孙
  3. 双亲：头上那一个，根没有双去哪
  4. 兄弟：仅限同一个双亲的隔壁，比如说F的兄弟就是E
  5. 堂兄弟：那一层的都是

结点的度和树的度​

  1. 结点的度：全部度的总和
  2. 树的度：结点的最大的度

结点的深度、高度和层次​

深度从下往上数，高度从上往下数（可以从1/0开始数）

有序树和无序树​

路径和路径长度​

森林​

由m个互不相交的树的集合组成。

树的性质​

结点数=总度数+1 （n=m+1）​

每个结点都有个天线，除了根没有，补个1就是总结点数

度=m的树第i层最多有$m^{i-1} $个结点​

1->m->m2m^2

m0m^0->m2−1m^{2-1}->mi−1m^{i-1}

最多结点数mi−1m−1\frac{m^i-1}{m-1}​

用等比数列来推，

SUM=a1(1−qn)1−qSUM=\frac{a_1(1-q^n)}{1-q}

a1=1，q=m，在上下同*-1即可得到

SUM=mi−1m−1SUM=\frac{m^i-1}{m-1}

最少结点数​

[log[n(m−1)+1]]向上取整[log[n(m-1)+1]]向上取整

度=m，结点数=n，最小高度也是一样的（类似于h=n）

度=m，结点数=n，最大高度 h=n-m+1​

n-m是把最后一层m个节点减掉，然后加上1就是高度

总结点数两个公式​

N=N0+N1+⋯+NnN=N_0+N_1+\cdots+N_n
N=1+N1+2N2+⋯+mNmN=1+N_1+2N_2+\cdots+ mN_m

第二个公式可以理解为度数为m的节点引出m个分支，好比是天线，但是根节点没有天线所以+1

延伸​

总结点数=总分支数+1总结点数=总分支数+1

总度数=总分支数​

会用到的=>

二叉树

与度=2的有序树区别​

  1. 度=2的树至少3个结点，但是二叉树可以为空
  2. 度=2的左右次序是相对另一个孩子而言的，如果只有一个就不用分左右次序，但是二叉树是需要的

几种特殊的二叉树​

  1. 满二叉树：

  2. 完全二叉树：

    1. 若i≤[n/2]向下取整后，则结点 i 为分支结点，否则为叶结点
    2. 叶结点只可能在最大的两层上出现。对于下面的叶结点，都靠左
    3. 若有度为1的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子。
    4. 按层序编号后，一旦出现某结点(编号为i)为叶结点或只有左孩子，则编号大于i的结点均为叶结点。（参考12号节点）
    5. 若n为奇数，则每个分支结点都有左孩子和右孩子；若n为偶数，则编号最大的分支结点(编号为n/2)只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

  3. 二叉排序树：

    左节点大于右节点

总结篇​

二叉树的顺序存储​

记得 找父节点是i/2之后向下取整

判断i是否为叶子分支节点

i>[n/2]向下取整i>[n/2]向下取整

链式存储​

二叉树求空指针域​

n个结点、2n个指针域，每个结点带一个天线但是root无，所以被占用的指针域有n-1个

空指针域=2n-(n-1)=n+1

三叉树空指针域or三叉链式带父节点的​

需要看场合来分析，比如说三叉树的就是3n个指针域

三叉链式带父节点的那种是二叉树

错题​

5.2.06​

08​

14完全二叉树 n求叶结点数​

完全二叉树 叶结点数求结点数最大最少值​

最少的话，就直接那几个叶子节点就是最后一层

最多的话，那几个叶子节点是倒数第二层的最右边

总结​

爆率最高：

  1. 当前层结点数：2h−12^{h-1}
  2. 总结点数：2h−12^h-1
  3. 完全二叉树第i个的祖先：[i/2]向下取整
  4. 完全二叉树
    1. n=2k为偶数：n1=1，n0=k，n2=k-1
    2. n=2k-1为奇数：n1=0，n0=k，n2=k-1
  5. n0=n1+1n_0=n_1+1
  6. 完全二叉树高度常用[log2n+1log_2{n}+1]

遍历​

请务必记住分支节点逐层展开法​

还有从你的全世界路过法​

层次遍历​

  1. 根节点入队
  2. 如果队列不空，出队一个并访问该节点，将其左右孩子入队
  3. 直到队列为空

由遍历序列构造二叉树​

无论哪个遍历都得加上中序遍历才能确定唯一的二叉树

前序+中序​

这个方法屌啊，由前序遍历找到根节点，再区分左右

线索二叉树​

注意，线索二叉树的数据结构有变

typedef struct TreadNode{
    ElemType data;
    struct ThreadNode *lchild,*rchild;
    int lflag,rflag;//tag=0为指向孩子，1为线索
}

注意，算法中的

判断条件，有点离谱的

加入左节点的：p->lchild==NULL

加入右节点的，不会一开始就用p判断p->rchild==NULL，因为要将pre指向后驱节点

所以判断条件为 pre!=NULL&&pre->rchild==NULL

最后遍历完，注意处理最后一个节点的right=NULL

先序线索化可能会出现的转圈问题​

在根节点加入线索后，第一个左边递归需要判断是不是左孩子线索

中序线索二叉树的遍历​

找中序后继​

找中序后继：

  1. 找到第一个被中序遍历的节点（就是最左下角）
    1. while(p->ltag==0)p=p->lchild;
    2. 意思是找到最后一个左下角不带线索的
  2. 找p的后继结点：
    1. 如果tag=1（不是叶子节点），右孩子就是线索，就是中序后继
    2. 如果tag=0（后继有人）要找右节点的最左下角的,中序是左根右，左边会递归 然后 再回溯到根输出根
  3. visit

找中序前驱​

逐层展开法看上去真的挺好用的

先序​

找先序前驱​

后续后驱​

总结​

不用背，现推

中序先序后续
找前驱√×√
找后继√√×

​ 除非有三叉链表实现找爹

森林​

存储结构​

双亲表示法（顺序）​

优点：找双亲节点方便

缺点，找孩子不方便，要遍历数组

孩子表示法（顺序+链式）​

优点：找孩子方便

缺点：找爹不行

孩子兄弟表示法（链式）​

总结​

森林、树、二叉树的转换​

主要为孩子兄弟表示法为核心存储

左孩子，右兄弟

兄弟右指针用糖葫芦串起来

孩子左指针挂下面