树的相关算法

Posted:   September 27, 2019

Status:   Completed

Tags :   数据结构

Categories :  

Were equations, pictures or diagrams not properly rendered, please refresh the page. If the problem persists, you can contact me.

一、树的基本概念

  1. 树的定义：
    • 当n=0时，那就是空树
    • 任意一棵非空树应该满足：
      • 有且仅有一个特定的被称为根的结点
      • 当n>1时，其余结点可以分为m个互不相交的有限集合，这些集合本身也是树，称为根结点的子树
  2. 基本术语（略）
  3. 树的性质
    • 树中的结点树等于所有结点度数加1
    • 高度为h的m叉树至多有(m^h - 1)/(m - 1)个结点，等比数列和公式
    • 具有n个结点的m叉树的最小高度为向下取整(logm(n(m - 1) + 1))
  4. 易错点：树的路径长度是所有路径长度的总和

二、二叉树的概念

  1. 二叉树的定义：每个结点至多只有两棵子树
  2. 几个特殊的二叉树：略
  3. 二叉树的性质：略，熟了
  4. 二叉树的存储结构：顺序存储结构与链式存储结构

三、二叉树的遍历：对非线性结构进行线性化操作

  1. 先序遍历

  2. 中序遍历

  3. 后序遍历

    #include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
   
typedef struct BitNode{
  int data;
  struct BitNode *lchild, *rchild;
}BitNode;
   
typedef struct Node{
  BitNode* data;
  struct Node *next;
}Node,*Stack;
   
typedef struct LinkStack{
  Node* top; //栈顶指针
  int count; //元素个数
}LinkStack;
   
LinkStack InitStack(){
  LinkStack stack;
  stack.top = NULL;
  stack.count = 0;
  return stack;
}
   
void Push(LinkStack* stack,BitNode* x){
  Node* s;
  s = (Node*)malloc(sizeof(Node));
  s->next = stack->top;
  s->data = x;
  stack->top = s;
  stack->count++;
}
   
void Pop(LinkStack* stack){
  Node* s;
  s = stack->top;
  stack->top = stack->top->next;
  free(s);
  stack->count--;
}
   
   
int isEmpty(LinkStack stack)
{
    if (stack.count == 0)
    {
        return TRUE;
    }
    else
        return FALSE;
}
   
//递归创建一棵二叉树
BitNode* Create_BitTree(){
  int x;
  scanf("%d",&x);
  BitNode* node = NULL;
  if(x != 999){
    node = (BitNode*)malloc(sizeof(BitNode));
    node->data = x;
    node->lchild = Create_BitTree();
    node->rchild = Create_BitTree();
  }
  return node;
}
   
//非递归前序遍历
void Preorder1(BitNode* T){
  LinkStack S = InitStack(); //初始化一个栈
  BitNode* p = T; //创造一个指向二叉树根的指针
  while (p!=NULL||isEmpty(S)==0) { //只有当二叉树不为空或栈不为空时才会开始
    while (p!=NULL) { //当二叉树不为空时
      Push(&S,p); //将现在访问的结点 
      printf("%d\n", p->data); //输出现在正在访问的结点，相当于已经遍历过了
      p = p->lchild; //因为是先序遍历，现在转到其结点的左孩子
    } //循环一波直到最左孩子
   
    if(isEmpty(S)==0){ //现在栈不为空，需要把其中存储元素的右结点弄出来
      p = S.top->data; //获得现在的栈顶元素，也就是最左下子树根结点
      Pop(&S); //栈元素-1
      p = p->rchild; //现在获得最左下子树根结点的右孩子
    }
  }
}
   
//非递归中序遍历，与前序遍历类似，问题不大
void Inorder1(BitNode* T){
  LinkStack S = InitStack();
  BitNode* p = T;
  while (p!=NULL||isEmpty(S)==0) {
    while (p!=NULL) {
      Push(&S,p);
      p = p->lchild;
    }
   
    if(isEmpty(S)==0){
      p = S.top->data;
      Pop(&S);
      printf("%d\n", p->data);
      p = p->rchild;
    }
  }
}
   
