返回顶部

收藏

二叉树(数据结构)

更多
#ifndef _BITREE_
#define _BITREE_

#include <iostream>
#include <string>
using namespace std;

template <class T>
struct BiNode   //二叉树的结点结构
{
  T data;       
  BiNode<T> * leftChild;
  BiNode<T> * rightChild;
};

template <class T>
class BiTree
{
public:
    BiTree();             //构造函数,初始化一棵二叉树,其前序序列由键盘输入
    ~BiTree();         //析构函数,释放二叉链表中各结点的存储空间
 BiNode<T> * Getroot();  //获得指向根结点的指针
    void PreOrder(BiNode<T> * root);     //前序遍历二叉树
    void InOrder(BiNode<T> * root);      //中序遍历二叉树
    void PostOrder(BiNode<T> * root);    //后序遍历二叉树
    void LeverOrder(BiNode<T> * root);   //层序遍历二叉树
private:
    BiNode<T> * root;         //指向根结点的头指针
    BiNode<T> * Creat( );     //构造函数调用
    void Release(BiNode<T> * root);   //析构函数调用 
};

/****************************************************/
/*        定义类中的成员函数                               */
/****************************************************/

/*
 *前置条件:二叉树不存在
 *输    入:无
 *功    能:构造一棵二叉树
 *输    出:无
 *后置条件:产生一棵二叉树 
 */
template <class T>
BiTree<T>::BiTree()
{
 this->root = Creat();
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:释放二叉链表中各结点的存储空间
 *输    出:无
 *后置条件:二叉树不存在 
 */
template <class T>
BiTree<T>::~BiTree()
{
 Release(root);
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:获取指向二叉树根结点的指针
 *输    出:指向二叉树根结点的指针
 *后置条件:二叉树不变 
 */
template <class T>
BiNode<T> * BiTree<T>::Getroot( )
{
 return root;
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:前序遍历二叉树
 *输    出:二叉树中结点的一个线性排列
 *后置条件:二叉树不变 
 */
template <class T>
void BiTree<T>::PreOrder(BiNode<T> * root)
{
 if(root==NULL)
  return;
 else
 {  
  cout<<root->data<<" ";
        PreOrder(root->leftChild);
  PreOrder(root->rightChild);
 }
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:中序遍历二叉树
 *输    出:二叉树中结点的一个线性排列
 *后置条件:二叉树不变 
 */
template <class T>
void BiTree<T>::InOrder (BiNode<T> * root)
{
    if(root==NULL)
  return;      //递归调用的结束条件           
    else
 { 
        InOrder(root->leftChild);    //中序递归遍历root的左子树
        cout<<root->data<<" ";    //访问根结点的数据域
        InOrder(root->rightChild);    //中序递归遍历root的右子树
 }
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:后序遍历二叉树
 *输    出:二叉树中结点的一个线性排列
 *后置条件:二叉树不变 
 */
template <class T>
void BiTree<T>::PostOrder(BiNode<T> * root)
{ 
    if(root==NULL)
  return;       //递归调用的结束条件
    else
 { 
        PostOrder(root->leftChild);    //后序递归遍历root的左子树
        PostOrder(root->rightChild);    //后序递归遍历root的右子树
        cout<<root->data<<" ";      //访问根结点的数据域
 }
}

/*
 *前置条件:二叉树已存在
 *输    入:无
 *功    能:层序遍历二叉树
 *输    出:二叉树中结点的一个线性排列
 *后置条件:二叉树不变
 */
template <class T>
void BiTree<T>::LeverOrder(BiNode<T> * root)
{
 const int MaxSize = 100;
 int front = 0;
 int rear = 0;  //采用顺序队列,并假定不会发生上溢
 BiNode<T>* Q[MaxSize];
    BiNode<T>* q;
 if (root==NULL)
  return;
 else
 {
  Q[rear++] = root;
  while (front != rear)
  {
   q = Q[front++];
       cout<<q->data<<" ";   
      if (q->leftChild != NULL)
    Q[rear++] = q->leftChild;  
   if (q->rightChild != NULL)
    Q[rear++] = q->rightChild;
  }
 }
}

/*
 *前置条件:空二叉树
 *输    入:数据ch;
 *功    能:初始化一棵二叉树,构造函数调用
 *输    出:无
 *后置条件:产生一棵二叉树
 */
template <class T>
BiNode<T> * BiTree<T>::Creat( )
{
 BiNode<T> * root;
 T ch;
 cout<<"请输入创建一棵二叉树的结点数据"<<endl;
 cin>>ch;
    if (ch=="#")
  root = NULL;
    else
 { 
      root = new BiNode<T>;       //生成一个结点
         root->data=ch;
         root->leftChild = Creat( );    //递归建立左子树
         root->rightChild = Creat( );    //递归建立右子树
    } 
    return root;
}

/*
 *前置条件:二叉树已经存在
 *输    入:无
 *功    能:释放二叉树的存储空间,析构函数调用
 *输    出:无
 *后置条件:二叉树不存在
 */
template <class T>
void BiTree<T>::Release(BiNode<T> * root)
{
  if (root != NULL)
  {                  
   Release(root->leftChild);   //释放左子树
      Release(root->rightChild);   //释放右子树
      delete root;
  }  
}

#endif
//该片段来自于http://outofmemory.cn

标签:c++,算法

收藏

0人收藏

支持

0

反对

0

»更多 您可能感兴趣的代码
  1. 2014-09-01 13:12:19计数排序 by lucasli
  2. 2014-09-10 11:32:48快速排序代码(自己写的,有点冗余) by sxgkwei
  3. 2014-10-27 10:07:37求一个数的所有质因子之和 by walker30
  4. 2014-11-16 12:05:30通用排序程序 by lucasli
  5. 2014-11-30 09:48:33数组逆序 by 灵剑子
  6. 2014-05-11 18:34:3821位水仙花数 by sxgkwei
  7. 2014-05-19 17:12:34数据结构 顺序栈 by qqmmcc
  8. 2014-05-22 11:38:42求两个数的最小公倍数 by 蟋蟀哥
  9. 2014-05-22 15:43:22神经元模型 by lucasli
  10. 2014-06-05 11:30:06经过优化后的快速排序算法 by 灵剑子
  11. 2014-06-07 20:27:27解数独 by niutao.linux
相关聚客文章
  1. surgesoft 发表 2014-10-28 08:01:58 LeetCode OJ: Restore IP Addresses
  2. espace 发表 2015-07-18 17:43:14 Two Sum
  3. abyssss 发表 2014-05-20 03:23:39 数据结构 最小堆 数组实现
  4. dianlujitao 发表 2014-10-17 13:56:48 POJ 1611 The Suspects
  5. bystander 发表 2013-05-15 10:37:24 倒水问题求解(C++)
  6. dianlujitao 发表 2014-10-17 14:11:26 POJ 1328 Radar Installation
  7. bystander 发表 2013-04-01 10:12:37 [藏]关于B树的一篇文章
  8. lvfuyu 发表 2015-04-12 08:53:30 [hihocoder]矩阵快速幂
  9. lvfuyu 发表 2015-04-18 09:13:32 [hihocoder]二分查找
  10. dianlujitao 发表 2013-11-04 11:49:12 【NOIP2012提高组】Vigenère密码 模拟 打表
  11. leaver 发表 2013-05-27 02:55:49 求整数1-N范围和为N的所有组合
  12. cijianzy 发表 2015-05-01 14:20:33 修复了中文维基百科基数排序C++代码的一个bug

发表评论