经典二叉树面试题

包括建立销毁二叉树，层序遍历二叉树，求二叉树的叶子节点，求二叉树第 k层的节点个数，求二叉树的高度等

#include <assert.h>
#include <queue>

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

template <class T>
class BinaryTree
{
public:
typedef BinaryTreeNode<T> Node;
//无参构造函数
    BinaryTree()
        :_root(NULL)
    {}

//构造函数
    BinaryTree(const T* a, size_t size, const T& invalid)
    {
        assert(a);
        size_t index = 0;
        _root = CreatTree(a, size, invalid, index);
    }

//拷贝构造
    BinaryTree(const BinaryTree<T>& b)
    {
        _root = _copy(b._root);
    }

//析构函数
    ~BinaryTree()
    {
if (NULL != _root)
        {
            Destroy(_root);
            _root = NULL;
        }
    }

//层序遍历打印
void LevelOrder()
    {
cout << "层序遍历:";
        _levelorder(_root);
cout << endl;
    }

//求叶子节点的个数
    size_t GetLeafSize()
    {
cout << "叶子节点的个数:";
return _GetLeafSize(_root);
    }

//求第K层节点的个数
    size_t GetKLevelSize(size_t k)
    {
cout << "第"<<k<<"层节点：";
return _GetKLevelSize(_root, k);
    }

//求二叉树的高度
    size_t Depth()
    {
cout << "树的深度：";
return _Depth(_root);
    }

protected:
//按照先序遍历递归建树,index传引用
    Node* CreatTree(const T* a, size_t size, const T& invalid, size_t& index)
    {
        assert(a);
        Node* root = NULL;
if (a[index] != invalid && index < size)
        {
            root = new Node(a[index]);
            root->_left = CreatTree(a, size, invalid, ++index);
            root->_right = CreatTree(a, size, invalid, ++index);
        }
return root;
    }

//使用队列，层序遍历打印树的各个节点
void _levelorder(Node* root)
    {
queue<Node* > q;
if (root)
        {
            q.push(root);
        }
while (!q.empty())
        {
            Node* front = q.front();
            q.pop();
cout << front->_data << " ";
if (front->_left)
            {
                q.push(front->_left);
            }
if (front->_right)
            {
                q.push(front->_right);
            }
        }
    }

//拷贝
    Node* _copy(Node* root)
    {
        Node* tmp = NULL;

if (root)
        {
            tmp = new Node(root->_data);
            tmp->_left = _copy(root->_left);
            tmp->_right = _copy(root->_right);
        }
return tmp;
    }

//递归释放空间
void Destroy(Node* root)
    {
//用后续遍历访问方式释放空间
if (root)
        {
            Destroy(root->_left);
            Destroy(root->_right);
delete root;
            root = NULL;
        }
    }

//求叶子节点
    size_t _GetLeafSize(Node* root)
    {
if (root == NULL)
return 0;
if (root->_left == NULL&&root->_right == NULL)
        {
return 1;
        }
else
        {
return _GetLeafSize(root->_left) + _GetLeafSize(root->_right);
        }
    }

//求第k层节点个数
    size_t _GetKLevelSize(Node* root, size_t k)
    {
        assert(k > 0);
        size_t count = 0;
if (NULL == root)
return 0;
if (k == 1)
            count++;
else
        {
            count = _GetKLevelSize(root->_left, k - 1) + _GetKLevelSize(root->_right, k - 1);
        }
return count;
    }

//求树的深度
    size_t _Depth(Node* root)
    {
if (root == NULL)
return 0;
else
        {
return _Depth(root->_left) > _Depth(root->_right) ? (_Depth(root->_left) + 1) : (_Depth(root->_right) + 1);
        }
    }
private:
    Node* _root;
};

void TestBinaryTree()
{
int arr[] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6, '#', '#', '#' };
    size_t size = sizeof(arr) / sizeof(arr[0]);
    BinaryTree<int> bt(arr, size, '#');
    BinaryTree<int> b1(bt);
//bt.~BinaryTree();
    bt.LevelOrder();
cout << bt.Depth() << endl;;
cout << bt.GetLeafSize() << endl;
cout << bt.GetKLevelSize(2) << endl;
}