先序非递归遍历二叉树,主要是利用了栈的先进后出原理,用一个栈即可实现该算法,下面我们一起来看一下如何来实现吧
目录
先序建立二叉树
先序递归遍历二叉树
先序非递归遍历二叉树
在进行先序非递归遍历之前,我们需要先建立一个二叉树,这里采用先序的方法建立二叉树
void Create(BiTree *t){
BiTree q; //树结点
char s; //输入的值
scanf("%c",&s);
getchar();
if(s=='#'){ //当建立时某个树没有左孩子或右孩子时,我们输入一个#
*t=NULL;
return;
}
q=(BiTree)malloc(sizeof(BiTree)); //分配内存
q->data=s;
*t=q; //根结点
Create(&q->lchild); //先序建立左子树
Create(&q->rchild); //先序建立右子树
}
在建立完二叉树后,我们先来看看递归的算法是如何实现的
void xianxu(BiTree t){
if(!t) return; //当树节点为空时,返回
printf("%c",t->data); //打印跟结点
xianxu(t->lchild); //先序遍历左子树
xianxu(t->rchild); //先序遍历右子树
}
下面我们来看看如何非递归对二叉树进行遍历
void fxianxu(BiTree t){
BiTree stack[100],p; //我们需要一个保存树结点的栈
int top=0; //栈顶指针
for(int i=0;i<100;i++){
stack[i]=0; //初始化栈
}
p=t; //根结点
while(p){
printf("%c",p->data); //打印根结点
if(p->rchild){ //先从右边开始,如果右子树不为空
stack[top++]=p->rchild; //右子树入栈
}
if(p->lchild){ //再看左子树,如果左子树非空
p=p->lchild; //继续遍历下一个左子树
}else if(top>0){ //如果左子树为空但是栈不为空
p=stack[--top]; //此时栈顶是当前树的右子树,将右子树出栈
}else{ //当左子树为空,且栈中没有元素时,遍历结束
p=0;
}
}
}
以上代码理解起来有点抽象,我们举个例子来说明一下:
假设现在我们输入了AB##C##,这是棵最简单的二叉树,A是根结点,B是A的左子树,C是A的右子树,我们用非递归方法对其进行遍历,先看A的右子树,发现它有右子树,右子树是C,C入栈,再看A的左子树,发现它有左子树,左子树为B,我们令B为新的树结点,第一次循环结束,开始第二次循环,我们先看右子树,发现B没有右子树,不做任何操作,再看B的左子树,发现B也没有左子树,但是当前栈中有元素C,我们出栈,并令C为新的树结点,第二次循环结束,执行第三次循环,我们还是先看C的右子树,发现C没有右子树,不做任何操作,再看C的左子树,发现左子树为空,并且当前栈中没有元素,我们令新的树结点为空,即可跳出循环
我们最后来总结一下如何对二叉树进行先序非递归的遍历:
第一步,打印根结点
第二步,先看树结点的右子树,存在,入栈
第三步,再看树结点的左子树,存在,令其为新的树结点,不存在看该树结点右子树是否存在(就是看栈中是否有元素),存在右子树就让右子树为新的树结点继续循环,当某个树结点既没有左子树也没有右子树时结束循环