首页 > 代码库 > 数据结构-二叉树的各种遍历(先中后层序!!)

数据结构-二叉树的各种遍历(先中后层序!!)


最近在写数据结构中二叉树的遍历,这里总结一下:


先序递归遍历:

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;>

数据结构-二叉树的各种遍历(先中后层序!!)