创建二叉树是怎么输入？？？？？？？？？？？
[问题点数：20分，结帖人eason_chan]
创建二叉树是怎么输入？？？？？？？？？？？
[问题点数：20分，结帖人eason_chan]
不显示删除回复
显示所有回复
显示星级回复
显示得分回复
只显示楼主
匿名用户不能发表回复！|随笔 - 98&
文章 - 0&评论 - 228&trackbacks - 0
& & &&在看到了这个题。层次遍历是用队列，一级一级地入队列然后输出。而用递归的话，我首先想到是用两个栈来模拟队列，在递归遍历二叉树的过程中入栈，然后最后一次性出栈。但仔细思考后发现无法做到层次遍历。在看到了正确的方法。
& & &主要代码如下:
1 void PrintNodeAtLevel(BiTree T,int level)
// 空树或层级不合理
if (NULL == T || level & 1 )
if (1 == level)
cout && T-&data && "
// 左子树的 level - 1 级
PrintNodeAtLevel(T-&leftChild,
level - 1);
// 右子树的 level - 1 级
PrintNodeAtLevel(T-&rightChild, level - 1);
21 void LevelTraverse(BiTree T)
if (NULL == T)
int depth = Depth(T);
for (i = 1; i &= i++)
PrintNodeAtLevel(T, i);
& & & 这个算法先求出根结点的高度，depth=高度+1。在函数PrintNodeAtLevel中，当且仅当level==1时才进行打印。举个例子:
& & & & &1&
& & 2 & & & &3
4 & & 5 & &6 & 7
& & &这棵树的根的高度是2,depth=3。然后，在LevelTraverse函数中，level从1开始，这会打印出1；之后level=2,进入PrintNodeAtLevel(T-&leftChild, &level - 1)函数和PrintNodeAtLevel(T-&rightChild, level - 1)，level又等于1，就打印出2，3。以此类推，整棵树就按层打印出来了。
& & &参考资料(即此递归算法的来源):http://blog.csdn.net/stpeace/article/details/8138458
& & & 如果你觉得我的文章对你有帮助，请推荐一下，非常感谢!
阅读(...) 评论()数据结构试验（用C语言）建立一棵二叉树，并用递归或者非递归的算法分别用先序。中序和后序遍历、谢谢_百度知道
数据结构试验（用C语言）建立一棵二叉树，并用递归或者非递归的算法分别用先序。中序和后序遍历、谢谢
能附一点实验思路更好
我有更好的答案
#define LEN sizeof(struct tree)#define NULL 0#include&stdio.h&#include&malloc.h&struct tree{
struct tree *lchild,*};//创建二叉树struct tree *creat(){
struct tree *t;
c=getchar();
if(c==' ')
t=(struct tree*)malloc(LEN);
t-&data=c;
t-&lchild=creat();
t-&rchild=creat();
}} //前序遍历void Preprint(struct tree*t) {
if(t!=NULL)
printf(&%c-&&,t-&data);
Preprint(t-&lchild);
Preprint(t-&rchild);
}}//中序遍历void Inprint(struct tree*t)
if(t!=NULL)
Inprint(t-&lchild);
printf(&%c-&&,t-&data);
Inprint(t-&rchild);
}} //后序遍历void Postprint(struct tree*t)
if(t!=NULL)
Postprint(t-&lchild);
Postprint(t-&rchild);
printf(&%c-&&,t-&data);
struct tree *t;
printf(&Please input tree in order:\n&);
t=creat();
printf(&The result of Preorder traversal is\n&);
Preprint(t);
printf(&^\nThe result of Inorder traversal is\n&);
Inprint(t);
printf(&^\nThe result of Postorder traversal is\n&);
Postprint(t);
printf(&^\n&);
采纳率：53%
为您推荐：
其他类似问题
二叉树的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。C语言编写二叉树的建立与遍历_中华文本库
第1页/共3页
C 语言编写二叉树的建立与遍历 100分
浏览:13346
提问时间: 13:19
1.对题目要有需求分析
在需求分析中,将题目中要求的功能进行叙述分析,并且设计解决此问题的数据存储结构, 设计或叙述解决此问题的算法。
给出实现功能的一组或多组测试数据, 程序调试后, 将按照此测试数据进行测试的结果列出 来。
如果程序不能正常运行,写出实现此算法中遇到的问题和改进方法;
2.对题目要有相应的源程序
源程序要按照写程序的规则来编写。 要结构清晰, 重点函数的重点变量, 重点功能部分要加 上清晰的程序注释。 (注释量占总代码的四分之一 )
程序能够运行,要有基本的容错功能。尽量避免出现操作错误时出现死循环;
3.最后提供的主程序可以象一个应用系统一样有主窗口,通过主菜单和分级菜单调用课程 设计中要求完成的各个功能模块, 调用后可以返回到主菜单, 继续选择其他功能进行其他功 能的选择。
二叉树的建立与遍历
[问题描述 ]
建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。 [基本要求 ]
从键盘接受输入,以二叉链表作为存储结构,建立二叉树,并对其进行遍历(先序、中 序、后序),将遍历结果打印输出。
以下是我的数据结构实验的作业:肯定好用, 里面还包括了统计树的深度和叶子数! 记住每 次做完一个遍历还要重新输入你的树哦!
#include "stdio.h"
#include "string.h"
#define NULL 0
typedef struct BiTNode{
struct BiTNode *lchild,*
}BiTNode,*BiT
BiTree Create(BiTree T){
ch=getchar();
if(ch=='#')
if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))
printf("Error!");
T-&lchild=Create(T-&lchild);
T-&rchild=Create(T-&rchild);
第1页/共3页
寻找更多 ""C++二叉树结构的建立与基本操作_C 语言
作者：用户
本文讲的是C++二叉树结构的建立与基本操作_C 语言，
准备数据定义二叉树结构操作中需要用到的变量及数据等。
复制代码 代码如下:
#define MAXLEN 20
//最大长度typedef char DATA;
//定义元素类型struct
准备数据定义二叉树结构操作中需要用到的变量及数据等。
复制代码 代码如下:
#define MAXLEN 20
//最大长度typedef char DATA;
//定义元素类型struct
//定义二叉树结点类型 { DATA
//元素数据
//左子树结点指针
//右子树结点指针 };
定义二叉树结构数据元素的类型DATA以及二叉树结构的数据结构CBTType。结点的具体数据保存在一个姐都DATA中，而指针left用来指向左子树结点，指针right用来指向右子树结点
初始化二叉树初始化二叉树，将一个结点设置为二叉树的根结点。
复制代码 代码如下:
CBTType * InitTree(){ CBTType * if(node = new CBTType)
//申请内存
cout&&"请先输入一个根节点数据："&&
cin&&node-&
node-&left=NULL;
node-&right=NULL;
if(node!=NULL)
//如果二叉树结点不为空
return NULL;
} } return NULL;}
首先申请一个结点，然后用户输入根结点 的数据，并将左子树和右子树的指针置为空，即可完成二叉树的初始化工作。
查找结点就是遍历二叉树中的每一个节点，逐个比较数据，当找到目标数据时将返回该数据所在结点的指针。
复制代码 代码如下:
CBTType *TreeFindNode(CBTType *treeNode,DATA data){ CBTType * if(treeNode==NULL) {
return NULL; }else {
if(treeNode-&data==data)
return treeN
//分别向左右子树查找
if(ptr=TreeFindNode(treeNode-&left,data))
//左子树递归查找
else if(ptr=TreeFindNode(treeNode-&right,data))
//右子树递归查找
return NULL;
输入参数treeNode为待查找的二叉树的根结点，输入参数data为待查找的结点数据。程序中首先判断根结点是否为空，然后根据数据判断是否为根结点，然后分别向左右子树进行查找，采用递归的方法进行查找，查找到该结点则返回结点对应的指针；如果全都查找不到，则返回NULL。
添加结点添加结点就是在二叉树中添加结点数据，添加结点时除了要输入结点数据外，还需要指定其父结点，以及添加的结点作为左子树还是右子树。然后将该结点置为其父结点的左子树或者右子树。
复制代码 代码如下:
void AddTreeNode(CBTType *treeNode){ CBTType *pnode,* DATA if(pnode=new CBTType)
//分配内存
cout&&"输入二叉树结点数据："&&
cin&&pnode-&
pnode-&left=NULL;
//设置左子树为空
pnode-&right=NULL;
//设置左子树为空
cout&&"输入该结点的父结点数据"&&
parent=TreeFindNode(treeNode,data);//查找父结点，获得结点指针
if(!parent)
cout&&"没有找到父结点"&&
cout&&"1.添加该结点到左子树；2.添加该结点到右子树。请输入操作对应的数字。"&&
if(menusel=='1'||menusel=='2')
switch(menusel)
//添加结点到左子树
if(parent-&left)
//左子树不为空
cout&&"左子树结点不为空"&&
parent-&left=
cout&&"数据添加成功！"&&
//添加结点到右子树
if(parent-&right)
//右子树不为空
cout&&"右子树结点不为空"&&
parent-&right=
cout&&"数据添加成功！"&&
cout&&"子节点选择error!"&&
}while(menusel!='1'&&menusel!='2'); }}
输入参数treeNode为二叉树的根结点，传入根节点是为了方便查找父结点。程序中首先申请内存，然后由用户输入二叉树结点数据，并设置左右子树为空。接着指定其父结点，将其置为左子树或者右子树。
二叉树的深度计算二叉树深度就是计算二叉树中结点的最大层数，这里往往需要采用递归算法来实现。
复制代码 代码如下:
int TreeDepth(CBTType *treeNode){ int depleft, if(treeNode==NULL) {
//结点为空的时候，深度为0
depleft=TreeDepth(treeNode-&left);
//左子树深度（递归调用）
depright=TreeDepth(treeNode-&right);
//右子树深度（递归调用）
if(depleft)
输入参数treeNode为待计算的二叉树的根结点。首先判断根节点是否为空，然后分别按照递归调用来计算左子树深度和右子树深度，从而完成整个二叉树深度的计算。
显示结点数据
复制代码 代码如下:
void ShowNodeData(CBTType *treeNode){ cout&&treeNode-&data&&"\t";
//直接输出结点数据 }
输入参数为需要显示的结点的指针。
清空二叉树清空二叉树就是将二叉树变成一个空树，这里也需要使用递归算法来实现。
复制代码 代码如下:
void ClearTree(CBTType *treeNode){ if(treeNode)
//判断当前树不为空
ClearTree(treeNode-&left);
//清空左子树
ClearTree(treeNode-&right);
//清空右子树
delete treeN
//释放当前结点所占用的内存
输入参数treeNode为待清空的二叉树的根节点。程序中按照递归的方法清空左子树和右子树以及根节点，释放结点占用的内存空间，从而完成清空操作。
遍历二叉树遍历二叉树就是逐个查找二叉树中所有的结点，这里为了直观的显示查找的结果，将会按照查找的顺序，依次输出对应的结点 。
按层遍历算法按层遍历算法是最直观的算法。即：首先输出第一层即根结点，然后输出第一个结点的左右子数，也就是第二层……这样循环处理，就可以逐层遍历，一层一层按照从上到下，从左到右的顺序输出结点。
复制代码 代码如下:
void LevelTree(CBTType *treeNode){ CBTType *p; CBTType *q[MAXLEN];
//定义一个队列
int head=0,tail=0; if(treeNode)
//如果队首指针不为空 {
tail=(tail+1)%MAXLEN;
//计算循环队列队尾序号
q[tail]=treeN
//二叉树根指针进入队列
while(head!=tail)
head=(head+1)%MAXLEN;
//计算循环队列的队首序号
p=q[head];
//获取队首元素
ShowNodeData(p);
//输出队首元素
if(p-&left!=NULL)
//如果存在左子树
tail=(tail+1)%MAXLEN;
//计算队列的队尾序号
q[tail]=p-&
//左子树入队
if(p-&right!=NULL)
//如果存在右子树
tail=(tail+1)%MAXLEN;
//计算队列的队尾序号
q[tail]=p-&
//右子树入队
输入参数treeNode为需要遍历的二叉树的根结点，程序在整个处理过程中，首先从根节点开始，将每层的结点逐步进入循环队列，并且每次循环都是输出队首的一个结点数据，然后再使它的左右子树进入队列。如此循环直到队列中的所有的数据都输出完毕。
先序遍历算法先序遍历算法就是先访问根节点，然后访问左子树，然后访问右子树。程序中可以按照递归的思想遍历左子树和右子树。
复制代码 代码如下:
void DLRTree(CBTType *treeNode){ if(treeNode) {
ShowNodeData(treeNode);
//显示结点内容
DLRTree(treeNode-&left);
//显示左子树内容
DLRTree(treeNode-&right);
//显示右子树内容
中序遍历算法先序遍历算法就是先访问左子树，然后访问根节点，然后访问右子树。程序中可以按照递归的思想遍历左子树和右子树。
复制代码 代码如下:
void LDRTree(CBTType *treeNode){ if(treeNode) {
LDRTree(treeNode-&left);
//显示左子树内容
ShowNodeData(treeNode);
//显示结点内容
DLRTree(treeNode-&right);
//显示右子树内容
后序遍历算法先序遍历算法就是先访问左子树，然后访问右子树，然后访问根节点。程序中可以按照递归的思想遍历左子树和右子树。
复制代码 代码如下:
void LRDTree(CBTType *treeNode){ if(treeNode) {
LRDTree(treeNode-&left);
//显示左子树内容
DLRTree(treeNode-&right);
//显示右子树内容
ShowNodeData(treeNode);
//显示结点内容 } }
完整代码示例操作：
在文件中加入头文件，然后包含上述所有函数，然后再写一个main函数即可：
复制代码 代码如下:
#include&iostream& #define MAXLEN 20
//最大长度typedef char DATA;
//定义元素类型struct
/定义二叉树结点类型 { DATA
//元素数据
//左子树结点指针
//右子树结点指针 };/*********************初始化二叉树***********************/CBTType * InitTree(){ CBTType * if(node = new CBTType)
//申请内存
cout&&"请先输入一个根节点数据："&&
cin&&node-&
node-&left=NULL;
node-&right=NULL;
if(node!=NULL)
//如果二叉树结点不为空
return NULL;
} } return NULL;}/***********************查找结点*************************/CBTType *TreeFindNode(CBTType *treeNode,DATA data){ CBTType * if(treeNode==NULL) {
return NULL; }else {
if(treeNode-&data==data)
return treeN
//分别向左右子树查找
if(ptr=TreeFindNode(treeNode-&left,data))
//左子树递归查找
else if(ptr=TreeFindNode(treeNode-&right,data))
//右子树递归查找
return NULL;
} } } /**********************添加结点*************************/void AddTreeNode(CBTType *treeNode){ CBTType *pnode,* DATA if(pnode=new CBTType)
//分配内存
cout&&"输入二叉树结点数据："&&
cin&&pnode-&
pnode-&left=NULL;
//设置左子树为空
pnode-&right=NULL;
//设置左子树为空
cout&&"输入该结点的父结点数据"&&
parent=TreeFindNode(treeNode,data);
//查找父结点，获得结点指针
if(!parent)
cout&&"没有找到父结点"&&
cout&&"1.添加该结点到左子树；2.添加该结点到右子树。请输入操作对应的数字。"&&
if(menusel=='1'||menusel=='2')
switch(menusel)
//添加结点到左子树
if(parent-&left)
//左子树不为空
cout&&"左子树结点不为空"&&
parent-&left=
cout&&"数据添加成功！"&&
//添加结点到右子树
if(parent-&right)
//右子树不为空
cout&&"右子树结点不为空"&&
parent-&right=
cout&&"数据添加成功！"&&
cout&&"子节点选择error!"&&
}while(menusel!='1'&&menusel!='2'); }} /***********************计算二叉树的深度********************************/int TreeDepth(CBTType *treeNode){ int depleft, if(treeNode==NULL) {
//结点为空的时候，深度为0
depleft=TreeDepth(treeNode-&left);
//左子树深度（递归调用）
depright=TreeDepth(treeNode-&right);
//右子树深度（递归调用）
if(depleft)
}} /*************************显示结点数据*********************************/void ShowNodeData(CBTType *treeNode){ cout&&treeNode-&data&&"\t";
//直接输出结点数据 } /***********************清空二叉树************************************/void ClearTree(CBTType *treeNode){ if(treeNode)
//判断当前树不为空
ClearTree(treeNode-&left);
//清空左子树
ClearTree(treeNode-&right);
//清空右子树
delete treeN
//释放当前结点所占用的内存
}} /**************************按层遍历算法*********************************/void LevelTree(CBTType *treeNode){ CBTType *p; CBTType *q[MAXLEN];
//定义一个队列
int head=0,tail=0; if(treeNode)
//如果队首指针不为空 {
tail=(tail+1)%MAXLEN;
//计算循环队列队尾序号
q[tail]=treeN
//二叉树根指针进入队列
while(head!=tail)
head=(head+1)%MAXLEN;
//计算循环队列的队首序号
p=q[head];
//获取队首元素
ShowNodeData(p);
//输出队首元素
if(p-&left!=NULL)
//如果存在左子树
tail=(tail+1)%MAXLEN;
//计算队列的队尾序号
q[tail]=p-&
//左子树入队
if(p-&right!=NULL)
//如果存在右子树
tail=(tail+1)%MAXLEN;
//计算队列的队尾序号
q[tail]=p-&
//右子树入队
} } /*************************先序遍历算法**********************************/void DLRTree(CBTType *treeNode){ if(treeNode) {
ShowNodeData(treeNode);
//显示结点内容
DLRTree(treeNode-&left);
//显示左子树内容
DLRTree(treeNode-&right);
//显示右子树内容
}} /***********************中序遍历算法************************************/void LDRTree(CBTType *treeNode){ if(treeNode) {
LDRTree(treeNode-&left);
//显示左子树内容
ShowNodeData(treeNode);
//显示结点内容
DLRTree(treeNode-&right);
//显示右子树内容
} } /***********************后序遍历算法************************************/void LRDTree(CBTType *treeNode){ if(treeNode) {
LRDTree(treeNode-&left);
//显示左子树内容
DLRTree(treeNode-&right);
//显示右子树内容
ShowNodeData(treeNode);
//显示结点内容 } } /*************************主函数部分************************************/int main(){ CBTType *root=NULL;
//root为指向二叉树根结点的指针 //设置根结点 root=InitTree(); //添加结点 do {
cout&&"请选择菜单添加二叉树的结点："&&
cout&&"0.退出;1.添加二叉树的结点。"&&
switch(menusel)
AddTreeNode(root);
cout&&"添加结点error"&&
} }while(menusel!='0');
//输出树的深度
cout&&"depth:"&&TreeDepth(root)&& //输出结点内容 do {
cout&&"请选择菜单遍历二叉树，输入0表示退出："&&
cout&&"1.按层遍历"&&
cout&&"2.先序遍历DLR"&&
cout&&"3.中序遍历LDR"&&
cout&&"4.后序遍历LRD"&&
switch(menusel)
cout&&"按层遍历的结果："&&
LevelTree(root);
cout&&"先序遍历的结果："&&
DLRTree(root);
cout&&"中序遍历的结果："&&
LDRTree(root);
cout&&"后序遍历的结果："&&
LRDTree(root);
cout&&"遍历方式选择出错！"&&
} }while(menusel!='0'); //清空二叉树
ClearTree(root); return 0;
对应的树形结构图如图：
程序运行界面：
以上是云栖社区小编为您精心准备的的内容，在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索c++
c语言二叉树的建立、c语言建立二叉树、c语言先序建立二叉树、递归建立二叉树c语言、数据结构二叉树的建立，以便于您获取更多的相关知识。
弹性可伸缩的计算服务，助您降低 IT 成本，提升运维效率
40+云计算产品，6个月免费体验
稳定可靠、可弹性伸缩的在线数据库服务，全球最受欢迎的开源数据库之一
云服务器9.9元/月，大学必备
云栖社区(yq.aliyun.com)为您免费提供相关信息，包括
，所有相关内容均不代表云栖社区的意见！