墨滴
江

江小南

V1

2022/12/13阅读：36主题：萌绿

【408篇】C语言笔记-第十四章（ 二叉树的建树和遍历&考研真题实战）

第一节：树与二叉树原理解析

1. 树

树是n(n>=0)个节点的有限集。当n=0时，称为空树。在任意一棵非空树中应满足：

  1. 有且仅有一个特定的称为根的结点。
  2. 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……,Tm，其中每个集合本身又是一棵树，并且称为根的子树。

树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

  1. 树的根节点没有前驱，除根节点外的所有结点有且只有一个前驱。
  2. 树种所有的节点可以有零个或多个后继。

树的结构：

2. 二叉树

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n(n>=0)个结点的有限集合：

  1. 或者为空的二叉树，即n=0.
  2. 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树分别是一棵二叉树。

二叉树的顺序存储：

二叉树的链式存储：

树节点数据结构：

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

树中任何一个结点都是一个结构体，它的空间我们通过malloc申请。

第二节：二叉树层次建树实战

function.h

//
// Created by Administrator on 2022/12/11.
//

#ifndef INC_14_4_TREE_FUNCTION_H
#define INC_14_4_TREE_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

// tag结构体是辅助队列使用的
typedef struct tag{
    BiTree p;// 树的某一个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;
#endif //INC_14_4_TREE_FUNCTION_H

main.cpp

#include "function.h"

int main() {
    BiTree pnew; // 新申请的树结点
    BiTree tree=NULL; // tree指向树根，代表树
    // 这些都是指针类型。phead就是队列头，ptail就是队列尾。listpnew指向新申请的结点，pcur指向当前放入数据的父节点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    char c;
    while (scanf("%c",&c)){
        if(c=='\n'){
            break; // 读到换行就结束
        }
        // calloc申请的大小就是两个参数的乘积
        pnew= (BiTree)calloc(1, sizeof(BiTNode));
        pnew->c=c;
        listpnew= (ptag_t)calloc(1, sizeof(tag_t)); // 给队列结点申请空间
        listpnew->p=pnew;
        if(NULL==tree){
            tree=pnew;
            phead=listpnew; // 队列头和队列尾指向第一个结点
            ptail=listpnew;
            pcur=listpnew;// pcur要指向要进入树的父亲元素
        } else{
            // 把结点放入队列中
            ptail->pnext=listpnew;
            ptail=listpnew;
            // 把结点放入树中
            if(NULL==pcur->p->lchild){
                pcur->p->lchild=pnew;  // 父亲结点的左孩子为空
            } else if(NULL==pcur->p->rchild){
                pcur->p->rchild=pnew;  // 父亲结点的右孩子为空
                pcur=pcur->pnext;  // 左右结点都满了，pcur指向下一个
            }
        }
    }
    return 0;
}
F:\Computer\Project\practice\14\14.4-tree\cmake-build-debug\14_4_tree.exe
abcdefghijk

进程已结束，退出代码为 0

原理图：

解析：

  1. listpnew始终指向新申请的空间。phead始终指向队列的头结点，ptail始终指向队列尾结点。pcur始终指向队列最后一个元素对应的父结点，比如i的父结点为d。
  2. 每次有新的元素，先将元素放入队列，ptail向后移。然后pcur指针对应的节点会判断左右两个孩子节点是否为空，如果左为空，就放入左孩子。如果右为空，就放入右孩子。然后再次向后移。
  3. pnew和tree是结构体类型。phead,ptail,listpnew,pcur是结构体指针类型。

第三节：二叉树前、中、后序遍历

在上一节建树的基础上增加前、中、后序遍历。

前序遍历：先打印自身，再打印左子树，然后打印右子树。

中序遍历：先打印左子树，再打印自身，然后打印右子树。

后序遍历：先打印左子树，再打印右子树，然后打印自身。

前序遍历也叫深度优先遍历。

function.h

//
// Created by Administrator on 2022/12/11.
//

#ifndef INC_14_4_TREE_FUNCTION_H
#define INC_14_4_TREE_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

// tag结构体是辅助队列使用的
typedef struct tag{
    BiTree p;// 树的某一个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;
#endif //INC_14_4_TREE_FUNCTION_H

main.cpp

#include "function.h"

// 前序遍历
void PreOrder(BiTree p){
    if(p!=NULL){
        putchar(p->c);  // 打印自身
        PreOrder(p->lchild); // 打印左子树
        PreOrder(p->rchild); // 打印右子树
    }
}
// 中序遍历
void InOrder(BiTree p){
    if(p!=NULL){
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}
// 后序遍历
void PostOrder(BiTree p){
    if(p!=NULL){
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}
int main() {
    BiTree pnew; // 新申请的树结点
    BiTree tree=NULL; // tree指向树根，代表树
    // 这些都是指针类型。phead就是队列头，ptail就是队列尾。listpnew指向新申请的结点，pcur指向当前放入数据的父节点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    char c;
    // abcdefghij
    while (scanf("%c",&c)){
        if(c=='\n'){
            break; // 读到换行就结束
        }
        // calloc申请的大小就是两个参数的乘积
        pnew= (BiTree)calloc(1, sizeof(BiTNode));
        pnew->c=c;
        listpnew= (ptag_t)calloc(1, sizeof(tag_t)); // 给队列结点申请空间
        listpnew->p=pnew;
        if(NULL==tree){ // 判断是否有跟结点
            tree=pnew;
            phead=listpnew; // 队列头和队列尾指向第一个结点
            ptail=listpnew;
            pcur=listpnew;// pcur要指向要进入树的父亲元素
        } else{
            // 把结点放入队列中
            ptail->pnext=listpnew;
            ptail=listpnew;
            // 把结点放入树中
            if(NULL==pcur->p->lchild){
                pcur->p->lchild=pnew;  // 父亲结点的左孩子为空
            } else if(NULL==pcur->p->rchild){
                pcur->p->rchild=pnew;  // 父亲结点的右孩子为空
                pcur=pcur->pnext;  // 左右结点都满了，pcur指向下一个
            }
        }
    }

    printf("--------PreOrder-----------\n");
    PreOrder(tree);
    printf("\n--------InOrder-----------\n");
    InOrder(tree);
    printf("\n--------PostOrder-----------\n");
    PostOrder(tree);
    return 0;
}
"F:\Computer\Project\practice\14\14.5-tree - front-in-end\cmake-build-debug\14_4_tree.exe"
abcdefghij
--------PreOrder-----------
abdhiejcfg
--------InOrder-----------
hdibjeafcg
--------PostOrder-----------
hidjebfgca
进程已结束，退出代码为 0

前序，中序，后序其实就是使用递归的思想，传入一个结点，按照顺序打印出来即可。

第四节：二叉树的层序遍历

层序遍历必须使用到辅助队列。

在上一节的基础上新增加了层序遍历函数LevelOrder。

层序遍历也叫层次遍历，也叫广度优先遍历。

function.h

//
// Created by Administrator on 2022/12/11.
//

#ifndef INC_14_4_TREE_FUNCTION_H
#define INC_14_4_TREE_FUNCTION_H
#include <stdio.h>
#include <stdlib.h>

typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode,*BiTree;

// tag结构体是辅助队列使用的
typedef struct tag{
    BiTree p;// 树的某一个结点的地址值
    struct tag *pnext;
}tag_t,*ptag_t;

// 队列相关的结构体
typedef BiTree ElemType;
typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;
typedef struct {
    LinkNode *front,*rear; // 链表头，链表尾
}LinkQueue; // 先进先出
void InitQueue(LinkQueue &Q);
void EnQueue(LinkQueue &Q,ElemType x);
bool DeQueue(LinkQueue &Q,ElemType &x);
bool IsEmpty(LinkQueue &Q);
#endif //INC_14_4_TREE_FUNCTION_H

queue.cpp

#include "function.h"

// 初始化队列
void InitQueue(LinkQueue &Q){
    Q.front=Q.rear=(LinkNode*) malloc(sizeof(LinkNode)); // 头和尾指向同一个结点
    Q.front->next=NULL; // 头结点的next指针为NULL
}

// 入队 尾部插入法
void EnQueue(LinkQueue &Q,ElemType x){
    LinkNode *s=(LinkNode*) malloc(sizeof(LinkNode));
    s->data=x;
    s->next=NULL;
    Q.rear->next=s; // rear始终指向尾部
    Q.rear=s;
}

// 出队 头部删除法
bool DeQueue(LinkQueue &Q,ElemType &x){
    if(Q.front==Q.rear){
        return false; // 队列尾空
    }
    LinkNode *p=Q.front->next;
    x=p->data;
    Q.front->next=p->next;  // 断链
    if(Q.rear==p){
        Q.rear=Q.front; // 队列置为空
    }
    free(p);
    return true;
}
// 判空函数
bool IsEmpty(LinkQueue &Q){
    if(Q.front==Q.rear){
        return true;
    } else{
        return false;
    }
}

main.cpp

#include "function.h"

// 前序遍历  也叫深度优先遍历
void PreOrder(BiTree p){
    if(p!=NULL){
        putchar(p->c);  // 打印自身
        PreOrder(p->lchild); // 打印左子树
        PreOrder(p->rchild); // 打印右子树
    }
}
// 中序遍历
void InOrder(BiTree p){
    if(p!=NULL){
        InOrder(p->lchild);
        putchar(p->c);
        InOrder(p->rchild);
    }
}
// 后序遍历
void PostOrder(BiTree p){
    if(p!=NULL){
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->c);
    }
}
// 层次遍历，也叫广度优先遍历
void LevelOrder(BiTree T){
    LinkQueue Q; // 辅助队列
    InitQueue(Q);
    BiTree p;
    EnQueue(Q,T); // 树根入队
    while (!IsEmpty(Q)){
        DeQueue(Q,p); // 出队当前结点并打印
        putchar(p->c);
        if(p->lchild!=NULL){ // 入队左孩子
            EnQueue(Q,p->lchild);
        }
        if(p->rchild!=NULL){ // 入队右孩子
            EnQueue(Q,p->rchild);
        }
    }
}
int main() {
    BiTree pnew; // 新申请的树结点
    BiTree tree=NULL; // tree指向树根，代表树
    // 这些都是指针类型。phead就是队列头，ptail就是队列尾。listpnew指向新申请的结点，pcur指向当前放入数据的父节点
    ptag_t phead=NULL,ptail=NULL,listpnew=NULL,pcur=NULL;
    char c;
    // abcdefghij
    while (scanf("%c",&c)){
        if(c=='\n'){
            break; // 读到换行就结束
        }
        // calloc申请的大小就是两个参数的乘积
        pnew= (BiTree)calloc(1, sizeof(BiTNode));
        pnew->c=c;
        listpnew= (ptag_t)calloc(1, sizeof(tag_t)); // 给队列结点申请空间
        listpnew->p=pnew;
        if(NULL==tree){ // 判断是否有跟结点
            tree=pnew;
            phead=listpnew; // 队列头和队列尾指向第一个结点
            ptail=listpnew;
            pcur=listpnew;// pcur要指向要进入树的父亲元素
        } else{
            // 把结点放入队列中
            ptail->pnext=listpnew;
            ptail=listpnew;
            // 把结点放入树中
            if(NULL==pcur->p->lchild){
                pcur->p->lchild=pnew;  // 父亲结点的左孩子为空
            } else if(NULL==pcur->p->rchild){
                pcur->p->rchild=pnew;  // 父亲结点的右孩子为空
                pcur=pcur->pnext;  // 左右结点都满了，pcur指向下一个
            }
        }
    }

    printf("--------PreOrder-----------\n");
    PreOrder(tree);
    printf("\n--------InOrder-----------\n");
    InOrder(tree);
    printf("\n--------PostOrder-----------\n");
    PostOrder(tree);
    printf("\n--------LevelOrder-----------\n");
    LevelOrder(tree);
    return 0;
}
"F:\Computer\Project\practice\14\14.6-tree - cengxubianli\cmake-build-debug\14_4_tree.exe"
abcdefghij
--------PreOrder-----------
abdhiejcfg
--------InOrder-----------
hdibjeafcg
--------PostOrder-----------
hidjebfgca
--------LevelOrder-----------
abcdefghij
进程已结束，退出代码为 0

总结：

  1. 前序遍历也叫深度优先遍历。
  2. 层序遍历也叫层次遍历，也叫广度优先遍历。
  3. 层序遍历使用到了辅助队列。
  4. 每一种遍历方式均使用到了递归的思想。
  5. 前中后序遍历是对于每一棵树来说，按照它的本身，左子树，右子树的相应的顺序打印出来。
  6. 层序遍历是按照树从上到下一层一层打印。

分类：

后端

标签：

C++

作者介绍

江
江小南
V1