求先序创建二叉树的c++代码

#include
#include
#include
#include
#include
#include
using namespace std;

typedef struct BiNode{
char data;
struct BiNode *lchild, *rchild;

} *BiTree;

//先序创建
int CreatBiTree(BiTree &T)
{
char ch;
cin>>ch;

if(ch=='#')
T=NULL;
else
{
if(!(T=(BiNode*)malloc(sizeof(BiNode))))
exit(0);
T->data=ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);

}
return 1;

}

//
//中序创建
int inOrderCreatBiTree(BiTree &T)
{
char ch;
cin>>ch;

if(ch=='#')
T=NULL;
else
{
if(!(T=(BiNode*)malloc(sizeof(BiNode))))
exit(0);
CreatBiTree(T->lchild);
T->data=ch;
CreatBiTree(T->rchild);

}
return 1;

}
//先序遍历
void PreOrderTraverse(BiTree T)
{

if(T){
cout<data<<" ";

PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}

//中序遍历
void inOrderTraverse(BiTree T)
{

if(T){
cout<data<<" ";

PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
//非递归遍历二叉树 中序遍历
int InOrderTraverse(BiTree t)
{
stack s;//创建时栈为空
BiTree p=t;
//s.push(p);
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;
}else{
p=(BiTree)s.top();
s.pop();
cout<data<<" ";
p=p->rchild;
}
}
return 1;
}
//得到节点书目
int getNodeNum(BiTree t)
{
stack s;//创建时栈为空
BiTree p=t;
int num=0;
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;
}else{
p=(BiTree)s.top();
s.pop();
num++;
p=p->rchild;
}
}
return num;
}

//插入新的子树
int insert(BiTree &t,char data,int pos,bool isLchild=true)
{
stack s;//创建时栈为空
BiTree p=t;
int i=0; //记录遍历到的位置
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;

}else{
p=(BiTree)s.top();

//在下面进行操作
if (pos==i)
{
BiTree temp;
if(!( temp=(BiNode*)malloc(sizeof(BiNode)))) exit(0);

temp->data=data;
if (isLchild)
{
if (p->lchild==NULL)
{
temp->lchild=NULL;
}else {
temp->lchild=p->lchild;
}
p->lchild=temp;
temp->rchild=NULL;//这一步至关重要 记住右指针置空
//右指针指向随机的内存 导致程序崩溃
}else{
temp->rchild=p->rchild;
p->rchild=temp;
temp->lchild=NULL; //同上
}

}
//完成操作
i++;//遍历到的位置标记加加
s.pop();
p=p->rchild;
}

}
return 1;
}

// 用数组先序创建二叉树
int CreatBiTreeByArr(BiTree &T, char *p)
{
char ch;
static int n=0;
ch=p[n];
if (p[n]=='\0')
{
return 0;
}
n++;
if(ch=='#')
T=NULL;
else
{
if(!(T=(BiNode*)malloc(sizeof(BiNode))))
exit(0);
T->data=ch;

CreatBiTreeByArr(T->lchild,p);
CreatBiTreeByArr(T->rchild,p);

}
return 1;
}

// 得到当前节点的数据
bool getPosData(BiTree t,int pos,char &data,bool isLchild=true) //默认删除左子树
{
stack s;//创建时栈为空
BiTree p=t;
int i=0; //记录遍历到的位置
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;

}else{
p=(BiTree)s.top();
//在下面进行操作
if (pos==i)
{
data=p->data;
}
//完成操作
i++;//遍历到的位置标记加加
s.pop();
p=p->rchild;
}
}
return 1;
}

//
// 删除当前节点的 左或右孩子
bool deletebi(BiTree t,int pos,char &data,bool isLchild=true) //默认删除左子树
{
stack s;//创建时栈为空
BiTree p=t;
int i=0; //记录遍历到的位置
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;

}else{
p=(BiTree)s.top();
//在下面进行操作
if (pos==i)
{
BiTree tr=p->lchild;
if (isLchild)
{
if (tr==NULL)
{
cout<<"该节点无左孩子"< }else{
data=tr->data;
p->lchild=tr->lchild;
free(tr);
tr=NULL;
}

}else{
if (tr==NULL)
{
cout<<"该节点无右孩子"< }else{
data=tr->data;
p->rchild=tr->rchild;
free(tr);
tr=NULL;
}
}
return 1;
}
//完成操作
i++; //遍历到的位置标记加加
s.pop();
p=p->rchild;
}
}
return 0;
}

// 修改当前节点的数据
bool modifyPosData(BiTree t,int pos,char data,bool isLchild=true) //默认删除左子树
{
stack s;//创建时栈为空
BiTree p=t;
int i=0; //记录遍历到的位置
while(p||!s.empty()) // || p不为空 或s不为空
{
if (p)
{
s.push(p);
p=p->lchild;

}else{
p=(BiTree)s.top();

//在下面进行操作
if (pos==i)
{
p->data=data;
}
//完成操作

i++;//遍历到的位置标记加加
s.pop();
p=p->rchild;
}
}
return 1;
}

void main()
{
BiTree t;
char ch[]="1234####567###89###";//输入的数组
cout<<"输入二叉树："< CreatBiTreeByArr(t,ch); //用上面的数组创建二叉树 我采用的是先序创建的 注意!!!
cout<<"中序遍历："< InOrderTraverse(t);
cout< //下面是对功能的测试
//modify(t,3,'a');
//PreOrderTraverse(t);
//insert(t,'b',5,true);
//cout<
cout<<"该树节点书目是:"< char data;
getPosData(t,4,data);//中序遍历 第一个数为根节点位置为0

cout<<"位置4的节点数据是:"< deletebi(t,2,data);
cout<<"删除的数是:"<
InOrderTraverse(t);

cout<
}