二叉樹實現(xiàn)

1.層次遍歷可以用于尋找葉子節(jié)點爵川，尋找路徑策添，尋找樹的最短最大高度的非遞歸實現(xiàn)吗铐。
2.中序遍歷搜索二叉樹后是升序的序列东亦。這個特性可以判斷搜索二叉樹的有效性。
3.使用雙向的遞歸可以遍歷每個分支的每個節(jié)點唬渗。

/*
 * Created by krislyy on 2018/11/23.
 * 作為圖的特殊形式典阵，二叉樹的基本組成單元是節(jié)點與邊奋渔；
 * 作為數(shù)據(jù)結(jié)構(gòu)，其基本的組成實體是二叉樹節(jié)點萄喳，而邊則
 * 對應(yīng)于節(jié)點之間的相互引用
 */

#pragma once

#include<iostream>
#include<queue>
#include<stack>

using namespace std;

template <class T>  //樹的結(jié)構(gòu)體
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()//節(jié)點數(shù)
    {
        int size = 0;
        cout<<_Size(_root,size)<<endl;

    }

    void Hight()//深度  /高度
    {
        cout << _Hight(_root) << endl;
    }

    void Destory()//銷毀
    {
        _Destory(_root);
        _root=NULL;
    }

    void LeafNum()//葉子節(jié)點數(shù)
    {
        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()  //后續(xù)  非遞歸
    {
        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://以下為遞歸的調(diào)用函數(shù)

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

構(gòu)造后形成的樹如下結(jié)構(gòu)

                         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