跪求各位，帮忙给这段二叉树层次遍历算法加上注释，尽量多一点详细一点。谢谢啦！！！（就是语句后//）
发布网友
发布时间：2022-04-23 03:40
共1个回答
热心网友
时间：2023-10-13 15:12
#include<iostream>
using namespace std;
struct bnode // 二叉树节点
{
char data;
bnode *lchild, *rchild;
};
struct node{ // 链式队列节点
bnode *date;
node *next;
};
// queue--------------------------------------------------------------
class queue // 层次遍历（广度优先遍历）需要用队列来保存访问过的节点
{
public:
queue();
bool empty()const; // 判断队列是否为空
bool append(bnode *&x); // 在对尾添加节点
bool getfront(bnode *&x)const; // 获得队首节点
bool serve(); // 删除队首节点
private:
node *front, *rear; // 队列首尾指针
};
queue::queue()
{
// 构造带头节点的链式队列
front=new node;
rear=front;
front->next=NULL;
}
bool queue::empty()const
{
if(front==rear)
return 1;
else
return 0;
}
bool queue::append(bnode *&x)
{
node *s=new node;
s->date=x;
s->next=NULL;
rear->next=s;
rear=s;
return 1;
}
bool queue::getfront(bnode *&x)const
{
if(empty())
return 0;
else{
x=front->next->date; // font指向头节点，其下一个节点才是真正的队首节点
return 1;
}
}
bool queue::serve()
{
if(empty())
return 0;
else{
node *u;
u=front->next;
front->next=u->next;
delete u;
if(front->next==NULL)
rear=front;
return 1;
}
}
// bitree-----------------------------------------------------
class bitree
{
public:
bitree();
bnode *get_root() { return root; } // 获取根节点
void create(){ create(root); } // 构造节点
private:
bnode *root;
void create(bnode *&T);
};
bitree::bitree()
{
root=NULL;
}
void bitree::create(bnode *&T)
{
char n;
cin>>n;
if(n=='.') // 输入'.'时停止构造该节点
T=NULL;
else{
T=new bnode;
T->data=n;
create(T->lchild);
create(T->rchild);
}
}
// test---------------------------------------------
queue tr;
int main()
{
bitree a;
a.create();
bnode *t=a.get_root();
tr.append(t); // 二叉树根节点入队
cout<<t->data<<endl;
while(!tr.empty())
{
bnode *p;
// 取出队首节点，依次访问它的左右子节点
tr.getfront(p);
tr.serve();
if(p->lchild!=NULL)
{
cout<<p->lchild->data<<endl;
tr.append(p->lchild);
}
if(p->rchild!=NULL)
{
cout<<p->rchild->data<<endl;
tr.append(p->rchild);
}
}
return 0;
}
对于叶节点，它的左右子树为空，所以需要用'.'来表示
