题目 6 建立二叉树，层序、先序遍历（用非递归的方法）

2024-11-07 09:03:58

推荐回答（3个）

回答（1）：

#include
#include
typedef
struct
bitnode
{
char
data;
struct
bitnode
*lchild,*rchild;
}
bitnode,*bitree;//二叉树的节点类型
typedef
struct
qnode
{
bitnode
data;
struct
qnode
*next;
}
qnode,*queueptr;//队列节点类型
typedef
struct
{
queueptr
front;
queueptr
rear;
}linkqueue;//队列的头尾指针
void
initqueue(linkqueue
*q)//创建队列
{
q->front=q->rear=(queueptr)malloc(sizeof(qnode));
q->rear->next=null;
}
void
enqueue(linkqueue
*q,bitnode
e)//入队操作
{
queueptr
p;
p=(queueptr)malloc(sizeof(qnode));
p->data=e;
p->next=null;
q->rear->next=p;
q->rear=p;
}
bitnode
dequeue(linkqueue
*q)//出对操作
{
bitnode
e;queueptr
p;
p=q->front->next;
e=p->data;
q->front->next=p->next;
if(q->rear==p)
q->rear=q->front;
free(p);
return
(e);
}
int
queueempty(linkqueue
*q)//判断队列是否为空
{
if(q->front==q->rear
)
return
1;
else
return
0;
}
bitree
createbitree()//创建二叉树
{
char
p;bitree
t;
scanf("%c",&p);
if(p=='
')
t=null;
else
{
t=(bitnode
*)malloc(sizeof(bitnode));
t->data=p;
t->lchild=createbitree(t->lchild);
t->rchild=createbitree(t->rchild);
}
return
(t);
}
void
preorder(bitree
t)//先序
{
if(t!=null)
{
printf("%c",t->data);
preorder(t->lchild);
preorder(t->rchild);
}
}
void
levelorder(bitree
t)//层次遍历
{
linkqueue
q;
bitnode
p;
initqueue(&q);
enqueue(&q,*t);
while(!queueempty(&q))
{
p
=
dequeue(&q);
printf("%c",p.data);
if(p.lchild!=null)
enqueue(&q,*(p.lchild));
if(p.rchild!=null)
enqueue(&q,*(p.rchild));
}
}
void
main()
{
bitree
ta;
ta=createbitree();
printf("层次遍历:");
printf("\n");
levelorder(ta);
printf("\n");
printf("先序遍历:");
printf("\n");
preorder(ta);
}
层次使用非递归的，用到队列
先序是用递归的
创建树使用先序递归建树
不知道你会不会输入
很多人不会输入所以还是给你个例子吧
abc**de*f**g***(注意*代表空格，因为空格你看不到就不好表示).

回答（2）：

#include
#define M 1000
using namespace std;
template
struct Btnode //定义二叉链表结点类
{T d; //数据域
Btnode *lchild; //左指针域
Btnode *rchild; //右指针域
}; //二叉链表类
template //类模板，T为虚拟类型
class Binary_Tree
{private:
Btnode *BT; //而叉链表根结点指针
public: //成员函数
Binary_Tree(){BT=NULL;return;} //二叉链表初始化
void creat_Binary_Tree(T); //生成二叉链表
void pretrav_Binary_Tree(); //前序遍历二叉链表
void intrav_Binary_Tree(); //中序遍历二叉链表
void postrav_Binary_Tree(); //后序遍历二叉链表
};
//——————————————生成二叉链表————————————————
template
void Binary_Tree::creat_Binary_Tree(T end){
Btnode *p;
T x;
cin>>x;
if(x==end)
return;
p=new Btnode;
p->d=x;
p->lchild=NULL;
p->rchild=NULL;
BT=p;
creat(p,1,end);
creat(p,2,end);
return;
}
template
static creat(Btnode *p,int k,T end)
{
Btnode *q;
T x;
cin>>x;
if(x!=end)
{
q=new Btnode; q->d=x;
q->lchild=NULL;
q->rchild=NULL;
if(k==1) p->lchild=q; if(k==2) p->rchild=q; creat(q,1,end);
creat(q,2,end); }
return 0;
}
//————————————前序遍历二叉链表——————————————
template
void Binary_Tree::pretrav_Binary_Tree( )
{
Btnode *p;
p=BT;
pretrav(p); cout< return;
}

template
static pretrav(Btnode *p)
{
if(p!=NULL)
{
cout<d<<" "; pretrav(p->lchild); pretrav(p->rchild); }
return 0;
}
//————————————中序遍历二叉链表——————————————
template
void Binary_Tree::intrav_Binary_Tree( )
{
Btnode *p;
p=BT;
intrav(p); cout< return;
}

template
static intrav(Btnode *p)
{
if(p!=NULL)
{
intrav(p->lchild); cout<d<<" "; intrav(p->rchild); }
return 0;
}
//————————————后序遍历二叉链表———————————————
template
void Binary_Tree::postrav_Binary_Tree( )
{
Btnode *p;
p=BT;
postrav(p); cout< return;
}

template
static postrav(Btnode *p)
{
if(p!=NULL)
{
postrav(p->lchild); postrav(p->rchild); cout<d<<" "; }
return 0;
}
int main( )
{
Binary_Treeb;
cout<<"输入各结点值(-1为结束符值):"< b.creat_Binary_Tree(-1);
cout<<"前序序列:"< b.pretrav_Binary_Tree( );
cout<<"中序序列:"< b.intrav_Binary_Tree( );
cout<<"后序序列:"< b.postrav_Binary_Tree( );
return 0;
}

回答（3）：

我靠那么复杂才20分懒得理你

最新问答

这个作业怎么做？香港和澳门的相同点是

滴滴打车如果写了5个乘客，车子来了但车子坐不下怎么办。

我个人没什么主见，生活中总会因为别人的话语改变自己决定的事，我要怎么才能拥有自己的主见

如果给别人转了账，从银行里能查出收款人名字信息吗？

如果从深圳龙华车站到湖南江华的客车，没有到终点站，但是我到了可不可以停车的？

在网上买的钢化膜，可以自己贴吗？怎么贴呢？