`
阿尔萨斯
  • 浏览: 4110453 次
社区版块
存档分类
最新评论

数据结构(C实现)------- 遍历二叉树

 
阅读更多

本文是自己学习所做笔记,欢迎转载,但请注明出处:http://blog.csdn.net/jesson20121020

二叉树是另一中树型结构,它的特点是每个结点至多只有两棵子树(即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。

根据二叉树的的递归定义可知,二叉树是由3个基本单元组成,根结点、左子树和右子树,因此,若能依次遍历这三部分,便是遍历了整个二叉树。假如以L、D、R分别表示遍历左子树、访问根结点和遍历右子树,则可能有DLR、LDR、LRD、DRL、RDL、RLD这6种遍历二叉树的方案。若限定先左后右,则只有前3种情况,分别称为先序遍历、中序遍历和后序遍历,另外,还有一种遍历方法,即从上到下,从左到右依次遍历二叉树的每个结点,称之为层次遍历。 故,共有4种遍历二叉树的方法。

二叉树遍历操作定义:

1. 先序遍历二叉树的操作定义:

若二叉树为空,则空操作;否则

1) 访问根结点

2) 先序遍历左子树

3) 先序遍历右子树

2. 中序遍历二叉树的操作定义:

若二叉树为空,则空操作;否则

1) 中序遍历左子树

2) 访问根结点

3) 中序遍历右子树

3. 后序遍历二叉树的操作定义:

若二叉树为空,则空操作;否则

1) 后序遍历左子树

2) 后序遍历右子树

3) 访问根结点

4. 层次遍历二叉树的操作定义:

若二叉树为空,则空操作;否则

1) 从上到下

2) 同一层,从左到右依次遍历

二叉树的存储结构:

1. 顺序存储结构:

#define MAX_TREE_SIZE 100
typedef char TElemType; 
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;

2. 链式存储结构:

//二叉树的的
#define MAXSIZE 100 //二叉树中最多的结点数 
typedef char TElemType; 
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

二叉树的遍历具体实现:

#include <stdio.h>
#include <stdlib.h>

//二叉树的的
#define MAXSIZE 100 //二叉树中最多的结点数 
typedef char TElemType; 
typedef struct BiTNode{
	TElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//定义函数指针
typedef void(* Visit)(BiTree);

//二叉树的初始化
void Init_BiTree(BiTree *T){
	*T = NULL;
}

//判断二叉树是否为空,返回1
int IsEmpty_BiTree(BiTree *T){
	return *T == NULL;
}

//创建二叉树
void Create_BiTree(BiTree *T){
	char ch;
	ch = getchar();
	//当输入的是"#"时,认为该子树为空
	if(ch == '#')
		*T = NULL;
	//创建树结点
	else{
		*T = (BiTree)malloc(sizeof(BiTNode));
		(*T)->data = ch; //生成树结点
		//生成左子树
		Create_BiTree(&(*T)->lchild);
		//生成右子树
		Create_BiTree(&(*T)->rchild);
	}
}

//输出结点的值
void Print_BiTreeNode(BiTree T){
	printf("%c\t",T->data);
	
}

//先序遍历二叉树
void PreOrder_BiTree(BiTree T,Visit visit){
	if(!IsEmpty_BiTree(&T)){
		visit(T);
		PreOrder_BiTree(T->lchild,visit);
		PreOrder_BiTree(T->rchild,visit);
	}
}
//中序遍历二叉树
void InOrder_BiTree(BiTree T,Visit visit){
	if(!IsEmpty_BiTree(&T)){
		InOrder_BiTree(T->lchild,visit);
		visit(T);
		InOrder_BiTree(T->rchild,visit);
	}
}

//后序遍历二叉树 
void PostOrder_BiTree(BiTree T,Visit visit){
	if(!IsEmpty_BiTree(&T)){
		PostOrder_BiTree(T->lchild,visit);
		PostOrder_BiTree(T->rchild,visit);
		visit(T);
	}
}

//层次遍历二叉树 
void LevelOrder_BiTree(BiTree T,Visit visit){
	//用一个队列保存结点信息,这里的队列采用的是顺序队列中的数组实现
	int front = 0;
	int rear = 0;
	BiTree BiQueue[MAXSIZE];
	BiTree tempNode;
	if(!IsEmpty_BiTree(&T)){
		//将根结点加入到队列中 
		BiQueue[rear++] = T;
		
		while(front != rear){
			//取出队头元素,并使队头指针向后移动一位 
			tempNode = BiQueue[front++];
			//判断左右子树是否为空,若为空,则加入队列 
			if(!IsEmpty_BiTree(&(tempNode->lchild)))
				BiQueue[rear++] = tempNode->lchild;
			
			if(!IsEmpty_BiTree(&(tempNode->rchild)))
				BiQueue[rear++] = tempNode->rchild;
			
			//输出队头结点元素 
			//Vist_BiTreeNode(tempNode->data);
			visit(tempNode);
		}
	}
}

int main(){
	BiTree T;
	//将二叉树初始为一个空的二叉树
	Init_BiTree(&T);
	//创建二叉树
	Create_BiTree(&T);
	//先序遍历
	printf("\n先序遍历结果:");
	PreOrder_BiTree(T,Print_BiTreeNode);
	//中序遍历二叉树
	printf("\n中序遍历结果:");
	InOrder_BiTree(T,Print_BiTreeNode);
	//后序遍历二叉树 
	printf("\n后序遍历结果:");
	PostOrder_BiTree(T,Print_BiTreeNode);
	//层次遍历二叉树 
	printf("\n层次遍历结果:");
	LevelOrder_BiTree(T,Print_BiTreeNode);
	return 0;
}

二叉树的遍历结果:

给定二叉树,如,输入1247###5#8##36###










分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics