自学到二叉树的时候,有一段关于遍历二叉树的代码看不懂..
这是中序遍历二叉树。
按左子结点，父结点，右子结点顺序输出。
函数分为三个部分。
第一个部分if（pNode-》pLeft）
{…..；}
这个意思是说，如果头结点的左子不为空，也就是说如果父结点有左子结点的话。
进入递归。函数的实参是父结点的左子结点。
再看这个结点有没有左子结点。如果有，继续递归，实参是这个结点的左子结点。
一直到某个结点的左子为空了，也就是没有左子了，这个时候当前执行的函数就进入下一个部分了。
下一个部分是输出这个结点的数据。
然后就是最后一个部分，递归父节点的右子。（如果有右子的话）
不过还是得先看当前结点有没有左子，如果有，递归，如果没有，输出结点数据。然后判断右子。
看图，输出的是应该是cbdafeg。
第一次①a结点，进入函数判断有没有左子，有，递归到b，②判断有没有左子，有，递归到c，③判断有没有左子，没有，输出c。判断有没有右子，没有。这个函数结束。返回到调用它的函数②里，这时候第一部分已经执行完毕（即使③），执行输出b，然后判断有没有右子，有，递归到d。④判断有没有左子，没有，输出d，判断有没有右子，没有，返回函数②，这时候函数②三个部分执行完毕，返回到函数①，这时候函数①也只是执行完第一部分，然后输出a。然后判断有没有右子，有。然后不就不往下说了。
二叉树的遍历的完整代码是什么
二叉树遍历代码
#include“iostream.h“
#include“stdlib.h“
#include“stdio.h“
#include《stack》
using namespace std;
#define NULL 0
#define OK 1
#define OVERFLOW -1
typedef int Status;
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}*bitree;
int k=0;
int depth(bitree T)//树的高度
{
if(!T)return 0;
else
{
int m=depth(T-》lchild); int n=depth(T-》rchild); return (m》n?m:n)+1;
}
}
//先序，中序 建树
struct node *create(char *pre,char *ord,int n) {
struct node * T;
int m;
T=NULL;
if(n《=0)
{
return NULL;
}
else
{
m=0;
T=new(struct node);
T-》data=*pre;
T-》lchild=T-》rchild=NULL; while(ord[m]!=*pre)
m++;
T-》lchild=create(pre+1,ord,m);
T-》rchild=create (pre+m+1,ord+m+1,n-m-1); return T;
}
}
//中序递归遍历
void inorder(struct node *T)
{
if(!T)
return;
else
{
inorder(T-》lchild );
cout《《T-》data;
inorder(T-》rchild );
}
}
void inpre(struct node *T)
{
if(!T)
return;
else
{
cout《《T-》data;
inpre(T-》lchild );
inpre(T-》rchild );
}
}
void postorder(struct node *T)
{
if(!T)
return;
else
{
postorder (T-》lchild );
postorder (T-》rchild );
cout《《T-》data;
}
}
//先序非递归遍历
void inpre1(struct node *T)
第2/4页
{
struct node *p;
struct node *stack;
int top=0;
p=T;
cout《《“非递归先序为:“《《endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
cout《《p-》data;
p=p-》lchild;
}
p=stack[–top];
p=p-》rchild ;
}
}
//中序非递归遍历
void inorder1(struct node *T)
{
struct node *p;
struct node *stack;
int top=0;
p=T;
cout《《“非递归中序为:“《《endl;
while(p||top!=0)
{
while (p)
{
stack[top++]=p;
p=p-》lchild ;
}
p=stack[–top];
cout《《p-》data;
p=p-》rchild ;
}
}
//主函数
int main()
{
bitree T;
char pre,ord;
第3/4页
int n,m;
cout《《“请输入先序为-+a*b%cd/ef的二叉树:“《《endl; gets(pre);
cout《《“请输入中序为a+b*c%d-e/f的二叉树:“《《endl; gets(ord);
n=strlen(pre);
T=create(pre,ord,n);
cout《《 “后序遍历为:“《《endl;
postorder (T);
cout《《endl;
inpre1(T);
cout《《endl;
inorder1(T);
cout《《endl;
m=depth(T);
cout《《“二叉树高度为：“《《m《《endl;
return 0;
}
如何实现二叉树的遍历
二叉树的遍历
在遍历二叉树的过程中，一般先遍历左子树，再遍历右子树。
（1）前序遍历
先访问根结点，然后遍历左子树，最后遍历右子树；并且在遍历左、右子树时，仍需先访问根结点，然后遍历左子树，最后遍历右子树。
（2）中序遍历
先遍历左子树、然后访问根结点，最后遍历右子树；并且，在遍历左、右子树时，仍然先遍历左子树，然后访问根结点，最后遍历右子树。
（3）后序遍历
先遍历左子树、然后遍历右子树，最后访问根结点；并且，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后访问根结点。
关于二叉树的递归与非递归遍历代码（主要是非递归后序）
二叉树的遍历是指按照一定次序访问二叉树中的所有节点，且每个节点仅被访问一次的过程。是最基本的运算，是其他运算的基础。二叉树有两种存储结构：顺序存储和链式存储顺序存储：（对完全二叉树来说，可以充分利用存储空间，但对于一般的二叉树，只有少数的存储单元被利用）[cpp]viewplaincopytypedefstruct{ElemTypedata[MaxSize];intn;}SqBTree;链式存储：[csharp]viewplaincopytypedefstructnode{ElemTypedata;structnode*lchild;structnode*rchild;}BTNode;二叉树三种递归的遍历方法：先序遍历访问根节点→先序遍历左子树→先序遍历右子树中序遍历中序遍历左子树→访问根节点→中序遍历右子树后序遍历后序遍历左子树→后序遍历右子树→访问根节点二叉树遍历的递归算法：[cpp]viewplaincopyvoidpreOrder(BTNode*b)//先序遍历递归算法{if(b!=NULL){visit(b);preOrder(b-》lchild);preOrder(b-》rchild);}}voidInOrder(BTNode*b)//中序遍历递归算法{if(b!=NULL){InOrder(b-》lchild);visit(b);InOrder(b-》rchild);}}voidPostOrder(BTNode*b)//后序遍历递归算法{if(b!=NULL){PostOrder(b-》lchild);PostOrder(b-》rchild);visit(b);}}二叉树非递归遍历算法：有两种方法：①用栈存储信息的方法②增加指向父节点的指针的方法暂时只介绍下栈的方法先序遍历：[cpp]viewplaincopyvoidPreOrder(BTNode*b){Stacks;while(b!=NULL||!s.empty()){if(b!=NULL){visit(b);s.push(b);b=b-》left;}else{b=s.pop();b=b-》right;}}}中序遍历：[cpp]viewplaincopyvoidInOrder(BTNode*b){Stacks;while(b!=NULL||!s.empty()){if(b!=NULL){s.push(b);s=s-》left}if(!s.empty()){b=s.pop();visit(b);b=b-》right;}}}后序遍历：[cpp]viewplaincopyvoidPostOrder(BTNode*b){Stacks;while(b!=NULL){s.push(b);}while(!s.empty()){BTNode*node=s.pop();if(node-》bPushed){visit(node);}else{s.push(node);if(node-》right!=NULL){node-》right-》bPushed=false;s.push(node-》right);}if(node-》left!=NULL){node-》left-》bpushed=false;s.push(node-》left);}node-》bPushed=true;//如果标识位为true,则表示入栈}}}层次遍历算法：（用队列的方法）[cpp]viewplaincopyvoidlevelOrder(BTNode*b){QueueQ;Q.push(b);while(!Q.empty()){node=Q.front();visit(node);if(NULL!=node-》left){Q.push(node-》left);}if(NULL!=right){Q.push(node-》right);}}}已知先序和中序求后序的算法：（已知后序和中序求先序的算法类似，但已知先序和后序无法求出中序）[cpp]viewplaincopyintfind(charc,charA,ints,inte)/*找出中序中根的位置。*/{inti;for(i=s;iin_e)return;/*非法子树，完成。*/if(in_s==in_e){printf(“%c“,in[in_s]);/*子树子仅为一个节点时直接输出并完成。*/return;}c=pre[pre_s];/*c储存根节点。*/k=find(c,in,in_s,in_e);/*在中序中找出根节点的位置。*/pronum(pre,pre_s+1,pre_s+k-in_s,in,in_s,k-1);/*递归求解分割的左子树。*/pronum(pre,pre_s+k-in_s+1,pre_e,in,k+1,in_e);/*递归求解分割的右子树。*/printf(“%c“,c);/*根节点输出。*/}main(){charpre=“abdc“;charin=“bdac“;printf(“Theresult:“);pronum(pre,0,strlen(in)-1,in,0,strlen(pre)-1);getch();}
编程实现以上二叉树中序遍历操作，输出遍历序列，求写代码~~
#include《stdio.h》
#include 《stdlib.h》
#include 《malloc.h》
#define OK 1
#define ERROR 0
#define OVERFLOW 0
typedef char TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
typedef enum {Link,Thread} PointerTag;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
PointerTag LTag,RTag;
}BiThrNode;
typedef BiThrNode *BiThrTree;
BiTree CreateBiTree(BiTree T) //先序遍历构造二叉树
{
char ch;
scanf(“%c“,&ch);
if(ch==’#’) //#代表空指针
T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //申请结点
if(!T)
exit(OVERFLOW);
T-》data=ch; //生成根结点
T-》lchild=CreateBiTree(T-》lchild); //构造左子树
T-》rchild=CreateBiTree(T-》rchild); //构造右子树
}
return T;
}
Status InOrderTraverse(BiTree T,Status(*visit)(TElemType))
{//中序遍历二叉树
if(T)
{
if(InOrderTraverse(T-》lchild,visit))
if(visit(T-》data))
if(InOrderTraverse(T-》rchild,visit))
return OK;
return ERROR;
}
else
return OK;
}
Status PrintElement(TElemType e)
{
printf(“%-2c“,e);
return OK;
}
void main()
{
BiTree T=NULL;
printf(“请输入构造二叉树的字符序列：“);
T=CreateBiTree(T);
if(T)
printf(“二叉树建立成功！\n“);
else
printf(“二叉树构造失败！！！\n“);
printf(“中序遍历二叉树：“);
InOrderTraverse(T,PrintElement);
printf(“\n“);
}
用c++来实现二叉树的遍历
内容比较多，好好看看
单链表实现二叉树结构综合案例（使用类模板的方法）
——————–二叉树节点类
#ifndef TREE_NODE
#define TREE_NODE
#include 《iostream》
using namespace std;
template《typename T》
class Tree_Node
{
friend ostream& operator《《 《T》(ostream& out,const Tree_Node& TN);//特例 这里不是：Tree_Node《T》&……模板参数移到前面去了
public:
Tree_Node();
Tree_Node《T》* searchNode(int _index); //判断当前节点，当前节点的孩子节点是否是要寻找的节点
void DeleteNode();
void Preorder();
void Inorder();
void Postorder();
int m_iIndex; //节点的唯一索引值
T m_TData; //节点的数据类型在运行的时候指定
//凡是要用到当前类的声明对象的都要加上模板参数
Tree_Node《T》* m_pLchild; //左孩子指针
Tree_Node《T》* m_pRchild; //右孩子指针
Tree_Node《T》* m_pParent; //父指针
};
template《typename T》
ostream& operator《《(ostream& out,const Tree_Node《T》& TN) //模板参数又移到形参变量的地方了
{
out《《TN.m_iIndex《《“:“《《TN.m_TData《《endl;
return out;
}
template《typename T》
Tree_Node《T》::Tree_Node() //实现构造函数，模板参数在类名中已经体现出来了
{
this-》m_iIndex =0;
this-》m_TData =NULL;
this-》m_pLchild =NULL;
this-》m_pRchild =NULL;
this-》m_pParent =NULL;
}
template《typename T》
Tree_Node《T》* Tree_Node《T》::searchNode(int _index) //根据节点的唯一索引值，查找节点，并返回节点的指针
{
if (this-》m_iIndex == _index) // 这个this指的是根节点这个对象
{
return this;
}
Tree_Node《T》* find_node =NULL; //保存左子树和右子树查找到的结果
if (this-》m_pLchild !=NULL)
{
if (this-》m_pLchild-》m_iIndex == _index)
{
return this-》m_pLchild;
}
else //当前节点的左孩子不是目标节点，再查找左孩子的后代，并返回结果，递归实现的关键
{
find_node = this-》m_pLchild-》searchNode(_index);
//如果在左子树上找到了，则返回找到的节点,如果没有找到，再去右子树查找，在右子树查找的结果不管有没有都返回
if (find_node != NULL)
{
return find_node;
}
}
}
if (this-》m_pRchild !=NULL)
{
if (this-》m_pRchild-》m_iIndex == _index)
{
return this-》m_pRchild;
}else
{
find_node =this-》m_pRchild-》searchNode(_index);
return find_node;
}
}
return NULL; // 要执行到这一步，就说明该节点既没有左孩子和右孩子，本身也不是待查找节点，就返回空指针了
}
template《typename T》
void Tree_Node《T》::DeleteNode() // 删除节点，递归删除它的左孩子节点和右孩子节点
{
if (this-》m_pLchild !=NULL) //如果当前节点的左孩子节点不为空，则递归删除该左孩子节点和左孩子所有后代节点
{
this-》m_pLchild-》DeleteNode();
}
if (this-》m_pRchild != NULL)//如果当前节点的右孩子节点不为空，则递归删除该子节点的所有后代
{
this-》m_pRchild-》DeleteNode();
}
//如果当前节点的父指针不为空，把这个指向关系置空
if (this-》m_pParent != NULL)
{
//判断当前节点是父节点的左孩子还是右孩子，以便置空父节点的左孩子指针还是右孩子指针
if (this-》m_pParent-》m_pLchild == this)
{
this-》m_pParent-》m_pLchild =NULL; //如果当前节点是父节点的左孩子，则置空父节点的
}
if (this-》m_pParent-》m_pRchild == this)
{
this-》m_pParent-》m_pRchild =NULL;
}
}
delete this;
//这里没有显示的定义析构函数的原因是，删除节点的时候，该节点的所有指针对象都已经是空值了，没有释放内存空间的需要
// 自身节点也就是一个数据域，使用系统默认的析构函数就能完成这一点
//最后再删除本身这个节点，递归执行到这一步，就是叶子节点做的操作，这一层递归结束后，它的父节点就变成了叶子节点，递归很合理
}
template《typename T》
void Tree_Node《T》::Preorder() // 二叉树的前序遍历
{
//前序遍历先输出本身，再输出左子树，后输出右子树,递归的使用本身
cout《《this-》m_iIndex《《“：“《《this-》m_TData《《endl;
if (this-》m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this-》m_pLchild-》Preorder();
}
if (this-》m_pRchild !=NULL)
{
this-》m_pRchild-》Preorder();
}
}
template《typename T》
void Tree_Node《T》::Inorder() //二叉树的中序遍历
{
//中序遍历先输出左子树，再输出根，后输出右子树
if (this-》m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this-》m_pLchild-》Inorder();
}
cout《《this-》m_iIndex《《“：“《《this-》m_TData《《endl;
if (this-》m_pRchild !=NULL)
{
this-》m_pRchild-》Inorder();
}
}
template《typename T》
void Tree_Node《T》::Postorder() //二叉树的后序遍历
{
if (this-》m_pLchild !=NULL) //如果当前的左节点不为空，则递归输出左节点以及左节点的后代
{
this-》m_pLchild-》Postorder();
}
if (this-》m_pRchild !=NULL)
{
this-》m_pRchild-》Postorder();
}
cout《《this-》m_iIndex《《“：“《《this-》m_TData《《endl; // 最后输出根节点的信息
}
#endif
——————————二叉树类的实现，带有模板参数的类，声明和实现最好放在一个文件中，不容易出错
#ifndef TREE_h
#define TREE_h
#include “Tree_Node.h“
template《typename T》
class Tree
{
public:
Tree();
Tree_Node《T》* searchNode(int _index); //从根节点递归的方法向下搜索树，知道找到节点的索引等于参数的索引值
bool AddNode(int _index, int _direction,Tree_Node《T》* pNode); //添加节点
bool DeleteNode(int _index); //删除节点，不仅仅要删除自己，还要删除自己所有的后代节点，父节点的指向，用递归来实现
~Tree(); //析构函数
//树的前序遍历，后序遍历和中序遍历都是递归的方法，递归的调用节点中的方法，从这里就看到面向对象编程的好处了，比C语言的方法简单多了
void Preorder();
void Inorder();
void Postorder();
private:
Tree_Node《T》* m_pTree;
};
template《typename T》
Tree《T》::Tree()
{
this-》m_pTree = new Tree_Node《T》();
//第一个节点为根节点，索引默认为0，未指定它的孩子节点，所以孩子节点指针为空，父节点不存在，指向默认为空
//这个地方出现了错误，写代码的时候语法没有检测出来，任何地方使用带有模板参数的函数都要加上参数列表
//错误的写法：this-》m_pTree = new Tree_Node();
}
template《typename T》
Tree_Node《T》* Tree《T》::searchNode(int _index)
{
return this-》m_pTree-》searchNode(_index);
}
template《typename T》
bool Tree《T》::AddNode(int _index, int _direction,Tree_Node《T》* pNode)
{
Tree_Node《T》* direction_node = this-》searchNode(_index);
//插入节点是在指定的节点下插入，如果这个指定的节点不存在，插入操作就失败了
if (direction_node ==NULL)
{
return false;
}
//不能传进来的临时节点pNode做为树中新增的结点，因为是对指针的操作，外部操作pNode会同步影响到插入树中节点的值，应该重新申请一块内存空间
Tree_Node《T》* new_node =new Tree_Node《T》();
if (NULL == new_node)
{
return false;
}
new_node-》m_iIndex = pNode-》m_iIndex;
new_node-》m_TData= pNode-》m_TData;
//新增节点的父节点
new_node-》m_pParent = direction_node;
if (_direction ==0) //如果插入的是左孩子，指针指向如下
{
direction_node-》m_pLchild = new_node;
// 程序这里默认，目标节点没有孩子节点，二叉树的构造是从上到下一步一步构造的
//实际上有了删除节点的方法，即使该节点有过孩子节点，只需删除该孩子节点，也不是很麻烦
}
if (_direction ==1) //如果是右孩子，则当前节点指向目标节点
{
direction_node-》m_pRchild = new_node;
}
return true;
}
template《typename T》
bool Tree《T》::DeleteNode(int _index) // 删除节点，这一步应该放在
{
Tree_Node《T》* direction_node = this-》searchNode(_index);
if (NULL == direction_node) //如果目标节点为空，那么删除操作也就没有意义了
{
return false;
}
//如果不为空则调用节点对象的删除方法
direction_node-》DeleteNode();
return true;
}
template《typename T》
Tree《T》::~Tree()
{
//树的析构函数执行起来就很简单了，直接对根节点调用deleteNode函数就可以了
this-》m_pTree-》DeleteNode();
// 或者 DeleteNode(0)
}
template《typename T》
void Tree《T》::Preorder()
{
//前序遍历
this-》m_pTree-》Preorder();
}
template《typename T》
void Tree《T》::Inorder()
{
//中序遍历
this-》m_pTree-》Inorder();
}
template《typename T》
void Tree《T》::Postorder()
{
//后续遍历
this-》m_pTree-》Postorder();
}
#endif
——————–测试主文件
#include 《iostream》
#include 《stdlib.h》
#include “Tree.h“
using namespace std;
/*
10(0)
9(1) 8(2)
7(3) 6(4) 5(5) 4(6)
*/
int main()
{
Tree《int》* tree =new Tree《int》();
//生成一个树的，默认有一个根节点，根节点不放数据，索引默认为0
Tree_Node《int》* node1 = new Tree_Node《int》();
node1-》m_iIndex =1;
node1-》m_TData =9;
Tree_Node《int》* node2 = new Tree_Node《int》();
node2-》m_iIndex =2;
node2-》m_TData =8;
//在根节点下插入1和2号子节点
tree-》AddNode(0,0,node1);
tree-》AddNode(0,1,node2);
Tree_Node《int》* node3 = new Tree_Node《int》();
node3-》m_iIndex =3;
node3-》m_TData =7;
Tree_Node《int》* node4 = new Tree_Node《int》();
node4-》m_iIndex =4;
node4-》m_TData =6;
//在1号节点下插入3和4号子节点
tree-》AddNode(1,0,node3);
tree-》AddNode(1,1,node4);
Tree_Node《int》* node5 = new Tree_Node《int》();
node5-》m_iIndex =5;
node5-》m_TData =5;
Tree_Node《int》* node6 = new Tree_Node《int》();
node6-》m_iIndex =6;
node6-》m_TData =4;
//在2号节点下插入5和6号子节点
tree-》AddNode(2,0,node5);
tree-》AddNode(2,1,node6);
//前序遍历：0 1 3 4 2 5 6
tree-》Preorder();
cout《《“———————“《《endl;
//中序遍历：3 1 4 0 5 2 6
tree-》Inorder();
cout《《“———————“《《endl;
//后序遍历：3 4 1 5 2 6 0
tree-》Postorder();
cout《《“———————“《《endl;
cout《《*(tree-》searchNode(3))《《endl; //返回3：7 模板类的输出运算符友元函数形式重载成功，特例，一定要记住，会用
cout《《“———————“《《endl;
// 删除操作的实现
tree-》DeleteNode(2);
tree-》Preorder();
system(“pause“);
return 0;
}
我要二叉树代码递归遍历，非递归遍历，层次遍历
#include《stdio.h》
#include《stdlib.h》
typedef char datatype;
typedef struct bitnode
{
datatype data;
struct bitnode *lchild,*rchild;
}tree;
tree *init()
{
tree *bt;
bt=NULL;
bt=(tree*)malloc(sizeof(tree));
bt-》lchild=NULL;
bt-》rchild=NULL;
return bt;
}
tree *create(tree *bt)
{
char ch;
scanf(“%c“,&ch);
if(ch==’0’)
{
bt=NULL;
return bt;
}
else
{
bt=(tree *)malloc(sizeof(tree));
bt-》data=ch;
bt-》lchild=create(bt-》lchild);
bt-》rchild=create(bt-》rchild);
}
return bt;
}
tree *Linsert(datatype x,tree *parent)
{
tree *p;
if(parent==NULL)
{
printf(“insert error\n“);
return NULL;
}
if((p=(tree*)malloc(sizeof(tree)))==NULL)
return NULL;
p-》data=x;
p-》lchild=NULL;
p-》rchild=NULL;
if(parent-》lchild==NULL)
parent-》lchild=p;
else
{
p-》lchild=parent-》lchild;
parent-》lchild=p;
}
return parent;
}
tree *Rinsert(datatype x,tree *parent)
{
tree *p;
if(parent==NULL)
{
printf(“insert error\n“);
return NULL;
}
if((p=(tree*)malloc(sizeof(tree)))==NULL)
return NULL;
p-》data=x;
p-》lchild=NULL;
p-》rchild=NULL;
if(parent-》rchild==NULL)
parent-》rchild=p;
else
{
p-》rchild=parent-》rchild;
parent-》rchild=p;
}
return parent;
}
tree *Ldel(tree *parent)
{
tree *p;
if(parent==NULL||parent-》lchild==NULL)
{
printf(“delete error\n“);
return NULL;
}
p=parent-》lchild;
parent-》lchild=NULL;
free(p);
return parent;
}
tree *Rdel(tree *parent)
{
tree *p;
if(parent==NULL||parent-》rchild==NULL)
{
printf(“delete error\n“);
return NULL;
}
p=parent-》rchild;
parent-》rchild=NULL;
free(p);
return parent;
}
void visit(tree *bt)
{
printf(“%c “,bt-》data);
}
void preorder(tree *bt)
{
if(bt==NULL)
return ;
visit(bt);
preorder(bt-》lchild);
preorder(bt-》rchild);
}
void inorder(tree *bt)
{
if(bt==NULL)
return ;
inorder(bt-》lchild);
visit(bt);
inorder(bt-》rchild);
}
void postorder(tree *bt)
{
if(bt==NULL)
return ;
postorder(bt-》lchild);
postorder(bt-》rchild);
visit(bt);
}
tree *search(tree *bt,datatype x)
{
tree *p;
p=NULL;
if(bt)
{
if(bt-》data==x)
return bt;
if(bt-》lchild)
p=search(bt-》lchild,x);
if(p!=NULL)
return p;
if(bt-》rchild)
p=search(bt-》rchild,x);
if(p!=NULL)
return p;
}
return p;
}
void nrpreorder(tree *bt)
{
tree *stack,*p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&⊤==-1))
{
while(p!=NULL)
{
visit(p);
top++;
stack[top]=p;
p=p-》lchild;
}
if(top《0)
return ;
else
{
p=stack[top];
top–;
p=p-》rchild;
}
}
}
void nrinorder(tree *bt)
{
tree *stack,*p;
int top=-1;
if(bt==NULL)
return ;
p=bt;
while(!(p==NULL&⊤==-1))
{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p-》lchild;
}
if(top《0)
return ;
else
{
p=stack[top];
top–;
visit(p);
p=p-》rchild;
}
}
}
void nrpostorder(tree *bt)
{
int top;
tree *d,*dd;
tree *stack,*p;
if(bt==NULL)
return ;
top=-1;
p=bt;
while(!(p==NULL&⊤==-1))
{
while(p!=NULL)
{
top++;
stack[top]=p;
p=p-》lchild;
}
dd=stack[top];
if(top》-1)
if(dd)
{
p=stack[top]-》rchild;
d[top]=stack[top];
stack[top]=NULL;
dd=NULL;
}
else
{
p=d[top];
top–;
visit(p);
p=NULL;
}
}
}
void levelorder(tree *bt)
{
tree *queue;
int front,rear;
if(bt==NULL)
return ;
front=-1;
rear=0;
queue[rear]=bt;
while(front!=rear)
{
front++;
visit(queue[front]);
if(queue[front]-》lchild!=NULL)
{
rear++;
queue[rear]=queue[front]-》lchild;
}
if(queue[front]-》rchild!=NULL)
{
rear++;
queue[rear]=queue[front]-》rchild;
}
}
}
int countleaf(tree *bt)
{
if(bt==NULL)
return 0;
if(bt-》lchild==NULL&&bt-》rchild==NULL)
return 1;
return(countleaf(bt-》lchild)+countleaf(bt-》rchild));
}
int main()
{
tree *bt,*p;
int n=1,m,t;
char x;
printf(“———————–程序说明—————————\n“);
printf(“1．本程序涉及二叉树的所有操作。\n“);
printf(“2．创建操作为先序输入，输入0代表空。\n“);
printf(“3．删除操作和插入操作之前必须使用查找操作找到其双亲。\n“);
printf(“4．输入回车键开始本程序。\n“);
printf(“———————————————————-\n“);
getchar();
while(n!=0)
{
printf(“choose:\n1、Create a bitree 2、Search\n3、Preorder 4、Inorder 5、Postorder\n6、Levelorder 7、The number of leaves \n0、End\n“);
printf(“Do: “);
scanf(“%d“,&n);
getchar();
switch(n)
{
case 1:
bt=init();
printf(“Create a bitree :“);
bt=create(bt);
break;
case 2:
printf(“Input a char :“);
scanf(“%c“,&x);
getchar();
p=search(bt,x);
if(p!=NULL)
{
printf(“1、do nothing \n2、Insret L-tree 3、Insert R-tree \n4、Delete L-tree 5、Delete R-tree \n“);
printf(“Do: “);
scanf(“%d“,&m);
getchar();
switch(m)
{
case 1: break;
case 2:
printf(“Input a char :“);
scanf(“%c“,&x);
Linsert(x,p);
break;
case 3:
printf(“Input a char :“);
scanf(“%c“,&x);
Rinsert(x,p);
break;
case 4:
if(Ldel(p)!=NULL)
printf(“Complish delete !\n“);
break;
case 5:
if(Rdel(p)!=NULL)
printf(“Complish delete !\n“);
break;
default : printf(“Input error\n“);
}
}
else printf(“The char dose not exist\n“);
break;
case 3:
printf(“1、Recursive 2、Nonrecursive\n“);
printf(“Do: “);
scanf(“%d“,&t);
if(t==1)
preorder(bt);
else
nrpreorder(bt);
printf(“\n“);
break;
case 4:
printf(“1、Recursive 2、Nonrecursive\n“);
printf(“Do: “);
scanf(“%d“,&t);
if(t==1)
inorder(bt);
else
nrinorder(bt);
printf(“\n“);
break;
case 5:
printf(“1、Recursive 2、Nonrecursive\n“);
printf(“Do: “);
scanf(“%d“,&t);
if(t==1)
postorder(bt);
else
nrpostorder(bt);
printf(“\n“);
break;
case 6:
levelorder(bt);
break;
case 7:
printf(“%d\n“,countleaf(bt));
break;
case 0:break;
default : printf(“Input error\n“);
}
printf(“\n“);
}
return 0;
}
C语言二叉树遍历代码
1.t = malloc(sizeof(tree));
2.t-》rchild =createTree();
3.void qianxu(tree *t)
4.zhongxu(t-》lchild );//再读左子树
printf(“%c“,t-》data);//先读根结点
zhongxu(t-》rchild );//再读右子树
5.houxu(t-》lchild );//再读左子树
houxu(t-》rchild );//再读右子树
printf(“%c“,t-》data);//先读根结点
6.return 0;
7.n=count(t-》lchild)+count(t-》rchild)+1;
8.t1-》data=t-》data;
9.return t1;
10.return m+1;
PS:注意有些语句结尾是没有分号的
这个二叉树遍历代码的输入怎么结束啊 求解答
这就是按先序算法建立的二叉树，如果一个结点没有某棵子树，输入一个空格就行了。
比如对于如图所示的二叉树：
应该这样输入：
124两空格5两空格36三空格
这是运行结果的截图：