- #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://www.codesnippet.cn/detail/080520133199.html
来源: http://www.codesnippet.cn/detail/080520133199.html