数据结构-二叉树（1）

树的抽象类型为：

template <class T>
class Tree{
//  对象是树，在类界面中的position是树中结点的地址
//  在顺序存储方式上是下标型，但链表存储方式下是指针型。T是树结点中存放数据的类型，要求所有结点的数据类型一致
public:
    Tree();
    ~Tree();
    position Root();            //返回根结点地址
    BuildRoot(const T& value);  //建立树的根结点
    position FirstChild(position p);  //返回p的第一个子女地址或者0
    position NextSibling(position p); //返回p的下一个兄弟地址或者0
    position Parent(position p);      //返回结点p父结点地址，若p为根则返回0
    T getData(position p);
    bool InsertChild(const position p,const T& value);
    bool DeleteChild(position p,int i)  //在结点p下删除第i个结点和其子孙结点
    void DeleteSubTree(position t);   //删除以t为根结点的子树
    bool IsEmpty();
    void Traversal(void(*visit)(position p)); //遍历，visit是用户自编的访问结点p数据的函数
}

二叉树的抽象类型为

template <class T>
class BinaryTree{
public:
    BinaryTree()
    BinaryTree(BinTreeNode<T> *lch, BinTreeNode<T> *rch, T item);   //构造函数，以item为根，lch、rch为左右结点构造子树
    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 perOrder(void (*visit)(BinTreeNode<T> *p));    //前序遍历，visit是访问函数
    void inOrder(void (*visit)BinTreeNode<T> *p);      //中序遍历
    void postOrder(void (*visit)(BinTreeNode<T> *p));  //后序遍历
    void levelOrder(void (*visit)BinTreeNode<T> *p);   //层次序遍历
}