C++实现先序创建二叉树，并用递归和非递归两种方式二叉树中序遍历

您所在的位置：网站首页 › 中序遍历和先序遍历构建二叉树 › C++实现先序创建二叉树，并用递归和非递归两种方式二叉树中序遍历

C++实现先序创建二叉树，并用递归和非递归两种方式二叉树中序遍历

2024-07-16 10:45:59| 来源: 网络整理| 查看: 265

这是数据结构课堂留下的一个作业：题目是：按先序次序输入二叉树中的结点的值（data为字符类型），以’#'表示空字符，创建二叉链表示二叉树。函数原型如下： void CreateBiTree(BiTree *T)；//创建二叉树函数 void InOrderTraverse(BiTree T); //利用栈以非递归的方式实现中序遍历上述二叉树二叉链表的定义如下：

typedef struct BiTNode{ char data; struct BiNode *lchild,*rchild; }BiTNode,*BiTree; //这里将BiTNode和BiTree声明为struct BiTNode和struct BiTNode*的别名

代码运行实例：在这里插入图片描述于是按照题目的要求写了第一个版本的代码（问题主要出现在二叉树的创建上，这里先不贴中序遍历的代码）：

#include #include using namespace std; //定义二叉链表的结构体 typedef struct BiTNode { char data; //用来存储数据 struct BiTNode* lchild, * rchild; //左右子树 }BiTNode, * BiTree; //函数声明 void CreateBiTree(BiTree *T); int main() { cout *T = NULL; } else { *T = (BiTNode*)malloc(sizeof(BiTNode)); (*T)->data = ch; CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } }

在上述的代码中，由于题目中传给 CreateBiTree(BiTree *T) 函数的参数是指向 BiTree 的指针，而根据 Typedef 的定义 BiTree 本身就是指向 struct BiTNode 的指针类型，于是 BiTree *T 就成为了指向 struct BiTNode 的指针的指针，所以创建二叉树的代码就变成了 (*T)->data = ch 和 CreateBiTree(&(*T)->lchild) 风格，虽然能够运行，但是有种“多此一举”的感觉。（这是因为C语言中没有引用，而创建二叉树需要修改参数BiTree T本身，所以就需要使用BiTree *T作为参数）。于是出现了第二个版本：

CreateBiTree(BiTree T);//调用函数 void CreateBiTree(BiTree T) { char ch; cin >> ch; if (ch == '#') { T = NULL; } else { T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }

直接将 BiTree 作为函数的参数，虽然这样做程序能够运行，但是 BiTree T 作为实参调用 CreateBiTree() 函数后，其仍然为空指针，也就是说二叉树没有建立成功，原因是此时的形参是 BiTree 类型的变量，实参也是 BiTree 类型的变量，而用指针作为函数参数时能够改变的是指针所指之物，而无法改变指针本身，因此二叉树没有建立成功。最后的版本是将 BiTree 的引用作为函数的形参，而引用作为形参时，其值的改变可以引起实参值的改变。此时二叉树成功的建立了。

CreateBiTree(T); //调用函数 void CreateBiTree(BiTree &T) { char ch; cin >> ch; if (ch == '#') { T = NULL; } else { T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } }

最后附上完整的代码：

#include #include #include using namespace std; //定义二叉链表的结构体 typedef struct BiTNode { char data; //用来存储数据 struct BiTNode* lchild, * rchild; //左右子树 }BiTNode, * BiTree; //函数声明 void CreateBiTree(BiTree &T); void InOrderTraverse(BiTree T); int main() { cout T = NULL; } else { T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } } //利用递归的方式二叉树的中序遍历 void InOrderTraverse(BiTree T){ if(T==NULL) return OK; else{ InOrderTraverse(T->lchild); cout rchild); } } //利用栈实现非递归二叉树中序遍历 void InOrderTraverse(BiTree T) { stack S; //初始化栈 BiTree p = T; while (p || !S.empty()) { //根指针进栈，遍历左子树 if (p) { S.push(p); p = p->lchild; } //根指针退栈，访问根结点，遍历右子树 else { p = S.top(); S.pop(); cout rchild; } } }

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

C++实现先序创建二叉树，并用递归和非递归两种方式二叉树中序遍历

C++实现先序创建二叉树，并用递归和非递归两种方式二叉树中序遍历

今日新闻

点击排行

推荐新闻

图片新闻

专题文章