考研笔记 | 数据结构 §5.树和二叉树

  • 英语:

§1 树

  1. 树是N(N≥0)个结点的有限集合,当N=0时,称为空树。
  2. 对非空树,有:

    • 有且仅有一个特定的结点,称为根;
    • 当N>1时,其余结点可风味m(m>0)个互不相交的有限集合$T_1$,$T_2$,……,$T_n$,其中一个集合又是一棵树,并称为子树。
    • 树的根结点没有前驱结点,除根结点外仅有一个前驱;
    • 树中所有结点可有零至多个结点。
  1. 1
    2
    3
    4
    5
    6
    graph LR
    A{祖先节点}---|n层|B(双亲结点)
    B(双亲结点)-->C[结点]
    B(双亲结点)-->D[兄弟结点]
    C(结点)-->E[孩子结点]
    E[孩子结点]-->|n层|F[子孙结点]
  2. 树中的一个结点的子结点个数称为该结点的度。
    树中结点最大度数称为树的度。

  3. 度大于0的结点称为分支结点,度为0的结点称为叶子(终端)结点。
    1. 结点层次从树根开始定义;
    2. 结点深度从根结点自顶向下累加;
    3. 结点高度从叶结点开始自底向上累加;
    4. 树的高度即为最大深度。
    1. 树的结点数等于所有结点的度数加1;
    2. 度为m的树中第i层上至多有$m^i-1$个结点(i≥1);
    3. 高度为h的m叉树至多有$\frac{m^n-1}{m-1}$个结点
    4. 具有n个结点的m叉树最小高度是$\lceil log_m(n(m-1)+1)\rceil$

§2 二叉树

  1. 二叉树:每个结点至多只有两棵子树,且有左右之分。
  2. 二叉树有五种基本形态

    二叉树的五种基本形态

  3. 第i层上至多有$2^i-1$个结点,深度为$k$的二叉树至多有$2^k-1$个结点。

  4. 满二叉树:深度为$k$,有$2^k-1$个结点。
  5. 完全二叉树(最后一层不满):

    • $i≤\lfloor\frac{n}{2}\rfloor$,则$i$为分支结点,否则是叶子;

    • 若有度为1的结点,只可能有一个,即其仅有左孩子而无右孩子。

  6. 二叉排序树:左子树上结点关键字<根节点<右子树节点。
  7. 平衡二叉树:树上任一结点左右子树深度之差不超过1。
  8. 1)非空二叉树上叶子结点树等于度为2的结点数加1,即$N_0=N_2+1$;
    2)非空二叉树上第$k$层最多有$2^{k-1}$个结点($k≥1$);
    3)高度为$h$的二叉树至多有$2^n-1$个结点;
    4)
    • 当$i$>1时,结点$i$的层次为$\lfloor\frac{i}{2}\rfloor$,若$i$=1,则为根;
    • $i$的左孩子是$2i$,如果$2i>n$,则无左孩子;
    • $i$的右孩子是$2i+1$,若$2i+1>n$,则无右孩子;
    • $i$所在的层次为$\lfloor\log_2i\rfloor$+1。
      • 5) 完全二叉树的高度为$\lceil\log_2(n+1)\rceil$或$\lfloor\log_2n\rfloor+1$

