另一种使用栈实现二叉树层序遍历的方法
另一种使用栈实现二叉树层序遍历的方法
使用队列是比较方便的实现二叉树层序遍历的常用方法，通过栈来实现也是可以的，以下给出一个使用栈实现二叉树层序遍历的方法。
使用三个栈实现二叉树的层次遍历
int LayerOrderByStackTraverse(BiTree T,int (*Visit)(TreeElemType d))
{
//s1存储每层的所有树节点，次序是逆序（左边的节点在栈下方）
//s2是存储当前层节点的下层所有节点，次序也是逆的
//s3是为了正确顺序输出节点，从s1反序而来的，左边的节点在栈上方）
//temp是s2和s1的中转变量，为了下次循环能够处理下一层节点。
LinkStack s1,s2,s3,temp;
initStack(&s1);
initStack(&s2);
initStack(&s3);
BiNode * node;
if(T==NULL)
return ERROR;
pushStack(s1,T);
while(lenStack(s1)){
while(lenStack(s1)){ //从s1反序生成s3，左边的节点在栈上方）
popStack(s1,&node);
pushStack(s3,node);
}
while(lenStack(s3)){ //从s3出栈并输出节点，是层序的正确顺序
popStack(s3,&node);
printTreeNode(node);
//按层序正确顺序将当前层的下层结点压入s2，s2中左边的节点在栈下方
if(node->l)
pushStack(s2,node->l);
if(node->r)
pushStack(s2,node->r);
} //循环结束后，s2中保存了下一层节点信息
//以下交换s2和s1所指向的栈，以便下次循环通过s1来处理下一层节点
temp=s1;
s1=s2;
s2=temp;
}
return OK;
}两个栈实现二叉树的层次遍历
以上代码写好后，发现了以下文章：
双栈法对二叉树进行层序遍历
https://blog.csdn.net/qq_46477898/article/details/110142364
从而精简掉s3栈，且省略了交换两个栈的过程。
精简后的代码：
int LayerOrderByStackTraverse2(BiTree T,int (*Visit)(TreeElemType d))
{
//s1存储每层的所有树节点，次序是逆序（左边的节点在栈下方）
//s2是为了正确顺序输出节点，从s1反序而来的，左边的节点在栈上方）
LinkStack s1,s2;
initStack(&s1);
initStack(&s2);
BiNode * node;
if(T==NULL)
return ERROR;
pushStack(s1,T);
while(lenStack(s1)){
while(lenStack(s1)){ //从s1反序生成s2，左边的节点在栈上方）
popStack(s1,&node);
pushStack(s2,node);
}
while(lenStack(s2)){ //从s2出栈并输出节点，是层序的正确顺序
popStack(s2,&node);
printTreeNode(node);
//按层序正确顺序将当前层的下层结点压入s1，s1中左边的节点在栈下方
if(node->l)
pushStack(s1,node->l);
if(node->r)
pushStack(s1,node->r);
} //循环结束后，s1中保存了下一层节点信息
}
return OK;
}完整的代码如下：
#include <stdio.h>
#include <conio.h>
#include <malloc.h>
#define ERROR 0
#define OK 1
typedef int TreeElemType;
typedef struct BinaryTree
{
TreeElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;
typedef BiNode *StackElemType;
struct SNODE
{
StackElemType data;
struct SNODE *next;
};
typedef struct SNODE SNode;
typedef struct SNODE *LinkStack;
int initStack(LinkStack *L)
{
*L=(SNode *)malloc(sizeof(SNode));
if(!L)
exit(ERROR);
(*L)->next=NULL;
return OK;
}
int lenStack(LinkStack L)
{
int j=0;
while (L->next)
{
L=L->next;
j++;
}
return j;
}
int popStack(LinkStack L,StackElemType *e)
{
LinkStack p;
SNode *temp;
p=L;
if(p->next){
*e=p->next->data;
temp=p->next;
p->next=temp->next;
free(temp);
return OK;
}else
return ERROR;
}
int topStack(LinkStack L,StackElemType *e)
{
LinkStack p;
p=L;
if(p->next){
*e=p->next->data;
return OK;
}else
return ERROR;
}
int pushStack(LinkStack L,StackElemType e)
{
LinkStack p,s;
p=L;
s=(LinkStack)malloc(sizeof(SNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
int printTreeElem(TreeElemType d)
{
printf("%d ",d);
return OK;
}
int printTreeNode(BiNode *node)
{
printf("curNode:%p L:%p, data:%2d, R:%p\n",node,node->l,node->data,node->r);
}
int printStack(LinkStack L)
{
LinkStack p;
p=L;
if(p->next==NULL)
printf("当前栈为空");
while(p->next)
{
p=p->next;
printTreeNode((BiNode*)p->data);
}
printf("end of stack----------------\n");
return 0;
}
//------------------------------------------
BiNode * newNode()
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
int CreateSubTree(BiTree *T,TreeElemType *all,int i)
{
if ((all[i]==0)||i>15)
{
*T=NULL;
return OK;
}
*T=newNode();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15*/
TreeElemType allNode[16]={0,1,2,3,0,0,4,5,0,0, 0, 0, 6, 0, 0, 0};
//TreeElemType allNode[16]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
void CreateBiTree(BiTree *T)
{
/*
1
/ \
2 3
/ \
4 5
/
6
*/
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15*/
//TreeElemType allNode[16]={0,1,2,3,0,0,4,5,0,0, 0, 0, 6, 0, 0, 0};
/*
1
/ \
2 3
/ \ / \
4 5 6 7
/ \ /\ / \ / \
8 9 10 11 12 13 14 15
*/
/* 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15*/
//TreeElemType allNode[16]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
CreateSubTree(T,allNode,1);
}
/*1 2 3 4 6 5*/
int PreOrderTraverse(BiTree T,int (*Visit)(TreeElemType d))
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit))
return OK;
return ERROR;
} else return OK;
}
/*2 6 4 5 3 1 */
int PostOrderTraverse(BiTree T,int (*Visit)(TreeElemType d))
{
if(T){
if(T->l)
PostOrderTraverse(T->l,Visit);
if(T->r)
PostOrderTraverse(T->r,Visit);
if(Visit(T->data)){
return OK;
}else
return ERROR;
} else return OK;
}
/*2 1 6 4 3 5 */
int InOrderTraverse(BiTree T,int (*Visit)(TreeElemType d))
{
if(T){
if(T->l)
InOrderTraverse(T->l,Visit);
if(Visit(T->data)){
if(T->r)
InOrderTraverse(T->r,Visit);
return OK;
}else
return ERROR;
} else return OK;
}
//请参考随后函数的注释
/*1 2 3 4 5 6 */
int LayerOrderByStackTraverse2(BiTree T,int (*Visit)(TreeElemType d))
{
//s1存储每层的所有树节点，次序是逆序（左边的节点在栈下方）
//s2是为了正确顺序输出节点，从s1反序而来的，左边的节点在栈上方）
LinkStack s1,s2;
initStack(&s1);
initStack(&s2);
BiNode * node;
if(T==NULL)
return ERROR;
pushStack(s1,T);
while(lenStack(s1)){
while(lenStack(s1)){ //从s1反序生成s2，左边的节点在栈上方）
popStack(s1,&node);
pushStack(s2,node);
}
while(lenStack(s2)){ //从s2出栈并输出节点，是层序的正确顺序
popStack(s2,&node);
printTreeNode(node);
//按层序正确顺序将当前层的下层结点压入s1，s1中左边的节点在栈下方
if(node->l)
pushStack(s1,node->l);
if(node->r)
pushStack(s1,node->r);
} //循环结束后，s1中保存了下一层节点信息
}
return OK;
}
/*
以下代码写好后，发现了以下文章：
双栈法对二叉树进行层序遍历
https://blog.csdn.net/qq_46477898/article/details/110142364
typedef struct BinaryTree
{
char data;
struct BinaryTree* lchild;//左孩子
struct BinaryTree* rchild;//右孩子
}BinaryTree,*Bitree;
void flow_traverse(Bitree T)//层序遍历
{
stack<Bitree>s1,s2;//定义两个栈
Bitree p = T;
cout << p->data;
s1.push(p->rchild);
s1.push(p->lchild);//将根结点的左右孩子压入栈1
while (1)
{
if (s1.empty() && s2.empty())//循环结束条件
break;
while(!s2.empty())
{
if (s2.top()->rchild != NULL)
s1.push(s2.top()->rchild);
if(s2.top()->lchild != NULL)
s1.push(s2.top()->lchild);
s2.pop();
}
while (!s1.empty())
{
cout << s1.top()->data;
s2.push(s1.top());
s1.pop();
}
}
}
从而精简掉s3栈，且省略了交换两个栈的过程。
精简后的代码为函数：LayerOrderByStackTraverse2
*/
/*1 2 3 4 5 6 */
int LayerOrderByStackTraverse(BiTree T,int (*Visit)(TreeElemType d))
{
//s1存储每层的所有树节点，次序是逆序（左边的节点在栈下方）
//s2是存储当前层节点的下层所有节点，次序也是逆的
//s3是为了正确顺序输出节点，从s1反序而来的，左边的节点在栈上方）
//temp是s2和s1的中转变量，为了下次循环能够处理下一层节点。
LinkStack s1,s2,s3,temp;
initStack(&s1);
initStack(&s2);
initStack(&s3);
BiNode * node;
if(T==NULL)
return ERROR;
pushStack(s1,T);
while(lenStack(s1)){
while(lenStack(s1)){ //从s1反序生成s3，左边的节点在栈上方）
popStack(s1,&node);
pushStack(s3,node);
}
while(lenStack(s3)){ //从s3出栈并输出节点，是层序的正确顺序
popStack(s3,&node);
printTreeNode(node);
//按层序正确顺序将当前层的下层结点压入s2，s2中左边的节点在栈下方
if(node->l)
pushStack(s2,node->l);
if(node->r)
pushStack(s2,node->r);
} //循环结束后，s2中保存了下一层节点信息
//以下交换s2和s1所指向的栈，以便下次循环通过s1来处理下一层节点
temp=s1;
s1=s2;
s2=temp;
}
return OK;
}
int main()
{
printf(" 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15\n");
printf("allNode[16]={");
for(int i=0;i<16;i++)
printf("%2d,",allNode[i]);
printf("};\n");
printf("%s\n%s\n%s\n%s\n%s\n%s\n%s\n",
" 1",
" / \\",
" 2 3",
" / \\",
" 4 5",
" /",
" 6"
);
printf("%s\n%s\n%s\n%s\n%s\n%s\n%s\n",
" 1",
" / \\",
" 2 3",
" / \\ / \\",
" 4 5 6 7",
" / \\ /\\ / \\ / \\",
"8 9 10 11 12 13 14 15 "
);
BiTree root;
CreateBiTree(&root);
printf("PreOrder:\n");
PreOrderTraverse(root,printTreeElem);
printf("\n");
printf("InOrder:\n");
InOrderTraverse(root,printTreeElem);
printf("\n");
printf("PostOrder:\n");
PostOrderTraverse(root,printTreeElem);
printf("\n");
printf("LayerOrderByStackTraverse:\n");
LayerOrderByStackTraverse2(root,printTreeElem);
printf("\n");
getch();
return 0;
}
zmofun@163.com 于 2023-4-15
评论已关闭