//非递归后序遍历，与前中序遍历都不太一样
void Postorder1(BitNode* T){
  LinkStack S = InitStack(); //初始化栈
  BitNode* pCur = T; //当前访问节点的指针
  BitNode* pLastVisit = NULL; //当前访问结点的上一个结点的指针
  while (pCur!=NULL) { //只要当前的访问结点不为空，循环
    Push(&S,pCur); //将当前结点入栈
    pCur = pCur->lchild; //获得当前结点的左孩子
  }
   
  while (isEmpty(S)==0) { //只要栈不为空，循环
    pCur = S.top->data; //从栈中获得当前结点
    Pop(&S); //获取后元素出栈
    if(pCur->rchild==NULL||pCur->rchild==pLastVisit){ //如果当前结点右孩子为空或等于当前结点的上一个访问结点
      printf("%d\n",pCur->data); //输出
      pLastVisit = pCur; //上一个访问结点变为现在输出过的结点
    }
    else{ //这种情况就是遇到子树根结点了
      Push(&S,pCur); //将当前结点重新入栈
      pCur = pCur->rchild; //当前结点指针指向其右孩子
      while (pCur!=NULL) {
        Push(&S,pCur); //将当前结点入栈
        pCur = pCur->lchild; //获得当前结点的左孩子
      }
    }
  }
}
   
   
//递归前序遍历
void Preorder(BitNode* T){
  if(T != NULL){
    printf("%d\n", T->data);
    Preorder(T->lchild);
    Preorder(T->rchild);
  }
}
   
//递归中序遍历
void Inorder(BitNode* T){
  if(T != NULL){
    Inorder(T->lchild);
    printf("%d\n", T->data);
    Inorder(T->rchild);
  }
}
   
//递归后序遍历
void Postorder(BitNode* T){
  if(T != NULL){
    Postorder(T->lchild);
    printf("%d\n", T->data);
    Postorder(T->rchild);
  }
}
   
int main(int argc, char const *argv[]) {
  BitNode* T = Create_BitTree();
  Preorder(T);
  Preorder1(T);
  Inorder(T);
  Inorder1(T);
  Postorder(T);
  Postorder1(T);
  return 0;
}

  4. 层次遍历（利用队列，和BFS的方法很像，略）

  5. 线索二叉树

    • 本质：二叉链表表示的二叉树存在大量空指针，利用他们指向前驱或者后继
    • n个结点的二叉树中有n+1个空指针
    • 指向结点前驱和后继的指针称为线索（点题）
    • 二叉树的线索化就是遍历一次二叉树，检查当前结点的左右指针域是否为空，为空的话就改为线索
    #include <stdio.h>
#include <stdlib.h>
#define TElemType char//宏定义，结点中数据域的类型
//枚举，Link为0，Thread为1
typedef enum {
    Link,
    Thread
}PointerTag;
//结点结构构造
typedef struct BiThrNode{
    TElemType data;//数据域
    struct BiThrNode* lchild,*rchild;//左孩子，右孩子指针域
    PointerTag Ltag,Rtag;//标志域，枚举类型
}BiThrNode,*BiThrTree;
   
BiThrTree pre=NULL;
   
