【数据结构】课堂复习笔记4——树和二叉树

学习的网课是青岛大学-王卓的数据结构与算法基础系列课程，可在bilibili上观看。并配合zjut课堂笔记整理，仅用于学习和复习

四、树和二叉树

4.1 树和二叉树的定义

4.1.1 树的定义

  • 树：是n个结点的有限集
    • 有且仅有一个称之为根的结点
    • 除根结点以外的其余结点可分为m（m＞0）个互不相交的有限集T1, T2, …, Tm, 其中每一个集合本身又是一棵树，并且称为根的子树（SubTree）
  • 树的前驱和后继的特点：
    • 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点
    • 树中所有结点可以有零个或多个后继结点。
  • 基本术语：
    • 1：
      • 根：即根结点(没有前驱)
      • 叶子：即终端结点(没有后继)
      • 森林：指m棵不相交的树的集合(例如删除A后的子树)
      • 有序树：结点各子树从左至右有序，不能互换（左为第一）
      • 无序树：结点各子树可互换位置
    • 2：
      • 双亲：即上层的那个结点(直接前驱)
      • 孩子：即下层结点的子树的根(直接后继)
      • 兄弟：同一双亲下的同层结点（孩子之间互称兄弟）
      • 堂兄弟：即双亲位于同一层的结点（但并非同一双亲）
      • 祖先：即从根到该结点所经分支的所有结点
      • 子孙：即该结点下层子树中的任一结点
    • 3：
      • 结点：即树的数据元素
      • 结点的度：结点挂接的子树数
      • 结点的层次：从根到该结点的层数（根结点算第一层）
      • 终端结点：即度为0的结点，即叶子
      • 分支结点：即度不为0的结点（也称为内部结点）
      • 树的度：所有结点度中的最大值
      • 树的深度：指所有结点中最大的层数

4.1.2 二叉树的定义

  • 二叉树：是n（n≥0）个结点所构成的集合，它或为空树（n = 0）；或为非空树，对于非空树T：
    • 有且仅有一个称之为根的结点
    • 除根结点以外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身又都是二叉树

4.2 二叉树的性质和存储结构

4.2.1 二叉树的性质

  • 性质：
    • 性质1: 在二叉树的第i层上至多有个结点。至少1个
    • 性质2: 深度为k的二叉树至多有个结点，至少k个
    • 性质3: 对于任何一棵二叉树，若2度的结点数有个，则叶子数必定为 （即）
    • 性质4: 具有n个结点的完全二叉树的深度必为
    • 性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为
  • 特殊形态的二叉树：
    • 满二叉树：一棵深度为k 且有个结点的二叉树
    • 完全二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应

4.2.2 二叉树的顺序存储

  • 实现：按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
    • 浪费空间，适于存满二叉树和完全二叉树

4.2.3 二叉树的链式存储

二叉链表：

typedef struct BiNode{
   TElemType   data;
   struct  BiNode   *lchild,*rchild; //左右孩子指针
}BiNode,*BiTree;

三叉链表：

typedef struct TriTNode
{  TelemType data;
   struct TriTNode *lchild,*parent,*rchild;
}TriTNode,*TriTree;

4.3 遍历二叉树和线索二叉树

4.3.1 遍历算法

  • 先序遍历：根、左、右
  • 中序遍历：左、根、右
  • 后序遍历：左、右、根 先序遍历算法：
Status PreOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     cout<<T->data; //访问根结点
     PreOrderTraverse(T->lchild); //递归遍历左子树
     PreOrderTraverse(T->rchild); //递归遍历右子树
    }
}

中序遍历算法：

Status InOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     InOrderTraverse(T->lchild); //递归遍历左子树
     cout<<T->data; //访问根结点
     InOrderTraverse(T->rchild); //递归遍历右子树
    }
}

后序遍历算法：

