二叉树(Binary Tree)的建立与遍历——C语言实现

一、运行环境简介

编辑器：VSCode + MicroSoft原生插件;

:cat:‍:dragon:运行环境： MinGW ;

:cat:‍:bust_in_silhouette:常用指令： gcc mian.c -o mian.exe

二、二叉树的定义

这里我们直接采用浙大数据结构课程中的代码。因为这种写法清晰明了，且便于后续扩展。

typedef char ElementType;

typedef struct TNode *Position; /* 结构体指针 */
typedef Position BinTree; /* 二叉树类型 */
struct TNode{ /* 树结点定义 */
    ElementType Data; /* 结点数据 */
    BinTree Left;     /* 指向左子树 */
    BinTree Right;    /* 指向右子树 */
}TNode;
复制代码

三、如何创建一个二叉树？

先看代码再分析

void CreateBinaryTree ( BinTree *T ) {
    ElementType ch;
    scanf("%c",&ch);

    if (ch == '#')
        *T = NULL;
    else {
        *T = (BinTree)malloc(sizeof(TNode));
        (*T)->Data = ch;
        CreateBinaryTree(&((*T)->Left));
        CreateBinaryTree(&((*T)->Right));
    }
}
复制代码

1.解决此函数的形参疑问

我们知道，二叉树的类型被我们定义为 BinTree ，而它的原类型是指向二叉树结点 TNode 的指针。我一开始犯的错误是，我认为直接传入这里的指针 BinTree 给函数 CreateBinaryTree() 就可以得到创建的二叉树。事实上这里需要传入指针的指针，即这个结构体指针的地址 *BinTree 。 也就是说，我们事实上传入的是 ** TNode ，即结点指针的指针。而采用上面的定义，就相当于是一个降维的过程，我们可以少写一个*。

为什么要传入结点指针的指针呢？我的理解是，我们所使用的数据结构二叉树在基本操作中就依赖于指针，这相当于我们一开始就在操控指针（比如不修改二叉树的一些操作——先序中序后序遍历中，我们用到了指针），但这些指针是包含在二叉树这个类型中的，打个比方，就相当于一个没有取得其地址的普通类型。所以我们需要修改二叉树的时候，我们要考虑取所谓“普通类型”的地址，即我们要取指针的地址，因此我们会在 CreateBinaryTree() 中传入结点指针的指针，即 ** TNode ，又即 *Bintree 。

2.对代码的一些说明

这里建立的二叉树，实际上是扩展二叉树，这里采用先序遍历的顺序依次输入结点的值（ char 类型），用 '#' 代表空结点。

例如：创建二叉树：第一层为A，第二层为B、C，第三层为D、F，D为B的左孩子，F为C的右孩子；我们需要输入 ABD###C#F## ；

四、二叉树的遍历——递归实现

3种递归实现仅仅是输出语句顺序不同。

其实现原理为

二叉树的先中后序遍历中经过的结点路径是一样的，但是访问各结点的时机不同，每个结点都会被经过三次，第一次经过就printf是先序，同理第二次printf是中序，第三次是后序。

1.先序遍历

void PreOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        printf("%c", BT->Data);
        PreOrderTraversal( BT->Left );
        PreOrderTraversal( BT->Right );
    }
}
复制代码

2.中序遍历

void InOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        PreOrderTraversal( BT->Left );
        printf("%c", BT->Data);
        PreOrderTraversal( BT->Right );
    }
}
复制代码

3.后序遍历

void PostOrderTraversal ( BinTree BT ) {
    if ( BT ) {
        PostOrderTraversal( BT->Left );
        PostOrderTraversal( BT->Right );
        printf("%c", BT->Data);
    }
}
复制代码

五、其他操作

1.先序遍历输出二叉树叶子结点

void PreOrderPrintLeaves ( BinTree BT ) {
    if ( BT ) {
        if ( !BT->Left && !BT->Right )
            printf("%c", BT->Data);
    PreOrderPrintLeaves( BT->Left );
    PreOrderPrintLeaves( BT->Right );
    }
}
复制代码

2.后序遍历求二叉树的高度

int PostOrderGetHeight ( BinTree BT) {
    int HL, HR, MaxH;

    if ( BT ) {
        HL = PostOrderGetHeight( BT->Left );
        HR = PostOrderGetHeight( BT->Right );
        MaxH = ( HL > HR ) ? HL : HR;
        return (MaxH + 1);
    }
    else
        return 0;
}
复制代码

六、测试

程序结构：

头文件为BTree.h，里面包含上述代码。主要程序文件为main.c，包含代码如下：

#include<stdio.h>
#include<stdlib.h>
#include"BTree.h"

int main() {
  BinTree myTree;
  printf("Create your Binary Tree:\n");
  CreateBinaryTree(&myTree);
  printf("\n PreOrder:");
  PreOrderTraversal(myTree);
  printf("\n InOrder:");
  InOrderTraversal(myTree);
  printf("\n PostOrder:");
  PostOrderTraversal(myTree);
  printf("\n Leaves:");
  PreOrderPrintLeaves(myTree);
  printf("\n");
  int high = PostOrderGetHeight(myTree);
  printf("The height of the tree: %4d", high);
  return 0;
}
复制代码

测试结果如下：

image

其实做为一个学习者，有一个学习的氛围跟一个交流圈子特别重要这里我推荐一个C/C++基础交流583650410，不管你是小白还是转行人士欢迎入驻，大家一起交流成长。