第六章 树【数据结构和算法】【精致版】

简介: 第六章 树【数据结构和算法】【精致版】

前言

2023-11-6 16:22:17

以下内容源自《【数据结构和算法】【精致版】》

仅供学习交流使用

第六章 树

6.1 应用实例

  1. 数据压缩问题
  2. 表达式的树形表示
  3. 等价类划分问题

6.2 树的概念

6.2.1树的定义与表示

1.树的定义

树(tree)是n(n≥0)个结点的有限集合。当n=0时,称为“空树”;当n>0时,该集合满足如下条件。

①有且仅有一个称为“根"(root)的特定结点,该结点没有前驱结点,但有零个或多个直接后继结点。

②除根结点之外的n-1个结点可划分成m(m≥0)个互不相交的有限集T1,T2,T3,…,Tn,

每个Ti又是一棵树,称为“根的子树”(subtree)。每棵子树的根结点有且仅有一个直接前驱就是树的根结点,同时可以有零个或多个直接后继结点。

树的定义采用了递归定义的方法,即树的定义中又用到了树的概念,这正好反映了树的特性。

2.树的表示方法

①树形图表示

②嵌套集合表示法(文氏图表示法)

③广义表表示法(嵌套括号表示法)

④凹入表示法

6.2.2 树的基本术语

以下列出一些有关树的基本术语。

结点(node):包含一个数据元素及若干指向其子树的分支。如图6-5©中的树有A、B、C、 D、E等13个结点。

结点的度(degree):结点拥有子树的个数称为该结点的“度”。如图6-5©中结点A的度为3,结点B的度为2.

树的度:树中所有结点的度的最大值。如图6-5( c )树的度为3。

叶子结点(leaf):度为0的结点称为“叶子结点”,也称“终端结点”。如图6-5©中结点E、 K、L.G等均为叶子结点。

内部结点(internal node):度不为0的结点称为“内部结点”,也称为“分支结点”或“非终端结点”。如图6-5( c )中结点B、C、D等均为内部结点

下面借助人类族谱的一些术语描述树中结点之间的关系,以便直观理解

孩子结点(child):结点的子树的根(即直接后继)称为该结点的“孩子结点”。如图6-5© 中结点B、C、D是A结点的孩子结点,结点E、F是B结点的孩子结点。

双亲结点(parent):结点是其子树的根的双亲,即结点是其孩子的双亲。如图6-5©中结 点A是B、C、D的双亲结点,结点D是H、I、J的双亲结点。

兄弟结点(sibling):同一双亲的孩子结点之间互称兄弟结点。如图6-5©中结点H、I、J互 为兄弟结点。

堂兄弟:双亲是兄弟或堂兄弟的结点间互称堂兄弟结点。如图6-5©中结点E、G、H互为 堂兄弟,结点L、M也互为堂兄弟。

祖先结点(ancestor):结点的祖先结点是指从根结点到该结点的路径上的所有结点。如图 6-5©中结点K的祖先是A、B、F结点。

子孙结点(descendant):结点的子孙结点是指该结点的子树中的所有结点。 结点D的子孙有H、1、J、M结点

结点的层次(level):结点的层次从树根开始定义,根为第一层,根的孩子为第二层。若某 点在第系层,则其孩子就在第k+1层,以此米推。如图6-5©中结点C在第二层,结点M在 四层

树的深度(deph):树中所有结点层次的最大值称为树的“深度”,也称树的“高度”。如果 6-5©中的树的深度为4。

前辈:层号比某结点层号小的结点,都可称为该结点的“前辈”。如图6-5©中结点A、B C、D都可称为结点E的前辈。

后辈:层号比某结点层号大的结点,都可称为该结点的“后辈”。如图6-5©中结点K、L 都可称为结点E的后辈

森林(forest):m(m=0)棵互不相交的树的集合称为“森林”。在数据结构中,树和森林不像自然界中有明显的量的差别,可以称0棵树、1棵树为森林。任意一棵非空的树,删去根结点变成了森林;反之,给森林中各棵树增加一个统一的根结点,就变成了一棵树

有序树(ordered tree)和无序树(unordered tree):树中结点的各棵子树从左到右是有特定次序的树称为“有序树”,否则称为“无序树”。

6.2.3树的抽象数据类型定义

6.3 二叉树

6.3.1二叉树的定义

二叉树(binary tree)是n(n20)个结点的有限集合。当n时,称为“空二叉树”;当n>( 时,该集合由一个根结点及两棵互不相交的,被分别称为“左子树”和“右子树”的二叉树 组成。

以前面定义的树为基础,二叉树可 以理解为是满足以下两个条件的树形结构

① 每个结点的度不大于2。

② 结点每棵子树的位置是明确区分左右的,不能随意改变。

由上述定义可以看出:二叉树中的每个结点只能有0、1或2个孩子,而且孩子有左右之分, 即使仅有一个孩子,也必须区分左右。位于左边的孩子(或子树)叫左孩子(左子树),位于右边 的孩子(或子树)叫右孩子(右子树)。

二叉树也是树形结构,故6.2.2小节所介绍的有关树的术语都适用于二叉树。

二叉树不是结点度不大于2的有序树,
反例:只有右子树的二叉树和只有左子树的二叉树不同

6.3.2 二叉树的性质

  1. 在二叉树的第i层上至多有2i-1个结点(i>=1)
  2. 深度为k的二叉树至多有2k-1个结点(k>=1)
  3. 对于任意一颗二叉树T,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1.

下面给出两种特殊的二叉树,然后讨论其相关性质。

满二叉树 深度为k且含有2k-1个结占的一叉树称为“满二叉树”

满二叉树的连续编号:对含有n个结点的的满二叉树,约定从根开始,按层从上到下,每

层内从左到右,逐个对每一结点进行编号1,2,…,n。

完全二叉树 深度为k、结点数为n(n<=2k-1)的二叉树,当且仅当其n个结点与满二叉树

中连续编号为1至n的结点位置一一对应时,称为“完全二叉树”。

完全二叉树有两个重要特征:其一,所有叶子结点只可能出现在层号最大的两层上;其二,对

任意结点,若其右子树的层高为k,则其左子树的层高只可为k或k+1。

由定义可知,满二叉树必为完全二叉树,而完全二叉树不一定是满二叉树。

  1. 具有n个结点的完全二叉树的深度为[log2n」+1。向下取整
  2. 对于具有n个结点的完全二叉树,如果按照对满二义树结点进行连续编号的方式,
    对所有结点从1开始顺序编号,则对于任意序号为的结点有以下结论。
    ① 如果i=1,则结点i为根,其无双亲结点;如果i>1,则结点i,则结点i的双亲结点为[i/2] 向下取整
    ② 如果2i<=n,则结点i的左孩子结点序号为2i,否则,结点i无左孩子。
    ③ 如果2i+1<=n,则结点i的右孩子结点序号为2i+1,否则,结点i无右孩子。

6.3.3 二叉树的存储

1.顺序存储结构

对于满二叉树和完全二叉树来说,可以按照对满二叉树结点连续编号的次序,将各结点数据

存放到一组连续的存储单元中,即用一维数组作存储结构,将二又树中编号为i的结点存放在数

组的第i号分量中、根据二叉树的性质5,可知数组中下标为i的结点的左孩子下标为2i,右孩

子下标为2i+1,双亲结点的下标为[ i/2」。

二叉树的顺序存储结构可描述如下。

#define MAX 100
typedef struct{
  datatype SqBiTree[ MAX+1];  //0号单元不用
  int nodemax;        //数组中最后一个结点的下标
}Bitree;

2.链式存储结构

二叉树的二叉链表结点结构:

LChild域指向该结点的左孩子

Data域指向该结点的数据

RChild域指向该结点的右孩子

typedef char DataType; 
typedef struct Node{
  DataType data;
  struct Node * LChild;
  struct Node * RChild;
}BiTNode,*BiTree;

一个二叉树含有n个结点,则它的二叉链表中必含有2n个指针域,而仅有n-1个指针域指向其孩子,其余的n+1的指针域为空的链域。

可以用空链域存储其他有用的信息,便得到“线索二叉树”

二叉树的三叉链表结点结构:

Parent域指向该结点的双亲

LChild域指向该结点的左孩子

Data域指向该结点的数据

RChild域指向该结点的右孩子

6.4 二叉树的遍历

6.4.1 二叉树的遍历及递归实现

1.二叉树的遍历

依据对根结点访问的先后次序不同来命名二叉树的访问方式,分别称DLR为先序遍历(或

先根遍历)、LDR为中序遍历(或中根遍历),LRD为后序遍历(或后根遍历)

下面给出二叉树三种遍历方式的递归定义。

(1)先序遍历

其二叉树为空,则空操作;否则依次执行如下二个操作,

①访问根结点。

②按先序遍历左子树。

③按先序遍历右子树。

(2)中序遍历

若二叉树为空,则空操作;否则依次执行如下三个操作。

①按中序遍历左子树。

②访问根结点。

③按中序遍历右子树。

(3)后序遍历

若二叉树为空,则空操作;否则依次执行如下三个操作。

①按后序遍历左子树。

②遍历右子树。

③访问根结点。

2.二叉树遍历的递归实现

1-二叉树的递归实现.c
#include<stdio.h>
#include<stdlib.h>
typedef char DataType; 
typedef struct Node{
  DataType data;
  struct Node * LChild;
  struct Node * RChild;
}BiTNode,*BiTree;
#define FALSE 0
#define TRUE 1
#define MAXSIZE 10
//【算法6-17】用扩展先序遍历序列创建二叉链表 
void CreateBiTree( BiTree *root){
  char ch;
  ch=getchar();
  if(ch=='^') * root= NULL;
  else{
    * root = (BiTree) malloc(sizeof(BiTNode));
    (*root)->data=ch;
    CreateBiTree(&((*root)->LChild));
    /*以左子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/  
    CreateBiTree(&((*root)->RChild));
    /*以右子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/
  }
}
//访问 
void Visit(DataType n){
  printf("%c",n);
}
//【算法6-1】递归 先序
void PreOrder(BiTree root){
  //先序遍历二叉树,root为根节点的指针 
  if(root){
    Visit(root->data);
    PreOrder(root->LChild);
    PreOrder(root->RChild);
  } 
} 
//【算法6-2】递归 中序
void InOrder(BiTree root){
  //中序遍历二叉树,root为根节点的指针 
  if(root){
    InOrder(root->LChild);
    Visit(root->data);
    InOrder(root->RChild);
  } 
} 
//【算法6-3】递归 后序 
void PostOrder(BiTree root){
  //后序遍历二叉树,root为结点的指针
  if(root){
    PostOrder(root->LChild);
    PostOrder(root->RChild);
    Visit(root->data);
  }
}
//ABD^G^^^CE^H^^F^^
int main(){
  BiTree root; 
  BiTree *_root=&root;
  printf("输入扩展先序序列\n"); 
  //ABD^G^^^CE^H^^F^^
  CreateBiTree(_root);
  printf("先序序列(递归)\n"); 
  PreOrder(root);//ABDGCEHF 
  printf("\n");
  printf("中序序列(递归)\n"); 
  InOrder(root);//DGBAEHCF
  printf("\n");
  printf("后序序列(递归)\n"); 
  PostOrder(root);//GDBHEFCA
  printf("\n");
}

6.4.2 二叉树遍历的非递归实现

1.先序遍历二叉树的非递归实现

2.中序遍历二叉树的非递归实现

3.后序遍历二叉树的非递归实现

4.二叉树的层次遍历

2-二叉树的非递归实现.c
#include<stdio.h>
#include<stdlib.h>
typedef char DataType; 
typedef struct Node{
  DataType data;
  struct Node * LChild;
  struct Node * RChild;
}BiTNode,*BiTree;
//定义顺序栈 
#define MAXSIZE 10
typedef BiTree  ElemType; 
typedef struct{ 
  ElemType elem[MAXSIZE];
  int top;
}SeqStack;
//(1)置空栈
//首先建立栈空间,然后初始化栈顶指针。
SeqStack * InitStack(){
  SeqStack *s;
  s=(SeqStack * ) malloc(sizeof( SeqStack));  
  s->top=-1;
  return s;
}
//(2)判空栈
int Empty(SeqStack *s){
  if(s->top==-1) return 1;  //代表空 
  else return 0;
}
//(3)入栈
int Push(SeqStack *s, ElemType x){
  if(s->top==MAXSIZE-1) return 0;//栈满不能入栈,否则将造成“上溢” 
  else {
    s->top++;
    s->elem[s->top]=x;
    return 1;
  } 
}
//(4)出栈
int Pop( SeqStack *s, ElemType *x){
  if(Empty(s)) return 0;  //栈空不能出栈
  else { 
    *x=s->elem[s->top];//栈顶元素存入*x,返回
    s->top--;
    return 1;
  }
}
//(5)取栈顶元素
ElemType GetTop(SeqStack *s){
  if(Empty(s)) return 0;//栈空
  else return (s->elem[s->top]);
}
#define FALSE 0
#define TRUE 1
#define MAXSIZE 10
typedef BiTree QueueDataType; 
//链队列的数据类型描述如下。
typedef struct node{ 
  QueueDataType data;
  struct node * next;
}QNode;
//链队列结点的类型
typedef struct{  
  QNode * front;
  QNode * rear;
} LQueue;//将头尾指针封装在一起的链队列
//(1)创建一个带头结点的空队
LQueue * Init_LQueue(){
  LQueue *q; QNode*p;
  q=(LQueue*)malloc( sizeof(LQueue));//申请头尾指针结点  
  p=(QNode*)malloc( sizeof(QNode));//申请链队列头结点  
  p->next=NULL;
  q->front=q->rear=p;
  return q;
}
//(2)入队
void InLQueue(LQueue *q , QueueDataType x){ 
  QNode *p;
  p=(QNode*)malloc(sizeof(QNode));//申请新结点  
  p->data=x;
  p->next=NULL; 
  q->rear->next=p;
  q->rear=p;
}
//(3)判队空
int Empty_LQueue(LQueue *q){
  if(q->front==q->rear) return 1;//代表空 
  else return 0;
}
//(4)出队
int Out_LQueue(LQueue *q, QueueDataType *x){
  QNode *p;
  if(Empty_LQueue(q)){
    printf("队空");
    return FALSE;
  }
  else{ 
    p=q->front->next;
    q->front->next=p->next;
    *x=p->data;//队头元素放x中
    free(p);
    if(q->front->next==NULL)//只有一个元素时,出队后队空,修改队尾指针
      q->rear=q->front;
    return TRUE;
  }
}
//【算法6-17】用扩展先序遍历序列创建二叉链表 
void CreateBiTree( BiTree *root){
  char ch;
  ch=getchar();
  if(ch=='^') * root= NULL;
  else{
    * root = (BiTree) malloc(sizeof(BiTNode));
    (*root)->data=ch;
    CreateBiTree(&((*root)->LChild));
    /*以左子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/  
    CreateBiTree(&((*root)->RChild));
    /*以右子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/
  }
}
//访问 
void Visit(DataType n){
  printf("%c",n);
}
//【算法6-4】非递归 先序
void PreOrderN(BiTree root){
  SeqStack *S;
  BiTree p;
  S=InitStack();
  p=root;
  while(p!=NULL||!Empty(S)){//当前结点指针及栈均空,则结束
    while (p!=NULL){//访问根结点,根指针进栈,进入左子树
      Visit(p->data);
      Push(S,p);
      p=p->LChild;
    }
    if(!Empty(S)){//根指针退栈,进入其右子树
      Pop(S,&p);
      p=p->RChild;
    }
  }
}
//【算法6-5】非递归 中序-1
void InOrderN1(BiTree root){
  SeqStack *S;
  BiTree p;
  S=InitStack();
  p=root;
  while(p!=NULL||!Empty(S)){//当前结点指针及栈均空,则结束
    while (p!=NULL){//访问根结点,根指针进栈,进入左子树
      Push(S,p);
      p=p->LChild;
    }
    if(!Empty(S)){//根指针退栈,进入其右子树
      Pop(S,&p);
      Visit(p->data);
      p=p->RChild;
    }
  }
} 
//【算法6-6】非递归 中序-2
void InOrderN2(BiTree root){
  SeqStack *S;
  BiTree p;
  S=InitStack();
  p=root;
  while(p!=NULL||!Empty(S)){//当前结点指针及栈均空,则结束
    if (p!=NULL){//访问根结点,根指针进栈,进入左子树
      Push(S,p);
      p=p->LChild;
    }else{//根指针退栈,进入其右子树
      Pop(S,&p);
      Visit(p->data);
      p=p->RChild;
    }
  }
}
//【算法6-7】非递归 后序
void PostOrderN(BiTree root){
  SeqStack *S;
  BiTree p,q;
  S=InitStack();
  p=root;
  q=NULL;
  while(p!=NULL||!Empty(S)){//当前结点指针及栈均空,则结束
    while (p!=NULL){//访问根结点,根指针进栈,进入左子树     
      Push(S,p);
      p=p->LChild;
    }
    if(!Empty(S)){
      p=GetTop(S);
      if((p->RChild==NULL)||(p->RChild==q)){
        //判断栈顶结点的有子树是否为空,右子树是否刚访问过 
        Pop(S,&p);
        Visit(p->data);
        q=p;
        p=NULL;
      }else{
        p=p->RChild;
      }
    }
  }
}
//【算法6-8】二叉树的层次遍历 
void LevelOrder(BiTree root){
  LQueue *Q;
  BiTree p;
  Q=Init_LQueue();
  InLQueue(Q,root);
  while(!Empty_LQueue(Q)){
    Out_LQueue(Q,&p);
    Visit(p->data);
    if(p->LChild!=NULL){
      InLQueue(Q,p->LChild);
    }
    if(p->RChild!=NULL){
      InLQueue(Q,p->RChild);
    }
  }
}
//ABD^G^^^CE^H^^F^^
int main(){
  BiTree root; 
  BiTree *_root=&root;
  printf("输入扩展先序序列\n"); 
  //ABD^G^^^CE^H^^F^^
  CreateBiTree(_root);
  printf("先序序列(非递归)\n"); 
  PreOrderN(root);//ABDGCEHF 
  printf("\n");
  printf("中序序列-1(非递归)\n"); 
  InOrderN1(root);//DGBAEHCF
  printf("\n");
  printf("中序序列-2(非递归)\n"); 
  InOrderN2(root);//DGBAEHCF
  printf("\n");
  printf("后序序列(非递归)\n"); 
  PostOrderN(root);//GDBHEFCA
  printf("\n");
  printf("层次遍历\n");
  LevelOrder(root);//ABCDEFGH
  printf("\n");
}

6.4.3 遍历算法的应用

1.统计二叉树的结点数

2.输出二叉树的叶子结点

3.统计二叉树的叶子结点数目

4.求二叉树的高度

5.求结点的双亲

6.二叉树相似性判定

7.按树状打印二叉树

8.创建二叉链表存储的二叉树

3-二叉树的遍历算法应用.c
#include<stdio.h>
#include<stdlib.h>
typedef char DataType; 
typedef struct Node{
  DataType data;
  struct Node * LChild;
  struct Node * RChild;
}BiTNode,*BiTree;
//【算法6-17】用扩展先序遍历序列创建二叉链表 
void CreateBiTree( BiTree *root){
  char ch;
  ch=getchar();
  if(ch=='^') * root= NULL;
  else{
    * root = (BiTree) malloc(sizeof(BiTNode));
    (*root)->data=ch;
    CreateBiTree(&((*root)->LChild));
    /*以左子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/  
    CreateBiTree(&((*root)->RChild));
    /*以右子树域地址为参数,可使被调用函数中建立的结点指针置于该域中*/
  }
}
//访问 
void Visit(DataType n){
  printf("%c",n);
}
//【算法6-1】递归 先序
void PreOrder(BiTree root){
  //先序遍历二叉树,root为根节点的指针 
  if(root){
    Visit(root->data);
    PreOrder(root->LChild);
    PreOrder(root->RChild);
  } 
} 
// 【算法6-9】先序遍历统计二叉树的结点数
int Count=0;
void CountWithPreOrder(BiTree root){
  //Count为统计结点数目的全局变量,调用前初始值为0
  if(root){
    Count++;//统计结点数
    CountWithPreOrder(root->LChild);//先序遍历左子树 
    CountWithPreOrder(root->RChild);//先序遍历右子树 
  }
} 
// 【算法6-10】中序遍历输出二叉树的叶子结点
void PrintTNWithInOrder(BiTree root){
  if(root){
    PrintTNWithInOrder(root->LChild);
    if(root->LChild==NULL&&root->RChild==NULL){
      Visit(root->data);
    }
    PrintTNWithInOrder(root->RChild);
  }
} 
// 【算法6-11】后序遍历输出二叉树的叶子结点数目 
int leaf(BiTree root){
  int nl,nr;
  if(root==NULL){
    return 0;
  } 
  if((root->LChild==NULL)&&(root->RChild==NULL)){
    return 1;
  }
  nl=leaf(root->LChild);//递归求左子树的叶子数
  nr=leaf(root->RChild);//递归求右子树的叶子数 
  return(nl+nr); 
} 
//【算法6-12】全局变量法求二叉树的高度
int depth=0; 
void TreeDepth(BiTree root,int h){
  //h为root结点所在的层次,首次调用前初始值为1
  //depth为记录当前求得的最大层次的全局变量,调用前初始值为0
  if(root){
    if(h>depth) {
      depth=h;//当前结点层大于depth,则更新 
    }     
    TreeDepth(root->LChild,h+1);//遍历左子树,子树根层次为h+1
    TreeDepth(root->RChild,h+1);//遍历右子树,子树根层次为h+1   
  } 
} 
//【算法6-13】求二叉树的高度
int PostTreeDepth(BiTree root){
  int hl,hr,h;
  if(root== NULL) return 0;
  else{
    hl = PostTreeDepth(root->LChild);//递归求左子树的高度
    hr= PostTreeDepth (root->RChild);//递归求右子树的高度
    h=(hl>hr? hl:hr)+1;       //计算树的高度
    return h;
  }
}
//【算法6-14】求二叉树中某一结点的双亲 
BiTree parent( BiTree root, BiTree current){
  //在以root为根的二叉树中找结点current的双亲
  BiTree p;
  if(root == NULL) return NULL;
  if(root->LChild== current||root->RChild ==current)
    return root;    //root即为current的双亲
  p=parent(root->LChild,current);//递归在左子树中找
  if (p!=NULL) return p;
  else return(parent (root->RChild,current));//递归在右子树中找
} 
//【算法6-15】二叉树相似性判定 
int like(BiTree t1, BiTree t2){
  int like1, like2;
  if(t1==NULL && t2==NULL) return 1;//t1,t2均空,则相似
  if(t1==NULL||t2==NULL)return 0;//t1、t2仅一棵空,则不相似  
  like1=like(t1->LChild,t2->LChild);//递归判左子树是否相似
  like2=like(t1->RChild,t2->RChild);//递归判右子树是否相似
  return (like1 && like2); 
}
//【算法6-16】按树状打印二叉树 
void PrintTree( BiTree root,  int h){
  if(root == NULL) return;
  PrintTree(root->RChild, h+1);  //先打印右子树
  int i;
  for(i=0;i<h;i++) printf(" ");//层次决定结点的左右位置  
  printf("%c\n",root->data);//输出结点
  PrintTree(root->LChild,h+1);  //后打印左子树
}
//ABD^G^^^CE^H^^F^^
int main(){
  BiTree root; 
  BiTree *_root=&root;
  printf("输入扩展先序序列\n"); 
  //ABD^G^^^CE^H^^F^^
  CreateBiTree(_root);
  if(Count!=0){
    Count=0;
  }
  printf("统计结点数\n");
  CountWithPreOrder(root);
  printf("%d",Count); 
  printf("\n");
  printf("输出叶子结点\n"); 
  PrintTNWithInOrder(root); 
  printf("\n");
  printf("统计叶子结点数\n");  
  int leafCount=leaf(root); 
  printf("%d",leafCount);
  printf("\n");
  if(depth!=0){
    depth=0;
  }
  printf("二叉树的高度\n"); 
  TreeDepth(root,1); 
  printf("%d",depth);
  printf("\n");
  printf("二叉树的高度\n"); 
  int dpth=PostTreeDepth(root); 
  printf("%d",dpth);
  printf("\n");
  printf("求双亲\n"); 
  BiTree current=(root->LChild)->LChild;
  BiTree pt=parent(root,current);
  Visit(pt->data);
  printf("\n");
  BiTree rt; 
  BiTree *_rt=&rt;
  printf("输入rt扩展先序序列\n"); 
  //ABD^G^^^CE^H^^F^^
  fflush(stdin); //清一下输入的\n 
  CreateBiTree(_rt);
  printf("先序序列(递归)\n"); 
  PreOrder(rt);
  printf("\n");
  printf("root和rt是否相似\n"); 
  int lk=like(root,rt);
  printf("%d",lk);
  printf("\n");
  printf("树状打印\n"); 
  int depth=PostTreeDepth(root);
  PrintTree(root,depth);
}

6.4.4由遍历序列确定二叉树

1.由先序和中序确定二叉树

思想:

先序确定根结点

中序确定左右结点

2.由中序和后序确定二叉树

思想:

后序确定根结点

中序确定左右结点

6.5线索二叉树

6.5.1 线索二叉树的基本概念

在线索二叉树中,为了正确区分指向左右孩子的指针和指向前驱后驱的指针,将结点结构改为5个域,原二又链表中的左孩子域、数据域和右孩子域依战保持不变,增加左标志域Ltag和右标志域它们是两个布尔型的数据城。

线索二叉树的结点结构如下 :

LChild Ltag Data Rtarg RChild

①若结点有左子树,则LChild城仍指向其左孩子;否则,LChild域指向其遍历序列中的直接前驱结点

②若结点有右子树,则RChild域仍指向其右孩子;否则,RChild域指向其遍历序列中的直接后继结点

③ Lag和Rtag的定义如下:

{   0 LChild域指示结点的左孩子
Ltag =  {
    { 1 LChild域指示结点的遍历前驱
    { 0 RChild域指示结点的右孩子
Rtag =  {
    { 1 RChid域指示结点的遍历后继

在上述存储结构中,指向前驱和后继结点的指针称为“线索”,对二叉树以某种次序进行遍历并且将空指针改为线索的过程叫做“线索化”,经过线索化的一叉树称为“线索二叉树”;以上述结点结构存储的含有线索的二叉链表称为“线索链表”

依据二叉树遍历策略的不同,存在三种不同的线索二叉树。依据二叉树的先序、中序、后序 遍历策略,分别对应有先序线索二叉树、中序线索二叉树和后序线索二叉树。

6.5.2 二叉树的线索化

6.5.3 线索二叉树的遍历

6.6 树和森林

6.6.1 树的存储

1.双亲表示法

双亲表示法的存储结构定义如下。

define MAX 100
typedef struct TNode{  /*顺序表结点结构定义。/  
  DataType data;
  int parent;
}TNode;
typedef struct{     /*树的定义*/
  TNode tree[MAX];
  int root;     /*树的根结点在表中的位置*/
  int num;      /*树的结点个数*/
 }PTree;

2.孩子表示法

孩子表示法的存储结构定义如下。

typedef struct ChildNode{ //孩子链表结点结构定义
  int Child;
  Struct ChildNode * next;
}ChildNode;
typedef struct{       //顺序表结点结构定义
  DataType data;
  ChildNode w FirstChild;
| DataNode;
typedef struct{       //树的定义
  DataNode nodes[ MAX];
  int root;       //树的根结点在顺序表中的位置
  int num;        //树的结点个数
| CTree;

3.孩子兄弟表示法

孩子兄弟表示法的存储结构定义如下。

typedef struet CSNode{
  DataType data;          /*结点信息*/
  Struct CSNode * FirstChild;   /*第一个孩子指针*/
  Struct CSNode * NextSibling;  /*右兄弟指针*/
}CSNode.* CSTree;

6.6.2 树、森林与二叉树的转换

6.6.3 树和森林的遍历

二叉树 森林
先序 先根 先序
中序 后根 中序
中序 \ 中序

6.7哈夫曼树及其应用

哈夫曼(Hufman)树,又称最优二叉树,是带权路径长度最短的树,来构造最优编码,用于信息传输、数据压缩等方面,是一种应用广泛的二叉树。

6.7.1哈夫曼树

在介绍哈夫量树之前,先介绍几个与哈夫曼树相关的基本概念

路径;树中个结点到另一个结点之间的分支序列构成两个结点间的路径,

路径长度:路径上分支的条数称为“路径长度”。

树的路径长度:从树根到每个结点的路径长度之和称为“树的路径长度”。

6.3节介绍的完全二叉树,是结点数给定的情况下路径长度最短的二叉树。

带权路径长度:结点到树根间的路径长度与结点的权的乘积,称为该结点的“带机

结点的权:给树中结点赋予一个数值,该数值称为“结点的权”。

树的带权路径长度:树中所有叶子结点的带权路径长度之和,称为“树的带权路径长度",常记为WPL:

WPL = ∑nk=1 Wkx,Lk

其中,n为叶子数,Wk为第k个叶子的权值,Lk为第k个叶子到树根的路径长度。

最优二叉树:在叶子个数n以及各叶子的权值W,确定的条件下,树的带权路径长度W 最小的二叉树称为“最优二叉树”。

1.哈夫曼树的建立

2.哈夫曼算法的实现

6.7.2哈夫曼编译码

1.哈夫曼编码的概念

信息压缩达到最短的前缀编码

2.哈夫曼编码的算法实现

3.哈夫曼编码的译码

6.8 实例分析与实现

6.8.1表达式树

6.8.2树与等价类的划分

6.8.3回溯法与N皇后问题

6.9 算法总结

实验

哈夫曼编码的实现

习题

1.单项选择题

(1)树最适合用来表示的结构是B

A.元素间的有序结构

B.元素间具有分支及层次关系的结构

C.元素间的无序结构

D.元素间无联系的结构

(2)设一棵二叉树的结点个数为18,则它的高度至少为B

A.4

B.5

C.6

D.18

(3)任意一棵二叉树的叶子结点在其先序、中序、后序序列中的相对位置C

A.肯定发生变化

B.有时发生变化

C.肯定不发生变化

D.无法确定

4)判断线索二叉树中某结点P有左孩子的条件是C

A. p!=NULL

B.p->lchild!=NULL

C.p->LTag=0

D.p->LTag=1

(5)二叉树在线索化后,仍不能有效求解的问题是C

A.先序线索二叉树中求后继

B.中序线索二叉树中求后继

C.中序线索二叉树中求前驱

D.后序线索二叉树中求后继

(6)设森林T中有4棵树,其结点个数分别为n、nz、ng、ng,那么当森林T转换成一棵二叉树后,则根结点 的右子树上有 D 个结点。

A.n1-1

B.n1

C.n1+n2+n3

D.n2+n3+n4

(7)由权值分别为925.7的4个叶子结点构造一棵哈夫曼树,则该树的带权路径长度WPL为C

A.23

B.37

C.44

D.46

(8)设T是一棵哈夫曼树,有8个叶结点,则树T的高度最高可以是C

A.4

B.6

C.8

D.10

3.完成题

3完成题

(1)已知一棵二叉树的后序序列为ABCDEFG,中序序列为ACBCEDF。试完成下列操作。

①画出该二叉树的树形图。

G(C(A,B),F(E(^,D),^))

②给出该二叉树的先序序列。

GCABFED

③画出该二叉树的顺序存储结构示意图。

0 1 2 3 4 5 6 ... 13 ...
  G C F A B E      D

(2)已知一棵树的双亲表示法如下所示,试完成下列操作。

①画出该树的树形图。

A----------------------------------
  B----------------------------------
    E----------------------------------
      K--------------------------
    F----------------------------------
      C--------------------------
      M--------------------------
  C--------------------------
    G--------------------------
      N--------------------------
    H--------------------------
      O--------------------------
  D--------------------------
    I--------------------------
    J--------------------------

②画出该树的孩子兄弟二叉链表存储结构示意图。

A
                 B           ^
      E                   C
  K        F             G                   D
  ^  ^    C   ^      N     H          I  ^
        ^   M         ^ ^  O   ^           ^ J
                    ^ ^         ^ ^

③画出对应二叉树的中序线索二叉树。

中序:KELMFBNGOHCIJDA

(3)假设某通信报文的字符集由A、B、C、D、E、F共6个字符组成,它们在报文中出现的次数分别为16、12、9、30、3、6。试构造一棵哈夫曼树,并完成如下操作。

(76)
      30      (46)
          (18)   (28)
        (9) 9     12 16
               3 6

①计算哈夫曼树的带权路径长度。

177

②写出各叶子结点对应字符的哈夫曼编码。

A   B    C   D  E    F
111 110  101 0  1000 1001

4.算法设计题

(1)编写算法,在以二叉链表存储的二叉树中,求度为2的结点的个数。

#include<stdio.h>
#include<stdlib.h>
typedef char DataType; 
typedef struct Node{
  DataType data;
  struct Node * LChild;
  struct Node * RChild;
}BiTNode,*BiTree;
int Node2(BiTree T){
  if(!T){
    return 0;
  }else if(T->LChild&&T->RChild){
    return Node2(T->LChild)+Node2(T->RChild)+1;
  }else{
    return Node2(T->LChild)+Node2(T->RChild);
  }
}
int main(){
  BiTNode e={'E'};
  BiTNode f={'F'};
  BiTNode d={'D',&e,&f};
  BiTNode b={'B'};
  BiTNode c={'C'};
  BiTNode a={'A',&b,&c};
  BiTNode root={'0',&a,&d};
  int res=Node2(&root);
  printf("%d",res);//3
}

(2)编写算法,在以二叉链表存储的二叉树中,交换二叉树各结点的左右子树。

#include<stdio.h>
#include<stdlib.h>
typedef char DataType; 
typedef struct TreeNode{
  DataType data;
  struct TreeNode * left;
  struct TreeNode * right;
}BiTNode,*BiTree;
struct TreeNode* invertTree(struct TreeNode *root){
  struct TreeNode* temp=NULL;
  if(root==NULL){
    return NULL;
  }
  temp=root->left;
  root->left=root->right;
  root->right=temp;
  invertTree(root->left);
  invertTree(root->right);
  return root;
} 
//访问 
void Visit(DataType n){
  printf("%c",n);
}
//【算法6-1】递归 先序
void PreOrder(BiTree root){
  //先序遍历二叉树,root为根节点的指针 
  if(root){
    Visit(root->data);
    PreOrder(root->left);
    PreOrder(root->right);
  } 
}
int main(){
  BiTNode e={'E'};
  BiTNode f={'F'};
  BiTNode d={'D',&e,&f};
  BiTNode b={'B'};
  BiTNode c={'C'};
  BiTNode a={'A',&b,&c};
  BiTNode root={'0',&a,&d};
  //翻转前 
  PreOrder(&root);
  printf("\n"); 
  BiTree r=invertTree(&root);
  //翻转后 
  PreOrder(r);
}

最后

2023-11-6 17:03:04

我们都有光明的未来

不必感谢我,也不必记得我

祝大家考研上岸

祝大家工作顺利

祝大家得偿所愿

祝大家如愿以偿

点赞收藏关注哦

相关文章
|
23天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
34 1
|
26天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
83 4
|
1月前
|
算法
数据结构之博弈树搜索(深度优先搜索)
本文介绍了使用深度优先搜索(DFS)算法在二叉树中执行遍历及构建链表的过程。首先定义了二叉树节点`TreeNode`和链表节点`ListNode`的结构体。通过递归函数`dfs`实现了二叉树的深度优先遍历,按预序(根、左、右)输出节点值。接着,通过`buildLinkedList`函数根据DFS遍历的顺序构建了一个单链表,展示了如何将树结构转换为线性结构。最后,讨论了此算法的优点,如实现简单和内存效率高,同时也指出了潜在的内存管理问题,并分析了算法的时间复杂度。
51 0
|
24天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
23天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
1月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
97 23
|
1月前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
60 20
|
24天前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
45 5
|
23天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
54 1
|
1月前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
50 0