二叉树的三种遍历算法的实现（前序、中序、后序）递归与非递归 |
您所在的位置：网站首页 › 树与二叉树的遍历 › 二叉树的三种遍历算法的实现（前序、中序、后序）递归与非递归 |
二叉树的三种遍历算法的实现（前序、中序、后序）递归与非递归
|
二叉树的三种遍历算法的实现（前序、中序、后序）递归与非递归
1、二叉树的定义
二叉树是n（n>=0）个数据元素的有限集，含有唯一的称为根的元素，且，其余元素分成两个互不相交的子集，每一个子集本身也是一个二叉树，分别称为左子树和右子树。集合为空的二叉树简称为空树，二叉树中的元素也称为节点。这是一个递归的定义。 2、二叉树的存储结构： 2.1 顺序存储结构 typedef struct{ TElemType *data;//存储空间的基地址 int nodenum;//树中节点的个数 }SqBiTree;
由此可以看出这种存储方式比较浪费空间。 2.2 链式存储结构
若二叉树为空，则空操作否则 （1）访问根节点 （2）先序遍历左子树 （3）先序遍历右子树 void Preorder(BiTree T,void(*visit)(BiTree)) { if(T) { visit(T); Preorder(T->lchild,visit); Preorder(T->rchild,visit); } } 3.2中序遍历二叉树（递归实现）若二叉树为空，则空操作否则 （1）中序遍历左子树 （2）访问根节点 （3）中遍历右子树 void Preorder(BiTree T,void(*visit)(BiTree)) { if(T) { Preorder(T->lchild,visit); visit(T); Preorder(T->rchild,visit); } } 3.3后序遍历二叉树（递归实现）若二叉树为空，则空操作否则 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根节点 4、二叉树三种遍历的非递归实现 4.1算法说明当二叉树不为空时，中序遍历二叉树的任务可以由三项子任务组成，即遍历左子树、访问根节点、遍历右子树，其中第一和第三项任务比较复杂，但可以大事化小，继续分解为两项较小的遍历任务和一项访问任务，中间的这项任务比较单纯，可以直接处理，小事化了。 可以将栈看成存放任务书的柜子，初始化时，栈中只有一项任务，即中序遍历二叉树，之后每从栈中取出一份任务书，即将任务复杂程度进行相应的处理，直到栈为空。 4.2伪代码 typedef enum {Travel = 1,Visit = 0}TaskType;//Travel = 1:工作状态为遍历。Visit=0:工作状态为访问 typedef struct{ BiTree ptr; TaskType task }SElemType;//栈元素 void InOrder(BiTree T,void(*visit)(TElemType e)) {//利用栈实现中序遍历二叉树，T为指向二叉树根节点的头指针 InitStack(&S);//初始化栈 e.ptr = T;//e为栈元素 e.task = Travel; if(T) Push(&S,e);//布置初始任务 while(!IsEmpty(S)) {//每次处理一项任务 Pop(&S,&e); if(e.task == Visit) visit(e.ptr->data);//处理访问任务 else { if(e.ptr)//处理非空树的遍历任务 { p = e.ptr; e.ptr = p->rchild; Push(&S,e);//最不迫切的任务右子树进栈 e.ptr = p; e.task = Visit; Push(&S,e);//处理访问任务的工作状态和节点指针域进栈 e.ptr = p->lchild; e.task = Travel; Push(&S,e);//迫切的任务遍历左子树进栈 } } } }利用访问任务的进栈语句的不位置可以写出前序后序的非递归算法。 5完整代码 #include #include #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 #define OK 1 #define ERROR 0 #define INIT_SIZE 20 #define INCREMENT_SIZE 5 typedef int Status; typedef int TElemType; //存储结构 typedef struct BiNode{ TElemType data; struct BiNode *lchild, *rchild; }BiNode, *BiTree; typedef enum {Travel = 1,Visit = 0}TaskType; typedef struct{ BiTree ptr; TaskType task }SElemType;//栈元素 typedef struct{ SElemType *top; SElemType *base; int size; }Stack;//栈的数据结构 //初始化栈 Status InitStack(Stack *S) { S->base = (SElemType *)malloc(sizeof(SElemType)*INIT_SIZE); if(!S->base)exit(OVERFLOW); S->top = S->base; S->size = INIT_SIZE; return OK; } //判断是否为空 Status IsEmpty(Stack S) { if(S.base==S.top)return TRUE; return FALSE; } //进入栈 Status Push(Stack *S,SElemType e)//*S->top++=e { if((S->top - S->base) / sizeof(SElemType)>=S->size) { S->base = (SElemType*)realloc(S->base,(S->size+INCREMENT_SIZE)*sizeof(SElemType)); if(!S->base)exit(OVERFLOW); S->top = S->base + S->size;//从新申请了内存地址发生了变化 S->size += INCREMENT_SIZE; } *S->top = e;//先取*s->top 在++//*++S->top先加再取值； S->top++; return OK; } //pop Status Pop(Stack *S, SElemType *e) { if(S->top == S->base)return ERROR; *e = *--S->top; return OK; } //创建二叉树(输入0结束） Status CreateBiTree(BiTree *T) { TElemType s; scanf("%d",&s); if(s==0) *T=NULL; else{ *T = (BiTree)malloc(sizeof(BiNode)); if(!T) { return OVERFLOW; } (*T)->data = s; CreateBiTree(&(*T)->lchild);//修改指针的值使其指向创建的值 CreateBiTree(&(*T)->rchild); } return OK; } //访问元素 void visit(TElemType e) { printf("%d ",e); } //先序遍历递归实现 Status PreOrderTraverse(BiTree T,void(*visit)(TElemType e)) { if(T) { (*visit)(T->data); PreOrderTraverse(T->lchild,visit) ; PreOrderTraverse(T->rchild,visit); } } //中序遍历 Status InOrderTraverse(BiTree T,void(*visit)(TElemType e)) { if(T) { InOrderTraverse(T->lchild,visit); (*visit)(T->data); InOrderTraverse(T->rchild,visit); } } // houxu Status PostOrderTraverse(BiTree T,void(*visit)(TElemType e)) { if(T) { PostOrderTraverse(T->lchild,visit); PostOrderTraverse(T->rchild,visit); (*visit)(T->data); } } //前序遍历非递归 Status PreOrder(BiTree T,void(*visit)(TElemType e)) { Stack S; InitStack(&S); BiTree p; SElemType e; e.ptr = T; e.task = Travel; if(T) Push(&S,e); while(!IsEmpty(S)) { Pop(&S,&e); if(e.task == Visit) visit(e.ptr->data); else { if(e.ptr) { p = e.ptr; e.ptr = p->rchild; e.task = Travel; Push(&S,e); e.ptr = p->lchild; e.task = Travel; Push(&S,e); e.ptr = p; e.task = Visit; Push(&S,e); } } } } //中序遍历非递归 Status InOrder(BiTree T,void(*visit)(TElemType e)) { Stack S; InitStack(&S); BiTree p; SElemType e; e.ptr = T; e.task = Travel; if(T) Push(&S,e); while(!IsEmpty(S)) { Pop(&S,&e); if(e.task == Visit) visit(e.ptr->data); else { if(e.ptr) { p = e.ptr; e.ptr = p->rchild; Push(&S,e); e.ptr = p; e.task = Visit; Push(&S,e); e.ptr = p->lchild; e.task = Travel; Push(&S,e); } } } } //houxu非递归 Status PostOrder(BiTree T,void(*visit)(TElemType e)) { Stack S; InitStack(&S); BiTree p; SElemType e; e.ptr = T; e.task = Travel; if(T) Push(&S,e); while(!IsEmpty(S)) { Pop(&S,&e); if(e.task == Visit) visit(e.ptr->data); else { if(e.ptr) { e.task = Visit; Push(&S,e); p = e.ptr; e.ptr = p->rchild; e.task = Travel; Push(&S,e); e.ptr = p->lchild; e.task = Travel; Push(&S,e); } } } } int main() { BiTree T; printf("创建树，输入0为空树：\n"); CreateBiTree(&T); printf("先序遍历递归："); PreOrderTraverse(T, *visit); printf("\n中序遍历递归："); InOrderTraverse(T, *visit); printf("\n后序遍历递归："); PostOrderTraverse(T, *visit); printf("\n"); printf("\n前序非递归算法: "); PreOrder( T,*visit); printf("\n中序非递归算法: "); InOrder( T,*visit); printf("\n后序非递归算法: "); PostOrder( T,*visit); return 0; }输入数据
|
完全二叉树的存储方式 
一般二叉树的存储方式
【本文地址】