二、二叉树的抽象数据结构定义

1、二叉树节点定义
    二叉树结点抽象数据类型BinaryTreeNode是带有参数T 的模板，T是存储在结点中的数据类型。每个元素结点都有leftchild()和rightchild()左右子结点结构，另外每个结点还包含一个数据域value()。为了强调抽象数据类型与存储无关，我们并没有具体规定该抽象数据类型的存储方式。
    template <class T> class BinaryTreeNode{
    friend class BinaryTree;//申明二叉树为结点类的友元类，便于访问私有数据成员
    private:
        T element;//二叉树结点数据域，实现时，可以补充private的左子结点右子结点定义
    public:
        BinaryTreeNode(); //缺省构造函数
        BinaryTreeNode(const T& ele);//拷贝构造函数
        //给定了结点值和左右子树的构造函数
        BinaryTreeNode(const T& ele,BinaryTreeNode<T>* l,BinaryTreeNode<T>* r);
        T value() const;//返回当前结点的数据
        BinaryTreeNode<T>* leftchild() const;//返回当前结点指向左子树
        BinaryTreeNode<T>* rightchild() const;//返回当前结点指向右子树
        void setLeftchild(BinaryTreeNode<T>*) ;//设置当前结点的左子树
        void setRightchild(BinaryTreeNode<T>*) ;//设置当前结点的右子树
        void setValue(const T& val);//设置当前结点的数据域
        bool isLeaf() const;//判定当前结点是否为叶结点,若是返回true
        BinaryTreeNode<T>& operator= (const BinaryTreeNode<T>& Node);//重载赋值操作符
    };

    2、二叉树结构定义
    二叉树的抽象数据类型的C++定义BinaryTree，没有具体规定该抽象数据类型的存储方式。
    template <class T> class BinaryTree {
    private:
        BinaryTreeNode<T>* root;//二叉树根结点指针
        //从二叉树的root结点开始查找current结点的父结点
        BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>* root,BinaryTreeNode<T>* current);
    public:
        BinaryTree(root=NULL); //构造函数
        ~BinaryTree() {DeleteBinaryTree(root);};//析构函数
        bool isEmpty() const; //判定二叉树是否为空树
        BinaryTreeNode<T>* Root(){return root;};//返回二叉树根结点
        BinaryTreeNode<T>* Parent(BinaryTreeNode<T>* current);//返回current结点的父结点
        BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T>* current);//返回current结点的左兄弟
        BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T>* current);//返回current结点的右兄弟
        // 以elem作为根结点，leftTree作为树的左子树，rightTree作为树的右子树，构造一棵新的二叉树
        void CreateTree(const T& elem,BinaryTree<T>& leftTree,BinaryTree<T>& rightTree);
        void PreOrder(BinaryTreeNode<T>* root)；//前序周游二叉树或其子树
        void InOrder(BinaryTreeNode<T>* root)；//中序周游二叉树或其子树
        void PostOrder(BinaryTreeNode<T>* root)；//后序周游二叉树或其子树
        void LevelOrder(BinaryTreeNode<T>* root)；//按层次周游二叉树或其子树
        void DeleteBinaryTree(BinaryTreeNode<T>* root);//删除二叉树或其子树
    };