//采用前序初始化二叉树
//中序和后序只需改变赋值语句的位置即可
void CreateTree(BiThrTree * tree){
    char data;
    scanf("%c",&data);
    if (data!='#')
    {
        if (!((*tree)=(BiThrNode*)malloc(sizeof(BiThrNode))))
        {
            printf("申请结点空间失败");
            return;
        }
        else
        {
            (*tree)->data=data;//采用前序遍历方式初始化二叉树
            CreateTree(&((*tree)->lchild));//初始化左子树
            CreateTree(&((*tree)->rchild));//初始化右子树
        }
    }
    else
    {
        *tree=NULL;
    }
}
//中序对二叉树进行线索化
void InThreading(BiThrTree p){
    //如果当前结点存在
    if (p) 
    {
        InThreading(p->lchild);//递归当前结点的左子树，进行线索化
        //如果当前结点没有左孩子，左标志位设为1，左指针域指向上一结点 pre
        if (!p->lchild) {
            p->Ltag=Thread;
            p->lchild=pre;
        }
        //如果 pre 没有右孩子，右标志位设为 1，右指针域指向当前结点。
        if (pre&&!pre->rchild) {
            pre->Rtag=Thread;
            pre->rchild=p;
        }
        pre=p;//pre指向当前结点
        InThreading(p->rchild);//递归右子树进行线索化
    }
}
   
//中序遍历线索二叉树
void InOrderThraverse_Thr(BiThrTree p)
{
    while(p)
    {
        //一直找左孩子，最后一个为中序序列中排第一的
        while(p->Ltag == Link){
            p = p->lchild;
        }
        printf("%c ", p->data);  //操作结点数据
        //当结点右标志位为1时，直接找到其后继结点
        while(p->Rtag == Thread && p->rchild !=NULL)
        {
            p = p->rchild;
            printf("%c ", p->data);
        }
        //否则，按照中序遍历的规律，找其右子树中最左下的结点，也就是继续循环遍历
        p = p->rchild;
    }
}
   
int main() {
    BiThrTree t;
    printf("输入前序二叉树:\n");
    CreateTree(&t);
    InThreading(t);
    printf("输出中序序列:\n");
    InOrderThraverse_Thr(t);
    return 0;
}

四、树的存储结构

  1. 双亲表示法

    #include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
typedef char ElemType;//宏定义树结构中数据类型
typedef struct Snode  //结点结构
{
    ElemType data;
    int parent; //双亲位置域
}PNode;
   
typedef struct  //树结构
{
    PNode tnode[MAX_SIZE];
    int n;                 //结点个数
}PTree;
   
PTree InitPNode(PTree tree)
{
    int i,j;
    char ch;
    printf("请输出节点个数:\n");
    scanf("%d",&(tree.n));
   
    printf("请输入结点的值其双亲位于数组中的位置下标:\n");
    for(i=0; i<tree.n; i++)
    {
        fflush(stdin);
        scanf("%c %d",&ch,&j);
        tree.tnode[i].data = ch;
        tree.tnode[i].parent = j;
    }
    return tree;
}
   
void FindParent(PTree tree)
{
    char a;
    int isfind = 0;
    printf("请输入要查询的结点值:\n");
    fflush(stdin);
    scanf("%c",&a);
    for(int i =0;i<tree.n;i++){
        if(tree.tnode[i].data == a){
            isfind=1;
            int ad=tree.tnode[i].parent;
            printf("%c的父节点为 %c,存储位置下标为 %d",a,tree.tnode[ad].data,ad);
            break;
        }
    }
    if(isfind == 0){
        printf("树中无此节点");
    }
}
   
int main()
{
    PTree tree;
    tree = InitPNode(tree);
    FindParent(tree);
    return 0;
}

  2. 孩子表示法

    #include<stdio.h>
