教育改变生活

标题: 【数据结构】二叉树先序遍历的非递归实现 [打印本页]

作者: wander 时间: 2023-9-5 16:00
标题: 【数据结构】二叉树先序遍历的非递归实现
本帖最后由 wander 于 2023-9-5 16:02 编辑

二叉树先序遍历的非递归实现

二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现，以下图所示二叉树为例，其 C 语言实现代码为：

#include <stdio.h>
#include <string.h>
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
*T=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->data=1;
(*T)->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
//前序遍历使用的进栈函数
void push(BiTNode** a,BiTNode* elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top--;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode* getTop(BiTNode**a){
return a[top];
}
//先序遍历非递归算法
void PreOrderTraverse(BiTree Tree){
BiTNode* a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {
p=getTop(a);//取栈顶元素
pop();//弹栈
while (p) {
displayElem(p);//调用结点的操作函数
//如果该结点有右孩子，右孩子进栈
if (p->rchild) {
push(a,p->rchild);
}
p=p->lchild;//一直指向根结点最后一个左孩子
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("先序遍历: \n");
PreOrderTraverse(Tree);
}

运行结果先序遍历:
1 2 4 5 3 6 7

欢迎光临教育改变生活 (http://bbs.goldoar.com/)