算法之二叉树各种遍历 (三)
stack.pop();
BT->biTree;
printf("%c ",BT->biTree->data);
}
//遍历右子树
if(!stack.empty()){
BT = stack.top();
//访问过右子树
BT->tag = 'R';
p = BT->biTree;
p = p->rchild;
}
}//while
}
<4>层次遍历
【思路】：按从顶向下，从左至右的顺序来逐层访问每个节点，层次遍历的过程中需要用队列。
[cpp]
//层次遍历
void LevelOrder(BiTree T){
BiTree p = T;
//队列
queue queue;
//根节点入队
queue.push(p);
//队列不空循环
while(!queue.empty()){
//对头元素出队
p = queue.front();
//访问p指向的结点
printf("%c ",p->data);
//退出队列
queue.pop();
//左子树不空，将左子树入队
if(p->lchild != NULL){
queue.push(p->lchild);
}
//右子树不空，将右子树入队
if(p->rchild != NULL){
queue.push(p->rchild);
}
}
}
//层次遍历
void LevelOrder(BiTree T){
BiTree p = T;
//队列
queue queue;
//根节点入队
queue.push(p);
//队列不空循环
while(!queue.empty()){
//对头元素出队
p = queue.front();
//访问p指向的结点
printf("%c ",p->data);
//退出队列
queue.pop();
//左子树不空，将左子树入队
if(p->lchild != NULL){
queue.push(p->lchild);
}
//右子树不空，将右子树入队
if(p->rchild != NULL){
queue.push(p->rchild);
}
}
}
测试用例：
输入：
ABC##DE#G##F###
输出：
代码：
[cpp]
#include
#include
#include
using namespace std;
//二叉树结点
typedef struct BiTNode{
//数据
char data;
//左右孩子指针
struct BiTNode *lchild,*rchild;
//按先序序列创建二叉树
int CreateBiTree(BiTree &T){
char data;
//按先序次序输入二叉树中结点的值（一个字符），‘#’表示空树
scanf("%c",&data);
if(data == '#'){
T = NULL;
}
else{
T = (BiTree)malloc(sizeof(BiTNode));
//生成根结点
T->data = data;
//构造左子树
CreateBiTree(T->lchild);
//构造右子树
CreateBiTree(T->rchild);
}
return 0;
}
//输出
void Visit(BiTree T){
if(T->data != '#'){
printf("%c ",T->data);
}
}
//先序遍历
void PreOrder(BiTree T){
if(T != NULL){
//访问根节点
Visit(T);
//访问左子结点
PreOrder(T->lchild);
//访问右子结点
PreOrder(T->rchild);
}
}
//中序遍历
void InOrder(BiTree T){
if(T != NULL){
//访问左子结点
InOrder(T->lchild);
//访问根节点
Visit(T);
//访问右子结点
InOrder(T->rchild);
}
}
//后序遍历
void PostOrder(BiTree T){
if(T != NULL){
//访问左子结点
PostOrder(T->lchild);
//访问右子结点
PostOrder(T->rchild);
//访问根节点
Visit(T);
}
}
/* 先序遍历(非递归)
思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
*/
void PreOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//访问根节点
printf("%c ",p->data);
//遍历左子树
p = p->lchild;
}
else{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}//w