树型结构是信 息的一种 重要组织形式
树是最为常用 的数据结构它的实际应用非常广泛二叉
序遍历有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找二叉树均能提供一种十分有效的方法比如在查找问题上任何借助于比较法查找长度为Ⅳ的一个序表的算法都可以表示成一株二叉树。反之任何二叉树都对应一个查找有序表的有效方法根据树的数学理论对于算法分析的某些最有启发性的应用是与给出用于计算各种类型中不同树的数目的公式有关的。
本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序让我们对二叉树的理解有更好的效果。
关键词二叉树的遍历左子树右子树递归
目录
1 .问题概述
1 . 1问题描述
创建二叉树并遍历基本要求
该程序集成了如下功能
1 二叉树的建立
2递归和非递归先序中序和后序遍历二叉树
3按层次遍历二叉树
4交换二叉树的左右子树
5输出叶子结点
6递归和非递归计算叶子结点的数目
1 . 2需求分析
分先序遍历中序遍历和后序遍历三种情况考虑。
1 .先序遍历当二叉树非空时按以下顺序遍历否则结束操作① 访问根结点
② 按先序遍历规则遍历左子树
③ 按先序遍历规则遍历右子树
2. 中序遍历当二叉树非空时按以下顺序遍历否则结束操作① 按中序遍历规则遍历左子树
② 访问根结点
③ 按中序遍历规3遍历右子树。
3.后序遍历当二叉树非空时按以下顺序遍历否则结束操作① 按后序遍历规则遍历左子树
② 按后序遍历规则遍历右子树
1 . 3设计内容和要求
对任意给定的二叉树顶点数自定建立它的二叉链表存贮结构并利用栈的五种基本运算清空堆栈、压栈、弹出、取栈顶元素、判栈空实现二叉树的先序、 中序、后序三种周游输出三种周游的结果。
1 .4流程图及结构图
开始i=0
图1b
c
a
图1 .2二叉链表存储结构模拟图
2.概要设计
2. 1数据结构设计
1 二叉树结点数据类型定义为template<typename T>struct BiNode
{
BiNode<T>*rchi ld,*lchi ld;//指向左孩子的指针
T data;//结点数据信息};
2 二叉树数据类型定义为template<typename T>class BiTree{template<typename T>friend ostream&operator<<(ostream&os,BiTree<T>&bt);publ ic:B i Tree();//无参构造函数
BiTree(int m){};//有参空构造函数
BiTree(T ary[], int num,T none);//有参构造函数
B i Tree();//析构函数void preorder();//递归前序遍历void inorder();//递归中序遍历void postorder();//递归后续遍历void levelorder();//层序遍历int count();//计算二叉树的结点数void display(ostream&os);//打印二叉树有层次
void creat();//创建二叉树protected: //以下函数供上面函数调用//对应相同功能
Voidcreat(BiNode<T>*&root);//创建void release(BiNode<T>*&root);//删除
BiNode<T>*Bui ld(Tary[], intnum,T none, int idx);//用数组创建二叉树void PreOrder(BiNode<T>* root);//前序遍历void PostOrder(BiNode<T>* root);//后续遍历void LevelNum(BiNode<T>* root);//层序遍历void preorder(Bi Node<T>* root);//递归前序遍历void inorder(BiNode<T>* root);//递归中序遍历void postorder(BiNode<T>* root);//递归后续遍历void levelorder(BiNode<T>*root);//层序遍历int count(BiNode<T>* root);//计算结点数void display(ostream&os,BiNode<T>* root, int dep);//打印static bool leastCommanAncestor(BiNode<T>*root,T va,T vb,BiNode<T>private:BiNode<T>*rootptr;
};
2. 2源程序代码
#include <iostream>usi ng namespace std;
*******************************************************************
******************
T data;
BTNode<T> * Lch i l d,*Rch i l d;
BTNode(T nodeVal ue = T() ,BTNode<T>* l ef tNode = NULL,BTNode<T>*r i ghtNode =NULL )
:data(nodeValue) ,Lchi ld( l ef tNode) ,Rchi ld( r ightNode){ } //可选择参数的默认构造函数
} ;
*******************************************************************
*******************
//二叉树的建立template <class T>voi d createB i nTree(BTNode<T> * &root )
{
BTNode<T>* p = root ;
BTNode<T>* k;
T nodeValue ;ci n>>nodeVal ue;i f (nodeValue==-1 )
{r o o t=NULL;
}else
{root=new BTNode<T>() ;root->data = nodeVal ue;createBinTree( root->Lchi ld) ;createBinTree( root->Rchi ld) ;
}
//二叉树的先序遍历template <class T>void preOrder( BTNode<T> * &p)
{i f (p)
{cout<<p->data<<" " ;preOrder(p->Lchi ld) ;preOrder(p->Rchi ld) ;
}
}
*******************************************************************
*******************
//二叉树的中序遍历template <class T>void i nOrder(BTNode<T> * &p)
{i f (p)
{i nOrder(p->Lchi ld) ;cout<<p->data<<" " ;i nOrder(p->Rchi ld) ;
}
}
*******************************************************************
*******************
//二叉树的后序遍历