§3 二叉树的存储结构

  1. 顺序存储:用数组,编号$i$存于$i-1$外。无用的用0补全
  2. 链式存储结构

    • 二叉链表二叉树的链式存储结构

      1
      2
      3
      4
      typedef struct BTNode{
      DataType data;
      struct BTNode,*lchild,*rchild;
      }BTNode,*BinTree;//二叉键表
    • 三叉链表二叉树的链式存储结构(三叉链表)

      1
      2
      3
      4
      typedef struct BTNode{
      DataType data;
      struct BTNode,*lchild,*rchild,*parent;
      }BTNode,*BinTree;//三叉键表
  3. 用二叉键表存储n个结点的二叉树,共要(n+1)个空指针域,
    用三叉键表存储n个结点的二叉树,共要(n+2)个空指针域。

  4. 二叉树的遍历

    • 1) 先序遍历,根左右(NLR)

      1
      2
      3
      4
      5
      6
      7
      void PreOrder(BiTree T){
      if(T!=Null){
      visit(T);
      PreOrder(T->lchild);
      PreOrder(T->rchild);
      }
      }
    • 2) 中序遍历,左根右(LNR)

      1
      2
      3
      4
      5
      6
      7
      void InOrder(BiTree T){
      if(T!=Null){
      InOrder(T->lchild);
      visit(T);
      InOrder(T->rchild);
      }
      }
    • 3) 后序遍历,左右根(LRN)

      1
      2
      3
      4
      5
      6
      7
      void PostOrder(BiTree T){
      if(T!=Null){
      PostOrder(T->lchild);
      PostOrder(T->rchild);
      visit(T);
      }
      }
    • 4) 层次遍历(借助队列)

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      void LevelOrder(BiTree){
      InitQueue(Q);//初始化队列
      BiTree P;
      EnQueue(Q,T);//树根入队列
      while(!=IsEmpty(Q){
      DeQueue(Q,P);
      visit(P);
      if(P->lchild!=Null)
      EnQueue(Q,P->lchild);
      if(P->rchild!=Null)
      EnQueue(Q,P->rchild);
      }
      }
  5. 非递归形式遍历

    • 中序遍历

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      void InOrder(BinTree T){
      InitStrack(S);
      BiTree P=T;
      while(P||!IsEmpty(S)){
      if(P){
      Push(S,P);//根入栈
      P=p->lchild;//非空则往左走
      }else{
      Pop(S,P);//退栈
      visit(P);
      P=P->rchild;//访问右结点
      }
      }
      }
    • 前序遍历

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      void PreOrder(BinTree T){
      InitStrack(S);
      BiTree P=T;
      while(P||!IsEmpty(S)){
      if(P){
      visit(P);
      Push(S,P);//根入栈
      P=p->lchild;//非空则往左走
      }else{
      Pop(S,P);//退栈
      P->P->rchild;
      P=P->rchild;//访问右结点
      }
      }
      }
    • 后序遍历

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      void PostOrder(BinTree T){
      InitStrack(S);
      InitStrack(Tag);
      BiTree P=T;
      while(P||!IsEmpty(S)){
      if(P){
      Push(S,P);
      Push(Tag,1);
      P=p->lchild;
      }else{
      Pop(S,P);
      Pop(Tag,f);
      if(f==1){
      Push(S,P);
      Push(Tag,2);
      P=P->rchild;//从左子树反回(二次入栈),然后转右子树
      }else{
      visit(P);
      P=Null;//从右子树反回(二次出栈),访问根。P必须置空,使得下一步继续退栈
      }
      }
      }
      }//栈中当前结点的所有祖先
  6. 遍历二叉树的引用与思路
    1) 02) 1 3) 1+L 4) 1+R 5) 1+L+R

    • 求二叉树结点的个数

      1
      2
      3
      4
      int NodeCount(BinTree T){
      if(T==0) return 0;
      else return 1+NodeCount(T->lchild)+NodeCount(T->rchild);
      }
    • 求二叉树叶子结点的个数

      1
      2
      3
      4
      5
      6
      7
      int LeafCount(BinTree T){
      if(T==0) return 0;
      else{
      if(T->lchild==0&&T->rchild==0) return 1;
      else return LeafCount(T->lchild)+LeafCount(T->rchild);
      }
      }
    • 求二叉树的深度

      1
      2
      3
      4
      int Depth(BinTree T){
      if(T==0) return 0;
      else return 1+Max(Depth(T->lchild),Depth(T->rchild);
      }
  7. 线索二叉树 线索二叉树
    若有左子树,则ltag=0,否则,ltag=1,指向前驱;
    若有右子树,则rtag=0,否则,rtag=1,指向后继。

  8. 画线索二叉树:先画遍历序列,再画线索。

§4 一般树的存储结构

  1. 树的存储结构

    • 双亲表示法:存储结点,同时增加指针指向双亲。

      树的存储结构

      可直接找到每个结点的双亲,但求孩子需要遍历真个结构。

    • 孩子表示法:将每个孩子结点都用单链表连接起来。​孩子表示法
      方便找子女,但找双亲需要遍历N个结点中孩子链表所知的N个孩子链表

    • 孩子兄弟表示法:每个结点有三个部分,值、第一个孩子、第一个兄弟。孩子兄弟表示法
      优点:方便转为二叉树操作,查找孩子。
      缺点:难以查找双亲,可增加partent指针

§5 树与二叉树

  1. 树与二叉树的转换
对应二叉树
第一个孩子左孩子
下一个兄弟右孩子
  1. 遍历关系
森林二叉树
先根遍历先序遍历先序遍历
后根遍历中序遍历中序遍历
  1. 树的孩子兄弟链表示法与二叉树的二叉链表示法,本质上是一样的,只是解释不同。即树可用二叉树唯一表示。

  2. 区别:

二叉树
度至多为2无此限制
有左右子树之分无此限制
允许为空一般不允许为空

§6 二叉排序树

  1. 二叉排序树(BTS):特点:左<根<右

  2. 二叉排序树非递归查找

    1
    2
    3
    4
    5
    6
    7
    8
    9
    BSTNode *BST_Search(Btree T,ElemType key,BSTNode *&P){ 
    P=Null;
    while(T!=Null&&key!=T->data){
    P=T;
    if(key<T->data)
    T=T->lchild;
    else T=T-rchild;
    }return T;
    }//查找并返回值为key的结点指针
  3. 二叉排序树插入

    1
    2
    3
    4
    5
    6
    7
    8
    9
    int BST_Insert(BiTree &T,KeyType k){
    if(T==Null){
    T=(BiTree)malloc sizeof(BSTNode);
    T->key=k;T->lchild=T->rchild=Null;
    return true;
    }else if(k=T->key) return false;
    else if(k<T->key) return BST_Insert(T->lchild,k);
    else return BST_Insert(T->lchild,k);
    }
  4. 二叉排序树的构造

    1
    2
    3
    4
    5
    6
    7
    void Creat_BST(BiTree &T,KeyType str[],int n){
    T=Null;int i=0;
    while(i<n){
    BST_Insert(T,str[i]);
    i++;
    }
    }
  5. 平衡二叉树

构造方法
LL(右单旋转)A的左孩子的左子树插入了新结点
RR(左单旋转)A的右孩子的右子树插入了新结点
LR(左右旋转)A的左孩子的右子树插入了新结点
RL(右左旋转)A的右孩子的左子树插入了新结点
  1. 平衡二叉树最大深度为$O(log_2n)$,平均查找长度$O(log_2n)$

  2. 哈夫曼树:树的带权路径长度最小。

  3. 构造:“每次取两个最小的树组成哈夫曼树”。

  4. 哈夫曼编码:向左分支为0,向右分支为1。

  5. 若二叉树采用二叉链表存储,要交换其所有分支结点左右子树的位置,利用后序遍历方法最合适。

  6. 二叉树线索后,仍不能有效求解,后序线索二叉树中求后序后继。

  7. $带权路径长度=\sum_{i=1}^n 叶结点权值×到根节点的距离\ =所有分支结点权值之和-根节点权值$

§7 线性表、树、广义表

  1. 总说
    • 线性表属于约束性最强的线性结构,在非空线性表中,只有一个“第一个元素”,也只有一个“最后一个”元素。出第一个元素外,每个元素都有唯一前驱,除最后一个元素外,每个元素都有唯一后继。
    • 树是一种层次结构,有且仅有一个根结点,每个结点可以有多个子女,但只有一个双亲(除根外),从这一意义上说存在一(双亲)对多(子女)的关系。
    • 广义表元素既可以是原子,也可以是子表。子表可以为它表共享。
  2. 区别与联系:从表中套表意义上说,广义表也是层次结构。从逻辑上讲,树与广义表均属于非线性结构。但在以下意义下,又变为线性结构,如:度为1的树,以及元素都是原子的广义表。另外,广义表从元素之间的关系可以看作前驱和后继,也符合线性表,但这时元素有原子,也有子表,即元素不属于同意数据对象。
  3. 计算树的表达式求值
    • 1)对该二叉树进行后序遍历,得到表达式的后序遍历序列,再按后缀表达式求值;
    • 2)递归求出最自述表达式的值,再递归求出右子树表达式的值,最后按根结点运算符(+、-、×、÷)等进行最后求值。
-------文章到此结束  感谢您的阅读-------