二叉树的层次，中序非递归遍历，以递归前序的方式构造二叉树，将二叉树中的e更新为d，输出从根结点出发 到指定结点,依次经过的祖先(即路径)，由前序和中序还原二叉树
这里是头文件函数
#ifndef BITREE_H_INCLUDED
#define BITREE_H_INCLUDED
typedef char DataTyp;
typedef struct Node
{
Node *lch;
Node *rch;
DataTyp data;
}Node,*Bitree;
void Create( Bitree &bt);///初始化一棵二叉树
void PrintTree(Bitree bt);///按照右子树为先输出
void Destroy( Bitree &bt);///以递归的方式销毁二叉树
bool Update(Bitree bt, DataTyp e, DataTyp d);///将二叉树中的e更新为d
Node* Search( Bitree bt , DataTyp e );
void PrintfPath( Bitree bt, DataTyp e,int depth);
/**输出从根结点出发 到指定结点,依次经过的祖先(即路径)
* 即简化版的“迷宫"，走过不用标记；t的下一步只有
* 各祖先的指针存入 path[1...depth-1]，
* bt 待查二叉树
* elem 待查元素值
* depth为当前长度,( 也即当前结点深度(根为第1层) )
**/
void PrintfPath( Bitree bt, DataTyp e);///包装输出从根结点出发 到指定结点,依次经过的祖先(即路径)
int SearchData(DataTyp A[],int L,int R,DataTyp e);///查找根结点
/**
* 由前序序列 pre[preL--preR],中序序列in[inL--inR] 构造二叉树t
序列合法，则成功构造，返回true; 序列不合法，则返回false
*/
bool CreateINpreTree(Bitree &bt ,DataTyp pre[] , int preL , int preR, DataTyp in[] , int inL , int inR );
void CreateINpreTree(Bitree &bt ,DataTyp pre[] , DataTyp in[] , int len);
void PrintInorder(Bitree bt);///非递归遍历(中序输出)二叉树
void PrintLevel(Bitree bt);///利用队列层序(从上至下，从左至右)输出二叉树
void LevelTraverse (Bitree bt );
#endif // BITREE_H_INCLUDED
///这里是上面头文件函数的实现
#include"Bitree.h"
#include<iostream>
#include<iomanip>
#include<stdio.h>
#include<string>
#include"Queue.h"
#include"Stack.h"
using namespace std;
/**初始化一棵二叉树(以递归前序的方式构造二叉树)
*并且以输入的#字符表示为空子树*/
void Create( Bitree &bt)
{
DataTyp e;
cin>>e;
if(e=='#')///递归的出口，表示是空的子树则返回
{
bt=NULL;
return;
}
bt=new Node;///生成根节点
bt->data=e;
Create(bt->lch);///生成左子树
Create(bt->rch);///生成右子树
}
const int ROW=5;///表示行的空格
const int COL=30;///表示行的——这个对齐符号
///depth表示该子树当前的层次
void PrintTree(Bitree bt,int depth)///按照右子树为先输出(打出一个有层次的二叉树)
{
if(bt==NULL)///这里是递归的出口
return;
PrintTree(bt->rch,depth+1);///先递归遍历右子树
int i;///这里要注意
for(i=0;i<depth*ROW;i++)///打出空格数
cout<<" ";
cout<<bt->data;
for(int k=i;k<COL;k++)///打出符号-
cout<<"-";
cout<<endl;///没打完一行则需画行
PrintTree(bt->lch,depth+1);
}///遍历完一行就+1
void PrintTree(Bitree bt)///这里函数时包装上面的输出的函数，屏蔽掉更多的参数
{
PrintTree( bt,1);
cout<<endl<<endl;
}
void Destroy( Bitree &bt)///以递归的方式销毁二叉树(只能后序)
{
if(bt==NULL)///递归的出口
return;
Destroy(bt->lch);
Destroy(bt->rch);
delete bt;
bt=NULL;
}
Node* Search( Bitree bt , DataTyp e)///先找到指定的元素
{
if(bt==NULL||bt->data==e)///递归出口，如果是空树返回本身，等于则返回该节点
return bt;
Node *p=Search(bt->lch,e);///查找左子树
if(p&&p->data==e)
return p;
else
return Search(bt->rch,e);
}
bool Update(Bitree bt, DataTyp e, DataTyp d)///将二叉树中的e更新为d
{
Node *p=Search(bt,e);///在查找的 过程中有两种情况
if(p->data==e)
{
p->data=d;
return true;
}
else
return false;
}
/**输出从根结点出发 到指定结点,依次经过的祖先(即路径)
* 即简化版的“迷宫"，走过不用标记；t的下一步只有
* 各祖先的指针存入 path[1...depth-1]，
* bt 待查二叉树
* elem 待查元素值
* depth为当前长度,( 也即当前结点深度(根为第1层) )
**/
Node *p[100];///记录当下的路过的结点
void PrintfPath( Bitree bt, DataTyp elem,int depth)
{
if(bt==NULL)///递归的出口
return;
if(bt->data==elem)
{
for(int i=1;i<depth;i++)
cout<<"\t<"<<p[i]->data<<">";
return;
}
p[depth]=bt;
PrintfPath( bt->lch, elem, depth+1);///查找左子树
PrintfPath( bt->rch, elem, depth+1);///查找左子树
}
void PrintfPath( Bitree bt, DataTyp elem)///这个是包装输出祖先路径的函数，屏蔽掉多个参数
{
PrintfPath(bt,elem,1);
}
int SearchData(DataTyp A[],int L,int R,DataTyp e)///查找根所在的位置
{
for(int i=L;i<=R;i++)
if(A[i]==e)
return i;
return -1;
}
/** 由前序序列 pre[preL...preR],中序序列in[inL...inR] 构造二叉树t
序列合法，则成功构造，返回true; 序列不合法，则返回false
**/
bool CreateINpreTree(Bitree &bt ,DataTyp pre[] , int preL , int preR , DataTyp in[] , int inL , int inR)
{
if(preL>preR)///长度不合法的时候，则建立空树
{
bt=NULL;
return true;
}
bt=new Node;///生成根结点
bt->data=pre[preL];///前序的第一个作为二叉树的根结点
int i=SearchData(in,inL,inR,pre[preL]);///查找中序根结点所在的位置i
if(i==-1)
return false;
if(CreateINpreTree(bt->lch , pre, preL+1 , preL+i-inL ,in ,inL, i-1))
if(CreateINpreTree(bt->rch , pre, preL+i-inL+1 , preR, in ,i+1, inR))
return true;
return false;
}
/**通过长度为len 的pre 和 in 两个遍历序列，生成二叉树t
*包装以上create函数，以减少函数参数，方便用户使用
*/
void CreateINpreTree(Bitree &bt ,DataTyp pre[] , DataTyp in[] , int len)
{
CreateINpreTree(bt , pre , 0 , len-1, in , 0 , len-1);
}
void PrintInorder(Bitree bt)///非递归遍历(中序输出)二叉树(栈)
{
SqStack s;
InitStack(s);///初始化栈
Node *p=bt;
do
{
while(p)///当p不为空时
{
Push(s,p);///进栈
p=p->lch;///继续遍历左孩子
}
if(!(IsEmpty(s)))///当栈不为空时,进行推栈操作
{
p=Pop(s);///退栈,访问根结点
cout<<"<"<<p->data<<">"<<setw(5);
p=p->rch;///遍历右子树结点
}
}while(p||!IsEmpty(s));///{如果是左子树返回，则退栈访问根结点，如果是右子树返回说明遍历结束}
}
void PrintLevel(Bitree bt)///利用队列层序(从上至下，从左至右)输出二叉树
{
QueueNode q;
InitQueue(q);///初始化
Node *p=bt;
EnQueue(q,p);
while(!IsEmptyQ(q))
{
p=DeQueue(q);
cout<<"<"<<p->data<<">"<<setw(5);
if(p->lch)
EnQueue(q,p->lch);
if(p->rch)
EnQueue(q,p->rch);
}
}
void LevelTraverse (Bitree bt )
{
QueueNode Q;
InitQueue(Q);
if ( bt == NULL ) return; /* 若是空树则直接返回 */
Node *t=bt;
EnQueue( Q, t );
while ( !IsEmptyQ( Q ) )
{
t = DeQueue( Q );
cout<<t->data<<" ";/**访问取出队列的结点*/
if ( t->lch )
EnQueue( Q, t->lch );
if ( t->rch )
EnQueue( Q, t->rch );
}
}
///这里是头文件，栈，用来实现非递归的中序遍历
#ifndef STACK_H_INCLUDED
#define STACK_H_INCLUDED
#include"Bitree.h"
#define MaxSize 50///栈中元素最大的个数
typedef Bitree St;///定义栈的结点数据类型为树结点
typedef struct
{
St *base;///存放栈中的元素
int top;///栈顶指针
}SqStack;
void InitStack(SqStack &s);///初始化栈
bool IsEmpty(SqStack &s);///判栈空
void Push(SqStack &s, St e);///元素压栈
St Pop(SqStack &s);///弹栈并返回栈顶元素
St Gettop(SqStack &s);///取栈顶元素
#endif // STACK_H_INCLUDED
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include"Stack.h"
using namespace std;
void InitStack(SqStack &s)///初始化栈
{
s.top=-1;
}
bool IsEmpty(SqStack &s)///判栈空
{
if(s.top==-1)
return true;
else
return false;
}
void Push(SqStack &s, St e)///元素进栈
{
if(s.top==MaxSize-1)///如果栈满
exit(-1);
else
s.base[++s.top]=e;
}
St Pop(SqStack &s)///弹栈并返回栈顶元素
{
if(IsEmpty(s)==true)
exit(-1);
else
return s.base[s.top--];
}
St Gettop(SqStack &s)///取栈顶元素
{
if(IsEmpty(s)==true)
exit(-1);
else
return s.base[s.top-1];
}
///这里是队列头文件，用来实现二叉树的层次遍历
#ifndef QUEUE_H_INCLUDED
#define QUEUE_H_INCLUDED
#include"Bitree.h"
typedef Bitree ElemData;///定义队列的结点数据类型为树结点
typedef struct QueueUNode///定义结点类型
{
ElemData data;
struct QueueUNode *next;
}QueueUNode;
typedef struct///定义队列类型
{
QueueUNode *front;///队头指针
QueueUNode *rear; ///队尾指针
}QueueNode;
void InitQueue(QueueNode &q);///初始化带头结点的空队列
void EnQueue(QueueNode &q, ElemData e);///元素e入队列
ElemData DeQueue(QueueNode &q);///队头元素出队列，并返回
int IsEmptyQ(QueueNode q);///队列判空
#endif // QUEUE_H_INCLUDED
///实现队列头文件的函数
#include<stdio.h>
#include<stdlib.h>
#include"Queue.h"
void InitQueue(QueueNode &q)///初始化带头结点的空队列
{
q.front=q.rear=new QueueUNode;
q.rear->next=NULL;
}
int IsEmptyQ(QueueNode q)///队列判空
{
if (q.rear==q.front)
return true;
else
return false;
}
void EnQueue(QueueNode &q, ElemData e)///元素e入队列(尾插法)
{
QueueUNode *p=new QueueUNode;
p->data=e;
q.rear->next=p;///尾插法
q.rear=p;
}
ElemData DeQueue(QueueNode &q)///队头元素出队列，并返回
{
if(IsEmptyQ(q))
exit(-1);
QueueUNode *p=q.front->next;///首结点
ElemData e=p->data;///作为返回的元素
if(p==q.rear)///当只剩一个结点时
q.rear=q.front;
q.front->next=p->next;
delete p;
return e;
}
///这里是main函数，实现全部
#include<iostream>
#include<stdio.h>
#include<string>
#include"Bitree.h"
using namespace std;
int main()
{
freopen("data.in","r",stdin);
Bitree bt=NULL;
Create(bt);
cout<<"\t输出下列构造好的二叉树如下:"<<endl<<endl;
PrintTree(bt);
cout<<"\t输出从根结点出发，到指定K结点,依次经过的祖先(即路径)如下:"<<endl;
PrintfPath(bt,'K');
Bitree bt1;
DataTyp pre[]="ABDHEFCIGJK";// 前序序列
DataTyp in[]= "HDBEFAICJGK";// 中序序列
cout<<endl<<endl<<endl<<"\t输出由前序和中序还原的二叉树如下:"<<endl;
CreateINpreTree( bt1 , pre , in ,11);
PrintTree(bt1);
cout<<endl<<endl<<"\t输出中序非递归遍历的二叉树如下:"<<endl;
PrintInorder(bt);
cout<<endl<<endl<<endl<<"\t输出层次遍历的二叉树如下:"<<endl;
PrintLevel( bt);
Update(bt,'E','&');
cout<<endl<<endl<<endl<<"\t输出下列将'E'改为'&'后的二叉树"<<endl;
PrintTree(bt);
return 0;
}
///下面这里是我在文件里面设置的二叉树的结点，根据读取文件的结点来实现二叉树的运行 文件名是 ( data.in )A B D H # # # E # F # # C I # # G J # # K # #
建立文件是这样建立的：：：：：
这下面是建立一个文件二叉树，从文件中去读取这些字母构造二叉树