#include<stdlib.h>
#define MAX_SIZE 20
#define TElemType char
//孩子表示法
typedef struct CTNode{
    int child;//链表中每个结点存储的不是数据本身，而是数据在数组中存储的位置下标
    struct CTNode * next;
}ChildPtr;
typedef struct {
    TElemType data;//结点的数据类型
    ChildPtr* firstchild;//孩子链表的头指针
}CTBox;
typedef struct{
    CTBox nodes[MAX_SIZE];//存储结点的数组
    int n,r;//结点数量和树根的位置
}CTree;
//孩子表示法存储普通树
CTree initTree(CTree tree){
    printf("输入节点数量：\n");
    scanf("%d",&(tree.n));
    for(int i=0;i<tree.n;i++){
        printf("输入第 %d 个节点的值：\n",i+1);
        fflush(stdin);
        scanf("%c",&(tree.nodes[i].data));
        tree.nodes[i].firstchild=(ChildPtr*)malloc(sizeof(ChildPtr));
        tree.nodes[i].firstchild->next=NULL;
   
        printf("输入节点 %c 的孩子节点数量：\n",tree.nodes[i].data);
        int Num;
        scanf("%d",&Num);
        if(Num!=0){
            ChildPtr * p = tree.nodes[i].firstchild;
            for(int j = 0 ;j<Num;j++){
                ChildPtr * newEle=(ChildPtr*)malloc(sizeof(ChildPtr));
                newEle->next=NULL;
                printf("输入第 %d 个孩子节点在顺序表中的位置",j+1);
                scanf("%d",&(newEle->child));
                p->next= newEle;
                p=p->next;
            }
        }
    }
    return tree;
}
   
void findKids(CTree tree,char a){
    int hasKids=0;
    for(int i=0;i<tree.n;i++){
        if(tree.nodes[i].data==a){
            ChildPtr * p=tree.nodes[i].firstchild->next;
            while(p){
                hasKids = 1;
                printf("%c ",tree.nodes[p->child].data);
                p=p->next;
            }
            break;
        }
    }
    if(hasKids==0){
        printf("此节点为叶子节点");
    }
}
   
int main()
{
    CTree tree;
    tree = initTree(tree);
    //默认数根节点位于数组notes[0]处
    tree.r=0;
    printf("找出节点 F 的所有孩子节点：");
    findKids(tree,'F');
    return 0;
}

  3. 孩子兄弟表示法

    #define ElemType char
typedef struct CSNode{
    ElemType data;
    struct CSNode * firstchild,*nextsibling;
}CSNode,*CSTree;

五、树、森林、二叉树的转换：这个主要是做题了

六、树和森林的遍历

  1. 先根遍历：若树非空，先访问根结点，再按从左到右的顺序遍历根结点的每棵子树，访问顺序与这棵树相应的二叉树的先序遍历相同

  2. 后根遍历：若树非空，先访问根结点，再按从左到右的顺序遍历根结点的每棵子树，访问顺序与这棵树相应的二叉树的中序遍历相同

  3. 中根遍历：没有的事哈，你怎么确定哪个是中哈哈哈

  4. 先序遍历森林：就正常的

  5. 后序遍历森林：就正常的

  6. 中序遍历森林：只有二叉树森林才有中序遍历与完整二叉树中序遍历对应

  7. 王道描述坑爹啊

七、树的应用：并查集（简单的集合表示）

  1. Union(S,root1,root2)：表示把集合S中的自己和root2并入子集合root1中。要求root1和root2互不相交，否则不执行合并操作

  2. Find(S,x)：查找集合S中单元素x所在的子集合，并且返回该子集合的名字

  3. Initial(S)：将集合S中的每个元素都初始化为只有一个单元素的子集合

  4. 通常用树的双亲表示作为并查集的存储结构，每个子集合以一棵树表示

  5. 所以子集合的树构成表示全集合的森林

  6. 数组元素下标表示元素名，根结点下标表示子集合名，根结点双亲结点表示负数

    #define SIZE 100
int UFSets[SiZE]; //并查集所使用的数组，双亲指针数组
   
void Initial(int S[]){ //每个自成单元集合
    for(int i=0;i<size;i++){
        S[i] = -1;
    }
}
    
int Find(int S[], int x){ //Find操作
    while(S[x] >= 0){ //不能是根结点
        x = S[x];
    }
    return x;
}
   
void Union(int S[], int root1, int root2){
    S[root2] = root1;
}

八、二叉排序树

  1. 二叉排序树的定义（可以为空）：

    • 若左子树非空，则左子树上所有结点关键字值均小于根结点的关键字值
    • 若右子树非空，则右子树上所有结点关键字值均大于根结点的关键字值
    • 左右子树本身分别也是一棵二叉排序树：产生递归性

  2. 二叉排序树的查找

    //非递归形式的查找算法
