遍历数据结构课程设计 二叉树的遍历 修订-可编辑

树型结构是信 息的一种 重要组织形式

树是最为常用 的数据结构它的实际应用非常广泛二叉

序遍历有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找二叉树均能提供一种十分有效的方法比如在查找问题上任何借助于比较法查找长度为Ⅳ的一个序表的算法都可以表示成一株二叉树。反之任何二叉树都对应一个查找有序表的有效方法根据树的数学理论对于算法分析的某些最有启发性的应用是与给出用于计算各种类型中不同树的数目的公式有关的。

本文对二叉树以及二叉树的各种功能做介绍以及写出一些基本的程序让我们对二叉树的理解有更好的效果。

关键词二叉树的遍历左子树右子树递归

目录

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

}

}

*******************************************************************

*******************

//二叉树的后序遍历