【数据结构】二叉树的实现（如：默认成员函数、（叶子）节点数、深度、四种遍历）

二叉树：树的每个节点最多有两个子节点。

我们看下它的结构，有二叉链表结构与三叉链表结构，具体结果如我摘自《C++Primer》中的图。

相比之下，三叉链表的优势在于当我们知道父亲节点要找他的子女节点比较方便和便捷，反之当我们知道子女节点找它的父亲节点时也方便。

下面，我实现下二叉链表的结构。

template <class T>
struct BinaryTreeNode
{
    BinaryTreeNode<T>* _left;    //左子树
    BinaryTreeNode<T>* _right;    //右子树
    T _data;
    
    BinaryTreeNode(const T& x)   
        :_left(NULL)
        , _right(NULL)
        , _data(x)
    {}
};

（1）求二叉树的叶子节点数leafsize:

叶子节点指的是，节点无子女节点。我们有两种思路：

1）设置一下全局变量或者静态变量的size，遍历二叉树，每次遇到一个节点就加加一次size

2)总叶子节点数就等于左子树叶子节点个数+右子树叶子节点个数

//思路1：
size_t _LeafSize(Node* root)
    {
        static int size = 0;
        if (root == NULL)
        { 
            return size;
        }
        if (root->_left == NULL && root->_right == NULL)
        {
            size++;
            return size;
        }    
        _LeafSize(root->_left);
        _LeafSize(root->_right);
    }

//思路2：
size_t _LeafSize(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        if (root->_left == NULL &&root->_right == NULL)
        {
            return 1;
        }
        return _LeafSize(root->_left) + _LeafSize(root->_right);
    }

（2）求二叉树的深度depth:

深度也称作为高度，就是左子树和右子树深度的较大值。

size_t _Depth(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        int LeftDepth = _Depth(root->_left);
        int RightDepth = _Depth(root->_right);
        return LeftDepth > RightDepth ? LeftDepth +1: RightDepth+1;
    }

（3）求二叉树的节点个数size:

总节点数就等于左子树节点个数+右子树节点个数+根节点个数1

size_t _Size(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

（4）求第k层节点数：

默认根节点为第一层1。

思路与求叶子节点类似。

size_t _kLevelSize(Node* root, int k)//默认根节点为第1层
{
    assert(k > 0);
    if (root == NULL)
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    //不可以传参数k--,不然只能是执行完这一句代码后k才会发生变化，k一直为3
    //不可以传参数--k,执行root->_left时，k变为2，执行root->_right时为同一层k变为1
    //传参数k-1
    return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);
}

（5）遍历二叉树：

注意：前中后序遍历要不要漏掉递归出口。

1）前序遍历：访问根节点->左子树->右子树

void _PrevOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        cout << root->_data << "  ";
        _PrevOrder(root->_left);
        _PrevOrder(root->_right);
    }

2）中序遍历：访问左子树->根节点->右子树

void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_data << "  ";
        _InOrder(root->_right);
    }

3）后序遍历：访问左子树->右子树->根节点

void _PostOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _PostOrder(root->_left);
        _PostOrder(root->_right);
        cout << root->_data << "  ";
    }

4）层次遍历：

即一层一层地遍历结束，再遍历下一层节点，如int a1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }（注意：#表示空。）则层次遍历就应为：1，2，5，3，4，6。

我们用队列解决该问题：首先先给队列无条件入队根节点，下面在出队根节点之前先入队它的子女节点2、5。此时，出队1后队头元素为2，在出队它之前入队它的根节点3，4……

void _LevelOrder(Node* root)
    {
        queue<Node*> q;
        if (root == NULL)
        {
            return;
        }
        q.push(root);
        while (!q.empty())
        {
            if (q.front()->_left != NULL)
            {
                q.push(q.front()->_left);

            }
            if (q.front()->_right != NULL)
            {
                q.push(q.front()->_right);

            }
            cout << q.front()->_data<< "  ";
            q.pop();
        }        
    }

我给出完整程序代码（测试用例我就不要在此处多加阐述了，你们可以自己实现）。

#define _CRT_SECURE_NO_WARNINGS 1
#ifndef __TREE_H__    //防止多次包含
#define __TREE_H__

#include<iostream>
using namespace std;
#include<assert.h>
#include<queue>
#include<stack>

template <class T>
struct BinaryTreeNode
{
    BinaryTreeNode<T>* _left;    //左子树
    BinaryTreeNode<T>* _right;    //右子树
    T _data;
    BinaryTreeNode(const T& x)
        :_left(NULL)
        , _right(NULL)
        , _data(x)
    {}
};

template<class T>
class BinaryTree
{
    typedef BinaryTreeNode<T> Node;    //重命名在于想简化代码，避免过长。
public:
    BinaryTree()
        :_root(NULL)
    {}

    BinaryTree(const T* a, size_t size, const T& invalid)
        :_root(NULL)
    {
        size_t index = 0;
        _root = _CreateTree(a, size, invalid, index);
    }
    
    BinaryTree<T>(const BinaryTree<T>& t)
        : _root(NULL)
    {
        _root = _Copy(t._root);
    }

    BinaryTree<T>& operator=(const BinaryTree<T>& t)
    {
        if (&t != this)
        {
            _Copy(t._root);
            _Destroy(_root);
        }
        return *this;
    }

    ~BinaryTree()
    {
        if (_root)
        {
            _Destroy(_root);
        }
    }

    //前序遍历
    void PreOrder()
    {
        _PrevOrder(_root);
        cout << endl;
    }
    
    //前序遍历非递归写法
    void PreOrderNon_R()
    {
        _PreOrderNon_R(_root);
        cout << endl;
    }

    //中序遍历
    void InOrder()
    {
        _InOrder(_root);
        cout << endl;
    }

