本文是自己学习所做笔记,欢迎转载,但请注明出处: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###
分享到:
相关推荐
C语言数据结构实现二叉树的建立与遍历.cpp
数据结构二叉树的遍历,采用C语言实现二叉树的非递归先序、中序、后序遍历算法
用堆栈实现二叉树遍历,C语言实现的数据结构
二叉树遍历,c语言 实现数据结构二叉树遍历
/****头文件"head.h"**********/ #include<stdio.h> #include<math.h> ...// 先序遍历二叉树T if (T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }
二叉树遍历的特点
一个用c语言实现的二叉树的 先序遍历,中序遍历、后序遍历的算法。
用c语言实现的二叉树的遍历,是数据结构中的经典案例。里面含有设计报告和源代码。代码拷贝出来即可运行。
数据结构 二叉树的遍历 自己写的代码,可以完整运行,适合数据结构课后实验
typedef struct Node {char data; struct Node *Lchild; struct Node *Rchild; }BiTNode,*BiTree; /*定义树*/ typedef struct {BiTree elem[Maxsize]; int top; }SeqStack;/*定义栈*/
数据结构实验,二叉树的建立与遍历,C语言
c语言,二叉树的建立和遍历操作。数据结构Bitree
参考资料:《数据结构》(C语言版)严蔚敏&&吴伟民&&米宁著 要求选用顺序存储结构和二叉链表存储结构实现抽象数据类型二叉树的基本操作。有个亮点是利用字符在dos界面显示二叉树的结构形态。 里面包含了完整的源程序和...
数据结构遍历二叉树算法(前序、中序、后序),C语言版程序(附完成版实验报告),完全可运,供大家参考。
数据结构 二叉树的遍历 课程设计 C/C ++ 语言
(2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,后序遍历; (4)实现递归到非递归方法的转变; 三、实验内容: 建立一棵用二叉树链表方式存储的二叉树,并...
运用C语言编写的二叉树遍历程序 先序遍历·中序遍历·后序遍历
C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例二叉树建立遍历冒泡排序快速排序等 C语言数据结构课程设计实例...
实验目的和要求: 掌握使用turboc2软件上机调试二叉树的基本方法; 掌握二叉树链表的结构和二叉树的建立过程; 掌握递归程序设计的特点和编程方法。
给出二叉树的中序遍历序列和后序遍历序列,编程还原该二叉树。 输入: 第1行为二叉树的中序遍历序列 第2行为二叉树的后序遍历序列 输出: 二叉树的按层遍历序列