BSTNode* BST_Search(BiTree T, int key, BSTNode* p){
    p = NULL; //p指向被查找结点的双亲，用于插入和查找操作
    while(T != NULL && key != T->data){
        p = T;
        if(key < T->data){
            T = T->lchild;
        }else{
            T = T->rchild;
        }
    }
    return T;
}

  3. 二叉树的插入：动态集合，并不是一次生成的，需要一步步插入

    int BST_Insert(BiTree T, int k){
    //在二叉排序树中插入一个关键字为k的结点
    if(T == NULL){ //原树为空，新插入的记录为根结点
        T = (BiTree)malloc(sizeof(BSTNode));
        T->key = k;
        T->lchild = T->rchild = NULL;
        return 1;
    }
    else if(k == T->key){ //树中存在相同的关键字
        return 0;
    }
    else if(k < T->key){
        return BST_Insert(T->lchild, k); //插入T的左子树
    }
    else{
        return BST_Insert(T->rchild, k); //插入T的右子树
    }
}

  4. 二叉树的构造：依次输入数据，插入到二叉排序树中合适的位置

    void Creat_BST(BiTree T, int str[],int n){
    //用关键字数组建立一个二叉排序树
    T = NULL;
    int i=0;
    while(i < n){
        BST_Insert(T, str[i]);
        i++;
    }
}

  5. 二叉树排序树的删除：对于平衡二叉树也有启发作用

    • 如果被删除结点是叶结点，直接删除，不会破坏本身性质
    • 若被删除结点拥有一棵左子树或一棵右子树，用子树替代被删除结点的位置
    • 若被删除结点拥有左右子树，那么需要用被删除结点的直接前驱或后驱（就是数值上挨着的）替换，然后就变成了上述两种情况，再进行转换
    • 新插入的关键字总是作为叶结点插入，但叶结点并不一定处于最底层
    • 当删除一个结点，结点是非叶结点时，，重新插入得到的二叉排序树和原来肯定不同

  6. 二叉排序树的查找效率分析

    • 查找平均长度和树的高度有关，而树的高度和二叉排序树的形态有关，而二叉排序树的形态和插入顺序有关
    • 平衡查找树的平均查找长度是O(log2n)
    • 有序表是静态查找表时，顺序表作为存储结构比较好
    • 有序表是动态查找表时，二叉排序树作为其逻辑结构比较好

九、平衡二叉树

  1. 就是为了避免二叉排序树的高度增长过快，用来保证二叉排序树的性能不会降的太快，所以有了平衡二叉树的规则来保证
  2. 调整规律：
    • 所在结点的左孩子的左子树插入新结点，打破平衡后，右旋操作
    • 所在结点的右孩子的右子树插入新结点，打破平衡后，左旋操作
    • 所在结点的左孩子的右子树插入新结点，打破平衡后，从下往上，先左旋操作，再右旋操作
    • 所在结点的右孩子的左子树插入新结点，打破平衡后，从下往上，先右旋操作，再左旋操作
  3. 平衡二叉树查找：与二叉排序树相同，毕竟只是优化了一些结构上的东西
    • 需要注意的算法：Nh表示深度为h的平衡树中含有的最少结点数，Nh = Nh-1 + Nh-2 + 1
    • 每一步都是最少结点树，都是平衡树，那么自然可以递推出来，可以看162的图

十、哈弗曼树与哈弗曼编码，至少现在没什么好说的，不算难

  1. 错法，尽管它题目有时候说怎么怎么着的规则，但是哈弗曼树本身就是为了起到压缩数据的效果嘛，那严奶奶的题我是觉得描述有误，但是人家是大佬不是，没办法JOJO

Comments

😅 Commenting is disabled on this post.
You can use extended GitHub flavored markdown in your comment. Commenting FAQs & Guidelines