    //中序遍历非递归写法
    void InOrderNon_R()
    {
        _InOrderNon_R(_root);
        cout << endl;
    }
    
    //后序遍历
    void PostOrder()
    {
        _PostOrder(_root);
        cout << endl;
    }
    
    //后序遍历非递归写法
    void PostOrderNon_R()
    {
        _PostOrderNon_R(_root);
        cout << endl;
    }
    
    //层次遍历
    void LevelOrder()
    {
        _LevelOrder(_root);
        cout << endl;
    }


    //节点数
    size_t Size()
    {
        return _Size(_root);
    }

    //深度（高度）
    size_t Depth()
    {
        return _Depth(_root);
    }

    //叶子节点数
    size_t LeafSize()
    {
        return _LeafSize(_root);
    }

    //第k层节点
    size_t kLevelSize(int k)
    {
        return _kLevelSize(_root, k);
    }
    
protected:
    void _Destroy(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        if (root->_left == NULL && root->_right == NULL)
        {
            delete root;
            root = NULL;
            return;
        }
        _Destroy(root->_left);
        _Destroy(root->_right);
    }

    Node* _Copy(Node* troot)
    {
        if (troot == NULL)
        {
            return NULL;
        }

        Node* root = new Node(troot->_data);

        root->_left = _Copy(troot->_left);
        root->_right = _Copy(troot->_right);
        return root;
    }

    //方法1：
    /*size_t _LeafSize(Node* root)
    {
        static int size = 0;
        if (root == NULL)
        { 
            return size;
        }
        if (root->_left == NULL && root->_right == NULL)
        {
            size++;
            return size;
        }    
        _LeafSize(root->_left);
        _LeafSize(root->_right);
    }*/

    //方法2：
    size_t _LeafSize(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        if (root->_left == NULL &&root->_right == NULL)
        {
            return 1;
        }
        return _LeafSize(root->_left) + _LeafSize(root->_right);
    }

    size_t _Size(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        return _Size(root->_left) + _Size(root->_right) + 1;
    }

    size_t _Depth(Node* root)
    {
        if (root == NULL)
        {
            return 0;
        }
        int LeftDepth = _Depth(root->_left);
        int RightDepth = _Depth(root->_right);
        return LeftDepth > RightDepth ? LeftDepth +1: RightDepth+1;
    }

    size_t _kLevelSize(Node* root,int k)//默认根节点为第1层
    {
        assert(k > 0);
        if (root == NULL)
        {
            return 0;
        }
        if (k == 1)
        {
            return 1;
        }
        //不可以传参数k--,不然只能是执行完这一句代码后k才会发生变化，k一直为3
        //不可以传参数--k,执行root->_left时，k变为2，执行root->_right时为同一层k变为1
        //传参数k-1
        return _kLevelSize(root->_left, k-1) + _kLevelSize(root->_right, k-1);
    }

    Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
    {
        Node* root = NULL;
        if (index < size && a[index] != invalid)
        {
            root = new Node(a[index]);
            root->_left = _CreateTree(a, size, invalid, ++index);
            root->_right = _CreateTree(a, size, invalid, ++index);
        }
        return root;
    }


    //前序遍历：访问根节点->左子树->右子树
    void _PrevOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        cout << root->_data << "  ";
        _PrevOrder(root->_left);
        _PrevOrder(root->_right);
    }

    //前序遍历的非递归
    void _PrevOrderNon_R(Node* root)
    {
        stack<Node*> s;
        if (root == NULL)
        {
            return;
        }

        s.push(root);
        while (!s.empty())
        {
            root = s.top();
            cout << root->_data << "  ";
            s.pop();
            if (root->_right)
            {
                s.push(root->_right);
            }
            if (root->_left)
            {
                s.push(root->_left);
            }
        }
    }

    //中序遍历：访问左子树->根节点->右子树
    void _InOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _InOrder(root->_left);
        cout << root->_data << "  ";
        _InOrder(root->_right);
    }

    //中序遍历的非递归
    void _InOrderNon_R(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        stack<Node*> s;
        Node* cur = root;
        Node* tmp = root;
        while (cur || !s.empty())
        {
            while (cur)
            {
                tmp = cur;
                s.push(cur);                
                cur = cur->_left;
            }

            cur = s.top();//将栈顶元素保存，以便于后面判断它是否有右孩子
            cout << s.top()->_data << "  ";        
            s.pop();

            if (cur->_right == NULL)
            {
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }
    }

    //后序遍历：访问左子树->右子树->根节点
    void _PostOrder(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        _PostOrder(root->_left);
        _PostOrder(root->_right);
        cout << root->_data << "  ";
    }

    //后序遍历非递归
    void _PostOrderNon_R(Node* root)
    {
        if (root == NULL)
        {
            return;
        }
        Node* cur = root;
        Node* prev = NULL;
        stack<Node*> s;
        while (cur || !s.empty())
        {
            while (cur)
            {
                s.push(cur);                
                cur = cur->_left;                
            }
            cur = s.top();
            if (cur->_right == NULL ||cur->_right==prev )
            {
                cout << cur->_data << "  ";
                s.pop();
                prev = cur;
                cur = NULL;
            }
            else
            {
                cur = cur->_right;
            }
        }                
    }

    //层次遍历
    void _LevelOrder(Node* root)
    {
        queue<Node*> q;
        if (root == NULL)
        {
            return;
        }
        q.push(root);
        while (!q.empty())
        {
            if (q.front()->_left != NULL)
            {
                q.push(q.front()->_left);

            }
            if (q.front()->_right != NULL)
            {
                q.push(q.front()->_right);

            }
            cout << q.front()->_data<< "  ";
            q.pop();
        }        
    }
    
protected:
    Node* _root;
};

#endif    //__TREE_H__