Status PostOrderTraverse(BiTree T){
  if(T==NULL) return OK; //空二叉树
  else{    
     PostOrderTraverse(T->lchild); //递归遍历左子树
     PostOrderTraverse(T->rchild); //递归遍历右子树
     cout<<T->data; //访问根结点
    }
}
  • 时间效率：，每个结点只访问一次
  • 空间效率：，栈占用的最大辅助空间

4.3.2 遍历算法的应用

二叉树的建立：按先序遍历序列建立二叉树的二叉链表

void CreateBiTree(BiTree &T){
cin>>ch;
if (ch==’#’)   T=NULL;  	//递归结束，建空树
else{
    T=new BiTNode;    T-＞data=ch; 	//生成根结点
    CreateBiTree(T-＞lchild);  //递归创建左子树
    CreateBiTree(T-＞rchild); //递归创建右子树
  }									
}

计算二叉树结点总数：

int NodeCount(BiTree T){
  if(T == NULL ) return 0;  			 
  else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

计算二叉树叶子结点总数：

int LeadCount(BiTree T){
  if(T==NULL) 	//如果是空树返回0
    return 0;
  if (T->lchild == NULL && T->rchild == NULL)
    return 1; //如果是叶子结点返回1
  else return LeafCount(T->lchild) + LeafCount(T->rchild);
}

计算二叉树的深度：

int Depth (BiTree T ){ // 返回二叉树的深度
   int depthval,  depthLeft,  depthRight;
   if ( !T )    depthval = 0;  // 递归结束条件
   else   {
     depthLeft = Depth( T->lchild );
     depthRight= Depth( T->rchild );
     depthval = 1 + (depthLeft > depthRight  ?depthLeft : depthRight);
   } 
   return depthval;
}

重要结论： 若二叉树中各结点的值均不相同，则：由二叉树的先序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。 中序遍历非递归算法：

Status InOrderTraverse(BiTree T){
  BiTree p; InitStack(S); p=T;
  while(p||!StackEmpty(S)){
    if(p) {Push(S,p);p=p->lchild;}
    else {
      Pop(S,q);
      printf("%c",q->data);
      p=q->rchild;
    }
  }
  return OK;
}

二叉树层次遍历算法：

typedef struct{
  BTNode data[MaxSize];
  int front,rear;
}SqQueue;

void LevelOrder(BTNode *b){
  BTNode *p; SqQueue *qu;
  InitQueue(qu);
  enQueue(qu,b);
  while(!QueueEmpty(qu)){
    deQueue(qu,p);
    printf("%c",p->data);
    if(p->lchild!=NULL) enQueue(qu,p->lchild);
    if(p->rchild!=NULL) enQueue(qu,p->rchild);
  }
}

复制二叉树：

int Copy(BiTree T,BiTree &NewT){
  if(T==NULL){
    NewT=NULL;
    return 0;
  }
  else{
    NewT=new BiTNode; NewT->data=T->data;
    Copy(T->lChild,NewT->lchild);
    Copy(T->rChild,NewT->rchild);
  }
}

4.3.3 线索二叉树

  • 若结点有左子树，则lchild指向其左孩子；否则， lchild指向其直接前驱(即线索)
  • 若结点有右子树，则rchild指向其右孩子；否则， rchild指向其直接后继(即线索)
    • 这种改变指向的指针称为：线索
    • 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化
  • 增设标志域：itag,rtag
    • itag=0：指向左孩子，itag=1：指向前驱
    • rtag=0：指向右孩子，rtag=1：指向后继

4.4 树和森林

4.4.1 树的存储结构

  • 双亲表示法：
typedef struct PTNode{
  TElemType data;
  int parent;
}PTNode;

#define MAX_TREE_SIZE 100
typedef struct{
  PTNode nodes[MAX_TREE_SIZE];
  int r,n; //根节点的位置和结点个数
}PTree;
  • 孩子链表：
typedef struct CTNode{
  int child;
  struct CTNode *next;
}*ChildPtr;

typedef struct{
  TElemType data;
  ChildPtr firstchild;
}CTBox;

#define MAX_TREE_SIZE 100
typedef struct{
  PTNode nodes[MAX_TREE_SIZE];
  int r,n; //根节点的位置和结点个数
}CTree;
  • 孩子兄弟表示法：二叉链表表示法 分别指向第一个孩子结点和下一个兄弟结点
typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild,*nextsibling;
}CSNode,*CSTree;

4.4.2 树与二叉树的转换

  • 树转换成二叉树： 给定一棵树，可以找到唯一对应的二叉树
    • 加线：在兄弟之间加一连线
    • 抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系
    • 旋转：所有水平路径以子树的根结点为轴心，将整树顺时针转45°

树转换成的二叉树其根结点右子树一定为空

  • 二叉树转换成树：
    • 加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都与p的双亲用线连起来
    • 抹线：抹掉原二叉树中双亲与右孩子之间的连线
    • 调整：将结点按层次排列，形成树结构

4.4.3 森林与二叉树的转换

  • 森林转换成二叉树：
    • 将各棵树分别转换成二叉树。
    • 将每棵树的根结点用线相连。
    • 以第一棵树根结点为新二叉树的根，每棵树的根结点水平直线连接，再以新二叉树的根结点为轴心，顺时针旋转，构成二叉树型结构。
  • 二叉树转换成森林：
    • 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树
    • 还原：将孤立的二叉树还原成树

4.5 哈夫曼树

4.5.1 哈夫曼树的基本概念

  • 路径：由一结点到另一结点间的分支所构成
  • 路径长度：路径上的分支数目
  • 树的路径长度：从树根到每一个结点的路径长度之和。记作：TL
    • 结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树
  • 权：将树种结点赋给一个有着某种含义的数值
  • 带权路径长度：结点到根的路径长度与结点上权的乘积
  • 树的带权路径长度：树中所有叶子结点的带权路径长度之和
  • 哈夫曼树：构造出来的带权路径长度最小的二叉树
  • 特点：
    • 满二叉树不一定是哈夫曼树
    • 权大的结点靠近根
    • 权相同的二叉树，哈夫曼树不唯一

4.5.2 哈夫曼树的构造算法

  • 根据给定的n个权值{w1,w2,……wn}，构造n棵只有根结点的二叉树
  • 在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。
  • 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。
  • 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。

哈夫曼树的结点度数为0或2，没有度为1的结点

一棵有n个叶子结点的Huffman树有2n-1个结点（n-1次合并，共产生n-1个新结点且都具有2个孩子）

  • 结点类型定义：
typedef  struct
{  int weght;
   int parent,lch,rch;
}*HuffmanTree
  • 初始化：
void CreatHuffmanTree (HuffmanTree HT,int n){
  if(n<=1)return;
  m=2*n-1;
  HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点   
  for(i=1;i<=m;++i)
    {HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}
  for(i=1;i<=n;++i)cin>>HT[i].weight; 
}
  • 后续构造：
for( i=n+1;i<=m;++i){       //构造  Huffman树
 { Select(HT,i-1, s1, s2);　
      //在HT[k](1≤k≤i-1)中选择两个其双亲域为0,
      // 且权值最小的结点,
      // 并返回它们在HT中的序号s1和s2
   HT[s1].parent=i;   HT[s2] .parent=i;  
     //表示从F中删除s1,s2
   HT[i].lch=s1;    HT[i].rch=s2 ; 
     //s1,s2分别作为i的左右孩子
   HT[i].weight=HT[s1].weight + HT[s2] .weight;
     //i 的权值为左右孩子权值之和
    }
}

4.5.3 哈夫曼树编码

  • 哈夫曼编码是前缀编码，即任一字符的编码都不是另一字符编码的前缀。
  • 哈夫曼编码树中没有度为1的结点。若叶子结点的个数为n，则哈夫曼编码树的结点总数为 2n-1
  • 接收过程：按左0、右1的规定，从根结点走到一个叶结点，完成一个字符的译码。反复此过程，直到接收数据结束。