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

2020-07-08  本文已影响0人  哪有岁月静好

一、运行环境简介

编辑器: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,不管你是小白还是转行人士欢迎入驻,大家一起交流成长。



上一篇下一篇

猜你喜欢

热点阅读