/**
** name: 二叉树的创建和遍历
** author: Dev|il
** date: 2011-10-15 12:56
**/
#include <iostream>
#include <queue>
using namespace std;
const int MAX_TREE_SIZE = 1000;
typedef int ElemType;
typedef bool Status;
typedef ElemType bitTree[MAX_TREE_SIZE]; //树的线性定义,只适合存储满二叉树
const ElemType END = -1;
//树的二叉链表定义
typedef struct LNode{
ElemType data;
struct LNode *lchild, *rchild;
}BitNode, *BiTree;
/////////////////////////////////函数的声明///////////////////////////////////////////
//按先序DLR输入二叉树节点的值,构造二叉链表表示的二叉树T
Status DLRCreateBiTree(BiTree &t);
//DLR
//采用二叉链表存储结构,visit是对节点操作的应用函数
//先序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e));
//LDR
//采用二叉链表的存储结构,visit是对节点操作的应用函数
//中序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e));
//LRD
//采用二叉链表的存储结构,visit是对节点操作的应用函数
//后序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e));
//采用二叉链表的存储结构,visit是对节点操作的应用函数
//层序遍历二叉树t,对每个节点调用visit函数一次且一次
//一旦visit操作失败,则函数操作失败
void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e));
//访问函数
Status visit(ElemType e);
//返回二叉树t的深度
int DLRBiTreeDepth(BiTree t);
///////////////////////////////////////////////////////////////////////////////
//////////////////////////////////函数的实现//////////////////////////////////
Status DLRCreateBiTree(BiTree &t)
{
ElemType e;
cin>>e;
if(e == END)
t = NULL;
else
{
t = (BiTree)malloc(sizeof(BitNode)); //创建节点,相当于建立头
if(!t)
return false;
t->data = e; //赋数据
if(!DLRCreateBiTree(t->lchild)) //建立左子树
return false;
if(!DLRCreateBiTree(t->rchild)) //建立右子树
return false;
}
return true;
}
Status PreOrderTraverse(BiTree t, Status (* visit)(ElemType e))
{
if(t)
{
if(visit(t->data))
if(PreOrderTraverse(t->lchild, visit))
if(PreOrderTraverse(t->rchild, visit))
return true;
return false;
}else
return true;
}
Status InOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
if(t)
{
if(InOrderTranverse(t->lchild, visit))
if(visit(t->data))
if(InOrderTranverse(t->rchild, visit))
return true;
return false;
}else
return true;
}
Status PostOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
if(t)
{
if(PostOrderTranverse(t->lchild, visit))
if(PostOrderTranverse(t->rchild, visit))
if(visit(t->data))
return true;
return false;
}else
return true;
}
void LevelOrderTranverse(BiTree t, Status(*visit)(ElemType e))
{
queue<BiTree> q;
q.push(t);
while(!q.empty())
{
BiTree cur = q.front();
q.pop();
visit(cur->data);
if(cur->lchild)
q.push(cur->lchild);
if(cur->rchild)
q.push(cur->rchild);
}
}
Status visit(ElemType e)
{
cout<<e<<" ";
return true;
}
int BiTreeDepth(BiTree t)
{
int Ldepth, Rdepth, max;
if(!t)
return 0;
else
{
Ldepth = BiTreeDepth(t->lchild);
Rdepth = BiTreeDepth(t->rchild);
max = Ldepth > Rdepth ? Ldepth : Rdepth;
return max + 1;
}
}
/////////////////////////////////////////////////////////////////////////////
int main()
{
BiTree t;
DLRCreateBiTree(t);
cout<<"先序遍历:";
PreOrderTraverse(t, visit);
cout<<endl<<"中序遍历:";
InOrderTranverse(t, visit);
cout<<endl<<"后序遍历:";
PostOrderTranverse(t, visit);
cout<<endl<<"层次遍历:";
LevelOrderTranverse(t, visit);
cout<<endl<<"树的深度:";
cout<<BiTreeDepth(t);
cout<<endl;
return 0;
}
分享到:
相关推荐
链表实现二叉树创建和遍历,三种遍历方式实现,二叉树
以二叉链表存储二叉树,按照完全二叉树的编号顺序输入节点,创建二叉树,最后,给出三种遍历的结果
采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,根据输入的一棵二叉树的完整先序遍历序列(子树空用’#’表示),建立...
二叉树的建立和遍历算法 数据结构课程设计用
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
利用递归方式完成二叉树的简单创建以及遍历。
大型二叉树建立与遍历系统\大型二叉树建立与遍历系统.
c语言中关于二叉树的先序遍历,链表的创建
数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,其中包含了:二叉树的定义、二叉树的递归遍历、二叉树基本操作。 数据结构实用教程之二叉树,...
大连理工大学数据结构上机 二叉树三种遍历,先序和中序建立二叉树,后序和中序建立二叉树,二叉搜索树查找,删除,插入
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
c语言,二叉树的建立和遍历操作。数据结构Bitree
二叉树创建及遍历算法
编写采用二叉链表形式存储的二叉树的创建、先序、中序、后序和按层遍历的算法。 2 编写将一棵二叉树的所有左右子树进行交换的算法。 提示:验证是否交换可以调用二叉树的遍历算法,比较输出结点序列。 3 编写一个...
本程序是数据结构课程设计作业,实现对二叉树的创建,遍历 找到相应结果,删除等操作。
二叉树的创建与遍历,使用递归调用,含前序遍历、中序遍历、后序遍历、层序遍历
C实现二叉树的建立及先中后序的遍历,控制台程序,在各版本vs上均可运行
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...