二叉树基本概念

一棵二叉树的结点的一个有限集合：该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的，互不相交的二叉树组成。
相关性质：
1.在二叉树的第i(i>=1)层最多有2的i-1次方个结点。
2.深度为k(k>=0)的二叉树最少有k个结点,最多有2的k次方-1个结点。
3.叶结点数等于度为2的非叶结点数加1:N0=N2+1
4.满二叉树:深度为k的满二叉树有2的k次方-1个结点
5.完全二叉树：每个结点都与高度为k的满二叉树中编号1~n的结点一一对应
6.具有n个结点的完全二叉树的深度为log2(n+1)向上取整

抽象数据类型：

#ifndef BINARYTREE_H
#define BINARYTREE_H

template<typename T>
class BinaryTree{
public:
    BinaryTree();
    //item为根,lch,rch为左右子树
    BinaryTree(BinTreeNode<T>* lch,BinTreeNode<T>* rch,T item);
    int Height();
    int Size();//结点个数
    bool IsEmpty();
    BinTreeNode<T> *Parent(BinTreeNode<T>* current);
    BinTreeNode<T> *LeftChild(BinTreeNode<T>* current);
    BinTreeNode<T> *RightChild(BinTreeNode<T>* current);
    bool Insert(T item);
    bool Remove(T item);
    bool Find(const T& item)const;
    bool getData(const T& item)const;
    BinTreeNode<T>* getRoot()const;
    void preOrder(void(*visit)(BinTreeNode<T>*p));//前序
    void inOrder(void(*visit)(BinTreeNode<T>*p));//中序
    void postOrder(void(*visit)(BinTreeNode<T>*p));//后序
    void levelOrder(void(*visit)(BinTreeNode<T>*p));//层次
};

#endif // BINARYTREE_H