数据结构之树-二叉树的建立及遍历算法（二）-学习笔记-55

引入

上一节，我们详细说明了二叉树的 4 种遍历方式，根据根的位置不同，我们分为前序遍历、中序遍历和后序遍历以及最常用的层序遍历。今天我们就来实战一下， 看看如何建立一棵树，并且按照我们需要的方式遍历树上的结点。

需求

• 根据输入建立一棵二叉树
• 输出其前序遍历、中序遍历和后序遍历结果

代码分析

首先要构建一棵树，因为是二叉树，所以结构体中包含左右两棵子树

• 存放数据的data
• 存放左右子树的指针域

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

struct BiTNode{
    char data;   //用于存放结点数据
    struct BiTNode *Lchild;   //存放左孩子地址
    struct BiTNode *Rchild;   //存放右孩子地址
};

接着，我们开始创建树，我们使用的是返回树根节点地址的方式

• 先创建一个临时结点
• 在创建一个临时 char 变量，用于存放用户输入的内容
• scanf 让用户输入内容，将值赋值给 char 变量
• 如果输入的是#号，则表示结点为空
• 如果不为空，则将这个结点看成根，将输入的值赋予根结点
• 接着将这个根的左右子树通过递归获取到
• 将所有的叶子结点都输入为#后，即所有结点都是 NULL ，没有左右子树，树创建完成。

struct BiTNode *Create(void){
    struct BiTNode *tempTree;
    char tempC;
    scanf("%c",&tempC);
    if(tempC=='#'){   //如果结点为空，那么就赋值为 NULL
        tempTree=NULL;
    }else{
    //如果结点不为空，那就生成动态存储空间
        tempTree=(struct BiTNode *)malloc(LEN);
        //我们默认输入的时候按照前序遍历输入，所以先存储结点值，然后左右子树遍历
        tempTree->data=tempC;
        tempTree->Lchild=Create();  //左子树递归
        tempTree->Rchild=Create();  //右子树递归
    }
    return tempTree;  //返回根结点地址
}

树的遍历，我们使用递归的思路，其实很好遍历

• 前序遍历是，根在前面，所以是中左右，所以先输出 data，再递归左右子树
• 中序遍历是，根在中间，所以是左中右，所以先递归左子树，再输出 data，再递归右子树
• 后序遍历是，根在后面，所以是左右中，所以先递归左右子树，再输出 data。
• 我们判断条件也非常简单，只要结点不为 NULL，就执行！

void PreVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        printf("%c",Temptree->data);
        PreVisitTree(Temptree->Lchild);
        PreVisitTree(Temptree->Rchild);
    }
}

void InVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        InVisitTree(Temptree->Lchild);
        printf("%c",Temptree->data);
        InVisitTree(Temptree->Rchild);
    }
}

void PostVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        PostVisitTree(Temptree->Lchild);
        PostVisitTree(Temptree->Rchild);
        printf("%c",Temptree->data);
    }
}

主调 Main 函数

• 首先创建一个树指针，用于存放生成好的树。
• 然后使用前序、中序、后续遍历的函数，分别调用这棵树。
• 输出的结果就是这棵树的前序、中序、后续遍历了。

int main(){
    struct BiTNode * tree;
    printf("请输入结点：\n");
    tree=Create();
    PreVisitTree(tree);
    printf("\n");
    InVisitTree(tree);
    printf("\n");
    PostVisitTree(tree);
    printf("\n");
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#define LEN sizeof(struct BiTNode)

struct BiTNode{
    char data;
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
};


struct BiTNode *Create(void){
    struct BiTNode *tempTree;
    char tempC;
    scanf("%c",&tempC);
    if(tempC=='#'){
        tempTree=NULL;
    }else{
        tempTree=(struct BiTNode *)malloc(LEN);
        tempTree->data=tempC;
        tempTree->Lchild=Create();
        tempTree->Rchild=Create();
    }
    return tempTree;
}

void PreVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        printf("%c",Temptree->data);
        PreVisitTree(Temptree->Lchild);
        PreVisitTree(Temptree->Rchild);
    }
}

void InVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        InVisitTree(Temptree->Lchild);
        printf("%c",Temptree->data);
        InVisitTree(Temptree->Rchild);
    }
}

void PostVisitTree(struct BiTNode *Temptree){
    if(Temptree){
        PostVisitTree(Temptree->Lchild);
        PostVisitTree(Temptree->Rchild);
        printf("%c",Temptree->data);
    }
}

int main(){
    struct BiTNode * tree;
    printf("请输入前序结点：\n");
    tree=Create();
    PreVisitTree(tree);
    printf("\n");
    InVisitTree(tree);
    printf("\n");
    PostVisitTree(tree);
    printf("\n");
}

输出结果
请输入前序结点：
ABDH##I##E#J##CF#K##G##
ABDHIEJCFKG
HDIBEJAFKCG
HIDJEBKFGCA

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。