递归创建及遍历输出二叉树

2024-07-13 19:35| 来源: 网络整理| 查看: 265

利用二叉树的链式存储结构

声明结构体

typedef struct BTNode{ char data;//节点中数据存放位置 struct BTNode *lchild;//左孩子 struct BTNode *rchild;//右孩子 }BTNode,*BinTree;

先序(根左右)创建二叉树，利用递归实现

首先定义退出条件，这里我声明的是遇到空格结束，节点左（右）孩子指向空指针，并且退出当前函数接下来进入建树主体环节由于是先序建树，先赋值给BT（也就是当前节点），然后进入递归，可以思考到在逻辑中，指针会一直赋值并且向左边跑，直到遇到第一个空格，退出最末一重函数（下图中的⑤），接下来进入右递归，会发现右递归第一次会遇到空格，于是退出当前一重函数（下图中的⑥），接下来给D（下图）赋值在这里插入图片描述

先序创建二叉树

bool CreatBinTree_PreOrder(BinTree &BT){//先序创建二叉树 char Symbol; scanf("%c",&Symbol); if (Symbol == ' '){//遇到停止 BT = NULL; return false; }else{ BT = (BinTree)malloc(sizeof(BTNode)); BT->data = Symbol;//根 CreatBinTree_PreOrder(BT->lchild);//左 CreatBinTree_PreOrder(BT->rchild);//右 } return true; }

接下来三种遍历输出二叉树

先序遍历（根左右）输出二叉树原理与上文提到的先序创建二叉树相似，同样是递归调用，visit函数仅仅为了显示数据使用，但是根据调用visit函数的位置不同，遍历分为先序，中序，后序同样的，利用递归遍历，先定义退出条件，当参数指针指向NULL时（也就是上文中的输入遇到空格，使指针指向空，并且退出一层调用），退出一层调用，执行下一函数，如下图中的③④⑤步骤，也就是接下来执行display_BinTree_PreOrder(BT->rchild); 语句段，然后在步骤⑤，发现传入的参数指针依然指向NULL，随即执行步骤⑥，此时已经退出了C的一层，接下来的步骤类似在这里插入图片描述

visit函数（也就是打印数值的作用）

void visit(BinTree BT){ printf("%c ",BT->data); return; }

先序遍历输出二叉树

void display_BinTree_PreOrder(BinTree BT){//先序遍历打印二叉树 if (BT==NULL){ return; }else{ visit(BT); display_BinTree_PreOrder(BT->lchild); display_BinTree_PreOrder(BT->rchild); } }

中序遍历（左根右）输出二叉树输出 CBDAE

中序遍历输出二叉树

void display_BinTree_InOrder(BinTree BT){//中序遍历打印二叉树 if (BT==NULL){ return; }else{ display_BinTree_InOrder(BT->lchild); visit(BT); display_BinTree_InOrder(BT->rchild); } }

后序遍历（左右根）输出二叉树

后序遍历输出二叉树在这里插入图片描述

void display_BinTree_PostOrder(BinTree BT){//后序遍历打印二叉树 if (BT==NULL){ return; }else{ display_BinTree_PostOrder(BT->lchild); display_BinTree_PostOrder(BT->rchild); visit(BT); } }

运行结果如下所示输入ABC##D##E##（用空格代替#）在这里插入图片描述

【本文地址】

公司简介

联系我们