首页 > 代码库 > 数据结构-二叉树的各种遍历(先中后层序!!)
数据结构-二叉树的各种遍历(先中后层序!!)
最近在写数据结构中二叉树的遍历,这里总结一下:
先序递归遍历:
void PreTravel(BiTree T) {//前序递归遍历 if(T) { printf("%c",T->data); PreTravel(T->lchild); PreTravel(T->rchild); } }
中序递归遍历:
void MidTravel(BiTree T) {//中序递归遍历 if(T) { MidTravel(T->lchild); printf("%c",T->data); MidTravel(T->rchild); } }
后序递归遍历:
void PostTravel(BiTree T) {//后序递归遍历 if(T) { PostTravel(T->lchild); PostTravel(T->rchild); printf("%c",T->data); } }
先序非递归遍历:
void PreOrder(BiTree &T) {//先序非递归遍历 stack<BiTree> s; BiTree p = T; while(p || !s.empty()) { if(p) { printf("%c", p->data); s.push(p); p = p->lchild; } else { p = s.top(); s.pop(); p = p->rchild; } } }
中序非递归遍历:
void InOrder(BiTree T) {//中序非递归遍历 stack<BiTree> s; BiTree p = T; while(p || !s.empty()) { if(p) { s.push(p); p = p->lchild; } else { p = s.top(); printf("%c", p->data); s.pop(); p = p->rchild; } } }
后序非递归遍历:
void PostOrder(BiTree &T) {//后序非递归遍历(加入一个标志变量visit,判断左右子树是否进栈) stack<BiTree> s; BiTree p = T; p->visit = false; if(T) s.push(T); while(!s.empty()) { p = s.top(); if(p->visit) { printf("%c", p->data); s.pop(); } else { if(p->rchild) { p->rchild->visit = false; s.push(p->rchild); } if(p->lchild) { p->lchild->visit = false; s.push(p->lchild); } p->visit = true; } } }
void PostOrder1(BiTree &T) {//后序非递归遍历 (销毁了树的结构,不可取) stack<BiTree> s; BiTree q, p = T; while(p || !s.empty()) { if(p) { s.push(p); q = p; p = q->lchild; q->lchild = NULL; } else { q = s.top(); p = q->rchild; q->rchild = NULL; if(p) { s.push(p); q = p; p = q->lchild; q->lchild = NULL; } else { p = s.top(); printf("%c", p->data); s.pop(); if(!s.empty()) { p = s.top(); p = p->lchild; } else return; } } } }
层序遍历:
void LevelOrder(BiTree &T) {//层序遍历 queue<BiTree> q; q.push(T); BiTree p; while(!q.empty()) { p = q.front(); printf("%c", p->data); q.pop(); if(p->lchild) q.push(p->lchild); if(p->rchild) q.push(p->rchild); } }
主函数调用:
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <cstdlib> #include <stack> #include <queue> #include "constant.h" using namespace std; typedef struct BiTNode { char data; bool visit; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; void Print(char a) { printf("%c", a); return; } void CreatBiTree(BiTree &T) {//前序法创建二叉树 char ch; if((ch=getchar())=='#') T=NULL; else { T=(BiTNode*)malloc(sizeof(BiTNode)); if(!T) exit(1); T->data=http://www.mamicode.com/ch;>数据结构-二叉树的各种遍历(先中后层序!!)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。