武汉c培训
达内武汉中心

15271940953

热门课程

武汉C++培训:binarytree

  • 时间:2016-06-03
  • 发布:霜柒染
  • 来源:51CTO

#pragma once 
#include<iostream>
#include<queue>
#include<stack>
using namespace std;
template <class T>  //树的结构体
struct BinaryTreeNode
{
public:
    T _data;
    BinaryTreeNode<T>* _leftChild;
    BinaryTreeNode<T>* _rightChild;
 
public:
    BinaryTreeNode(const T& data)
        :_data(data)
        , _leftChild(NULL)
        , _rightChild(NULL)
    {}
 
    ~BinaryTreeNode()
    {}
};
 
template <class T>
class BinaryTree //树的封装
{
public:
    BinaryTreeNode<T>* _root;
 
public:
    BinaryTree()
        :_root(NULL)
    {}
 
    BinaryTree( T*a, size_t size)
    {
        size_t index = 0;
        _root = _CreateBiTree(a, index, size);
    }
 
    BinaryTree(const BinaryTree& tmp)
        :_root(NULL)
    {
        _root=_Copy(tmp._root);
 
    }
    ~BinaryTree()
    {
        Destory();
    }
 
    BinaryTree<T>& operator=( BinaryTree<T> tmp)
    {
        swap(_root, tmp._root);
        return *this;
 
    }
     
    void InOrder()//中序遍历递归方法
    {
        _InOrder(_root);
        cout << endl;
    }
 
    void PreOrder()//前序遍历递归方法
    {
        _PreOrder(_root);
        cout << endl;
    }
 
    void PosOrder()//后序遍历递归方法
    {
        _PosOrder(_root);
        cout << endl;
    }
 
    void LevelOrder()//层序遍历
    {
        queue<BinaryTreeNode<T>*> s ;
        s.push(_root);
        while (!s.empty())
        {
            BinaryTreeNode<T>* cur = s.front();
            cout<<cur->_data<<' ';
            if (cur->_leftChild)
                s.push(cur->_leftChild);
            if (cur->_rightChild)
                s.push(cur->_rightChild);
            s.pop();
        }
        cout << endl;
    }
 
    void Size()//节点数
    {
        int size = 0;
        cout<<_Size(_root,size)<<endl;
 
    }
 
    void Hight()//深度  /高度
    {
        cout << _Hight(_root) << endl;
    }
 
    void Destory()//销毁  
    {
        _Destory(_root);
        _root=NULL;
    }
 
    void LeafNum()//叶子节点数
    {
        int num = 0;
        _LeafNum(_root, num);
        cout <<num<<endl;
 
    }
 
    void PreOrderNonR()//前序 非递归  (借用栈)
    {
        if (_root == NULL)
            return;
        stack<BinaryTreeNode<T>*> s ;
         s.push(_root);
        while (!s.empty())
        {
            BinaryTreeNode<T>* cur;
            cur=s.top();
            s.pop();
            cout << cur->_data << ' ';
            if (cur->_rightChild)
                s.push(cur->_rightChild);
            if (cur->_leftChild)
                s.push(cur->_leftChild);
        }
        cout << endl;
    }
 
    void InOrderNonR() //中序 非递归
    {
        if (_root == NULL)
            return;
        stack<BinaryTreeNode<T>*> s;
        s.push(_root);
        BinaryTreeNode<T>* prev=NULL;
        BinaryTreeNode<T>* cur=NULL;
        while (!s.empty())
        {
            cur = s.top();
            if(prev != cur&&cur->_leftChild) //左不空 压左
            {
                s.push(cur->_leftChild);
            }
            else //左空   出栈 输出
            {
                cout << cur->_data << ' ';
                s.pop();
                if (!s.empty())
                    prev = s.top();//prev始终为出栈后的栈顶
                if (cur->_rightChild)//  cur右不空  压右
                {
                     
                    s.push(cur->_rightChild);
                     
                }
            }
        }
        cout << endl;
    }
 
