二叉树实现

1.层次遍历可以用于寻找叶子节点，寻找路径，寻找树的最短最大高度的非递归实现。
2.中序遍历搜索二叉树后是升序的序列。这个特性可以判断搜索二叉树的有效性。
3.使用双向的递归可以遍历每个分支的每个节点。

/*
 * Created by krislyy on 2018/11/23.
 * 作为图的特殊形式，二叉树的基本组成单元是节点与边；
 * 作为数据结构，其基本的组成实体是二叉树节点，而边则
 * 对应于节点之间的相互引用
 */

#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>* &node)
    {
        if (node == NULL)
            return;
        _InOrder(node->_leftChild);
        cout << node->_data << ' ';
        _InOrder(node->_rightChild);
    }

    void _PreOrder(BinaryTreeNode<T>* &node)
    {
        if (node == NULL)
            return;
        cout << node->_data<<' ';
        _PreOrder(node->_leftChild);
        _PreOrder(node->_rightChild);

    }

    void _PosOrder(BinaryTreeNode<T>* &node)
    {
        if (node == NULL)
            return;
        _PosOrder(node->_leftChild);
        _PosOrder(node->_rightChild);
        cout << node->_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;

    }
};

测试代码

void CheckBinaryTree(){
    int l[j] = { 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();
}

构造后形成的树如下结构

                         1
                        /  \
                      2     7
                     / \   /  \
                   3    6  8   9
                  / \         /
                4    5       10

输出：

pre    : 1 2 3 4 5 6 7 8 9 10
in     :  4 3 5 2 6 1 8 7 10 9
post   : 4 5 3 6 2 8 10 9 7 1
level  : 1 2 7 3 6 8 9 4 5 10