    void PosOrderNonR()  //后续  非递归
    {
        if (_root == NULL)
            return;
        stack<BinaryTreeNode<T>*> s;
        BinaryTreeNode<T>* cur = NULL;
        BinaryTreeNode<T>* prev = NULL;
        BinaryTreeNode<T>* tmp = NULL;
        s.push(_root);                 
        while (!s.empty())
        {
            cur = s.top();
            if (prev != cur&&cur->_leftChild != NULL)//1.左不空且prev!=cur 压左 
                s.push(cur->_leftChild);
            else//左空
            {
                if (cur->_rightChild!=tmp  &&cur->_rightChild)//右不空 且 cur->right!=tmp 压右
                {
                    s.push(cur->_rightChild);
                }
                     
                else             //右空  输出 cur
                {
                    cout << cur->_data << ' ';
                    tmp = s.top();    //tmp(判断是否压右)始终为出栈前的栈顶
                    s.pop();
                    if (!s.empty())
                    {
                        prev = s.top();//prev(判断是否压右)始终为出栈后栈顶
                     
                    }
                }
            }      
        }
        cout << endl;
    }
 
protected://以下为递归的调用函数
 
    BinaryTreeNode<T>* _CreateBiTree(const T* tmp, size_t& index, size_t size)
    {
        BinaryTreeNode<T>* root = NULL;
        if (index < size&&tmp[index]!='#')
        {
            root = new BinaryTreeNode<T>(tmp[index]);
            root->_leftChild = _CreateBiTree(tmp, ++index, size);
            root->_rightChild = _CreateBiTree(tmp, ++index, size);      
        }
        return root;
    }
 
    void _InOrder(BinaryTreeNode<T>* &T)
    {
        if (T == NULL)
            return;
        _InOrder(T->_leftChild);
        cout << T->_data << ' ';
        _InOrder(T->_rightChild);
    }
 
    void _PreOrder(BinaryTreeNode<T>* &T)
    {
        if (T == NULL)
            return;
        cout << T->_data<<' ';
        _PreOrder(T->_leftChild);
        _PreOrder(T->_rightChild);
 
    }
 
    void _PosOrder(BinaryTreeNode<T>* &T)
    {
        if (T == NULL)
            return;
        _PosOrder(T->_leftChild);
        _PosOrder(T->_rightChild);
        cout << T->_data << ' ';
    }
 
    int _Size(BinaryTreeNode<T>* root,int & size)
    {
        if (root == NULL)
            return 0;
        size++;
        _Size(root->_leftChild, size);
        _Size(root->_rightChild, size);
        return size;
    }
 
    int _Hight(BinaryTreeNode<T>* root)
    {
        int hight = 1;
        if (root == NULL)
            return 0;
        hight += _Hight(root->_leftChild);
        int ritHight = 0;
            ritHight+= _Hight(root->_rightChild);
        if (hight < ritHight)
            hight = ritHight;
        return hight;
 
 
    }
    void _Destory(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
            return;
        BinaryTreeNode<T>* del = root;
         
        _Destory(del->_leftChild);
        _Destory(del->_rightChild);
        delete root;
             
        return;
    }
 
    void _LeafNum(BinaryTreeNode<T>* root,int& num)
    {
        if (root == NULL)
            return ;
        if (root->_leftChild == NULL&&root->_rightChild == NULL)
            ++num;
        _LeafNum(root->_leftChild,num);
        _LeafNum(root->_rightChild,num);
        return ;
    }
 
    BinaryTreeNode<T>* _Copy(BinaryTreeNode<T>* root)
    {
        if (root == NULL)
            return NULL;
        BinaryTreeNode<T>* newRoot = NULL;
        newRoot = new BinaryTreeNode<T>(root->_data);
        newRoot->_leftChild = _Copy(root->_leftChild);
        newRoot->_rightChild = _Copy(root->_rightChild);
        return newRoot;
 
    }
};
 
 
//测试用例
 
#include"binarytree.hpp"
 
using namespace std;
 
void test()
{
    int l[10] = { 1, 2, 3,'#', '#', 4, '#', '#', 5, 6 };
    int s[18] = { 1, 2, 3, 4, '#', '#', 5, '#', '#', 6,'#','#' ,7, 8, '#', '#', 9, 10 };
    BinaryTree<int> t1;
    BinaryTree<int> t2(s, 18);
    BinaryTree<int> t3(t2);
    t1 = t2;
    t2.PreOrder();
    t2.InOrder();
    t2.PosOrder();
    t2.LevelOrder();
    t2.Size();
    t2.Hight();
    t2.Destory();
    t3.InOrder();
    t1.InOrder();
    t3.LeafNum();
    t3.PreOrderNonR();
    t3.InOrderNonR();
    t3.PosOrderNonR();
}
 
int main()
{
    test();
    return 0;
}
上一篇:c++ 二叉树的线索化
下一篇:武汉C++培训:c++广义表
选择城市和中心
贵州省

广西省

海南省