丁亮的个人博客   Java/Go/Linux/开源

GitHub 上 Star 数最多的 Java 博客 Solo
Golang 黑科技之在线 IDE Wide
黑客与画家的社区 Sym

二叉树类型设计

    二叉树类型设计说明

    一、引言

    1.背景

    二叉树是树形结构的一个重要类型,许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,因此,二叉树显得特别重要。

    2.摘要

    这是一个简单的二叉树类型及在此类型上的一些常用操作。该二叉树采用的是二叉链表的存储结构,C++实现。

    3.工作条件 / 限制

    由于时间仓促,外加人力有限,本二叉树类型的实现难免存在一些不足。可能会存在用户想要的接口没有定义的情况,也可能会存在是一些操作的实现效率低下等等……就此,可能会在以后的时间里进行类型的再设计与优化。

     

    二、总体设计

    .概要设计

    这是一个二叉树的类模板,用户可以根据自己的需要设置二叉树的节点类型,以下分为两部分说明:

    ⑴二叉树节点类型的功能规格说明

    // 根据类型T设置节点的存储数据类型

    template <class T>

    class BinaryTreeNode

    {

        public:// 用户接口说明

           // 缺省的构造器

           BinaryTreeNode(void);

           // 带参数的构造器

           BinaryTreeNode(const T &data,   // 该节点保存的数据

                           BinaryTreeNode *leftChild = NULL, // 左指针域

                           BinaryTreeNode *rightChild = NULL); // 右指针域

           // 返回该节点的数据

           T& GetData(void);

           // 返回该节点的左孩子指针

           BinaryTreeNode<T>* GetLeftChild(void);

           // 返回该节点的右孩子指针

           BinaryTreeNode<T>* GetRightChild(void);

           // 设置该节点的数据

           void SetData(const T &data);

           // 设置该节点的左孩子指针域

           void SetLeftChild(BinaryTreeNode<T> *leftChild);

           // 设置该节点的右孩子指针域

           void SetRightChild(BinaryTreeNode<T> *rightChild);

        private: // 私有方法及数据说明

           T m_data;      // 存储该节点的数据

           BinaryTreeNode<T> *m_leftChild; // 存储该节点的左孩子指针

           BinaryTreeNode<T> *m_rightChild;// 存储该节点的右孩子指针

    };

     

    ⑵整体二叉树类型的功能规格说明

    // 根据类型T设置节点的存储数据类型

    template<class T>

    class BinaryTree

    {

       

        public:// 用户接口说明

           // 缺省的构造器,初始化该树

           BinaryTree(void);

           // 析构器,释放资源给OS

           virtual ~BinaryTree(void);

           // 判断树是否是空树

           bool IsEmpty(void)   const;

           // 判断一个节点是否是左孩子

           bool IsLeftChild(BinaryTreeNode<T> *p);

           // 判断一个节点是否是右孩子

           bool IsRightChild(BinaryTreeNode<T> *p);

           // 取得整棵树的树根

           BinaryTreeNode<T>* GetRoot(void);

           // 取得一个节点的父亲节点指针

           BinaryTreeNode<T>* GetParent(BinaryTreeNode<T> *p);

           // 取得一个节点的左子树根指针

           BinaryTreeNode<T>* LeftChild(BinaryTreeNode<T> *root) const;

           // 取得一个节点的右子树根指针

           BinaryTreeNode<T>* RightChild(BinaryTreeNode<T> *root) const;

           // 取得一个节点的左兄弟指针

           BinaryTreeNode<T>* LeftSibling(BinaryTreeNode<T> *leftChild);

           // 取得一个节点的右兄弟指针

           BinaryTreeNode<T>* RightSibling(BinaryTreeNode<T> *rightChild);

           // 返回一个节点的数据

           T Retrieve(BinaryTreeNode<T> *p)   const;

           // 设置一个节点的数据

           void Assign(BinaryTreeNode<T> *p, const T &d) const;

           // 插入右孩子到当前节点下

           void InsertRightChild(BinaryTreeNode<T> *p, const T &d) const;

           // 插入左孩子到当前节点下

           void InsertLeftChild(BinaryTreeNode<T> *p, const T &d) const;

           // 删除当前节点的右孩子

           void DeleteRightChild(BinaryTreeNode<T> *p);

           // 删除当前节点的左孩子

           void DeleteLeftChild(BinaryTreeNode<T> *p);

           // 先序遍历整棵树

           virtual void PreOrderTraverse(void)    const;

           // 中序遍历整棵树

            virtual void InOrderTraverse(void) const;

           // 后序遍历整棵树

           virtual void PostOrderTraverse(void)   const;

           // 按层遍历整棵树

           virtual void LevelOrderTraverse(void)  const;

        protected:// 保护的数据或方法

           // 用于存储树根

           BinaryTreeNode<T> *m_root;

           // 根据给定数据创建树的根节点

           void CreateRoot(const T &data);

           // 从一个节点开始先序遍历其子树

           virtual void PreOrder(BinaryTreeNode<T> *root)   const;

           // 从一个节点开始中序遍历其子树

           virtual void InOrder(BinaryTreeNode<T> *root) const;

           // 从一个节点开始后序遍历其子树

           virtual void PostOrder(BinaryTreeNode<T> *root)  const;

           // 从一个节点开始按层遍历其子树

           virtual void LevelOrder(BinaryTreeNode<T> *root)const;

           // 取得给定节点的父亲节点指针

           BinaryTreeNode<T>* Parent(BinaryTreeNode<T> *root,                                         BinaryTreeNode<T> *p);

           // 从给定节点开始销毁其子树

           void Destroy(BinaryTreeNode<T> *p);

    };

     

    .详细设计

    ⑴二叉树节点类型具体实现说明

    template<class T> // 以下函数均基于类型T

    //=============================

    // 函数名:BinaryTreeNode

    // 功能:缺省的构造函数,设置该节点的左右孩子指针域均为空

    // 输入参数:void

    // 输出参数:无

    BinaryTreeNode<T>::BinaryTreeNode(void)

    {

        m_leftChild = m_rightChild = NULL;

     

        return;

    }

    //=============================

    // 函数名:BinaryTreeNode

    // 功能:带参数的构造函数,根据参数设置该节点的左右孩子指针域

    // 输入参数:const T &data:用于初始化该节点数据域

    //           BinaryTreeNode *leftChild:用于初始化该节点左孩子指针

    //           BinaryTreeNode *rightChild:用于初始化该节点左孩子指针

    // 输出参数:无

    BinaryTreeNode<T>::BinaryTreeNode(const T &data,

                                  BinaryTreeNode *leftChild,

                                      BinaryTreeNode *rightChild)

    {

        m_data = data;

        m_leftChild = leftChild;

        m_rightChild = rightChild;

     

        return;

    }

    //=============================

    // 函数名:GetData

    // 功能:返回该节点的数据

    // 输入参数:void

    // 输出参数:T&:该节点的数据

    T& BinaryTreeNode<T>::GetData(void)

    {

        return m_data;

    }

    //=============================

    // 函数名:GetLeftChild

    // 功能:返回该节点的左孩子指针

    // 输入参数:void

    // 输出参数:BinaryTreeNode<T>*:该节点的左孩子指针

    BinaryTreeNode<T>* BinaryTreeNode<T>::GetLeftChild(void)

    {

        return m_leftChild;

    }

    //=============================

    // 函数名:GetRightChild

    // 功能:返回该节点的右孩子指针

    // 输入参数:void

    // 输出参数:BinaryTreeNode<T>*:该节点的右孩子指针

    BinaryTreeNode<T>* BinaryTreeNode<T>::GetRightChild(void)

    {

        return m_rightChild;

    }

    //=============================

    // 函数名:SetData

    // 功能:设置该节点的数据域

    // 输入参数:const T &data:根据此参数设置数据域

    // 输出参数:void

    void BinaryTreeNode<T>::SetData(const T &data)

    {

        m_data = data;

           

        return;

    }

    //=============================

    // 函数名:SetLeftChild

    // 功能:设置该节点的左孩子指针域

    // 输入参数:BinaryTreeNode<T> *leftChild:根据此参数设置左孩子指针域

    // 输出参数:void

    void BinaryTreeNode<T>::SetLeftChild(BinaryTreeNode<T> *leftChild)

    {

        m_leftChild = leftChild;

           

        return;

    }

    //=============================

    // 函数名:SetRightChild

    // 功能:设置该节点的右孩子指针域

    // 输入参数:BinaryTreeNode<T> *RightChild:根据此参数设置右孩子指针域

    // 输出参数:void

    void BinaryTreeNode<T>::SetRightChild(BinaryTreeNode<T> *rightChild)

    {

        m_rightChild = rightChild;

           

        return;

    }

    ⑵整体二叉树类型具体实现说明

    template<class T> // 以下函数均基于类型T

    //=============================

    // 函数名:BinaryTree

    // 功能:构造器,初始化整棵树为空树

    // 输入参数:void

    // 输出参数:无

    BinaryTree<T>::BinaryTree(void)

    {

        m_root = NULL;

     

        return;

    }

    //=============================

    // 函数名:~BinaryTree

    // 功能:析构器,基于函数Destory销毁整棵树,释放资源给OS

    // 输入参数:void

    // 输出参数:无

    BinaryTree<T>::~BinaryTree(void)

    {

        Destroy(m_root);

        m_root = NULL;

     

        return;

    }

    //=============================

    // 函数名:IsEmpty

    // 功能:判断这棵树是否是空树

    // 输入参数:void

    // 输出参数:bool:如果是则返回true,反之返回false

    bool BinaryTree<T>::IsEmpty(void)       const

    {

        return m_root == NULL ? true:false;

    }

    //=============================

    // 函数名:IsLeftChild

    // 功能:判断该节点p是否为左孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 注意:树根不能作为输入参数

    // 输出参数:bool:为真说明是左孩子,反之是右孩子

    bool BinaryTree<T>::IsLeftChild(BinaryTreeNode<T> *p)

    {

        return p == GetParent(p)->GetLeftChild() ? true:false;

    }

    //=============================

    // 函数名:IsRightChild

    // 功能:判断该节点p是否为右左孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 注意:树根不能作为输入参数

    // 输出参数:bool:为真说明是右孩子,反之是左孩子

    bool BinaryTree<T>::IsRightChild(BinaryTreeNode<T> *p)

    {

        return p == GetParent(p)->GetRightChild() ? true:false;

    }

    //=============================

    // 函数名:Destroy

    // 功能:销毁给定树,释放资源

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::Destroy(BinaryTreeNode<T> *p)\

    {

        if (NULL != p)

        {

            Destroy(p->GetLeftChild());

            Destroy(p->GetRightChild());

            delete p;

        }

     

        return;

    }

    //=============================

    // 函数名:GetRoot

    // 功能:取得整棵树的根节点指针

    // 输入参数:void

    // 输出参数:BinaryTreeNode<T>*:整棵树的树根指针

    BinaryTreeNode<T>* BinaryTree<T>::GetRoot(void)

    {

        return m_root;

    }

    //=============================

    // 函数名:GetParent

    // 功能:基于函数Parent取得给定节点的父亲指针

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:指向该节点父亲的指针

    BinaryTreeNode<T>* BinaryTree<T>::GetParent(BinaryTreeNode<T> *p)

    {

        return Parent(m_root, p);

    }

    //=============================

    // 函数名:Parent

    // 功能:取得给定节点的父亲指针

    // 输入参数:BinaryTreeNode<T> *root:从root指向的节点开始寻找

    BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:指向该节点父亲的指针

    BinaryTreeNode<T>* BinaryTree<T>::Parent(BinaryTreeNode<T> *root,

                                             BinaryTreeNode<T> *p)

    {

        BinaryTreeNode<T> *q;

     

        if (NULL == root)

        {

           return NULL;

        }

        if ((p == root->GetLeftChild()) || (p == root->GetRightChild()))

        {

           return root;

        }

        if (NULL != (q = Parent(root->GetLeftChild(), p)))

        {

           return q;

         }

         else

         {

           return Parent(root->GetRightChild(), p);

         }

    }

    //=============================

    // 函数名:RightSibling

    // 功能:基于Parent函数取得给定节点的右兄弟的指针

    // 注意:如果该节点就是右孩子,那么函数将返回空值

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:指向该节点右兄弟的指针或空值

    BinaryTreeNode<T>* BinaryTree<T>::RightSibling(BinaryTreeNode<T> *p)

    {

        BinaryTreeNode<T> *q;

     

        q = Parent(m_root, p);

        if ((NULL == q) || (p == q->GetRightChild()))

        {

            return NULL;

        }

        else

        {

            return q->GetRightChild();

        }

    }

    //=============================

    // 函数名:LeftSibling

    // 功能:基于Parent函数取得给定节点的左兄弟的指针

    // 注意:如果该节点就是左孩子,那么函数将返回空值

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:指向该节点左兄弟的指针或空值

    BinaryTreeNode<T>* BinaryTree<T>::LeftSibling(BinaryTreeNode<T> *p)

    {

        BinaryTreeNode<T> *q;

     

        q = Parent(m_root, p);

        if ((NULL == q) || (p == q->GetLeftChild()))

        {

            return NULL;

        }

        else

        {

            return q->GetLeftChild();

        }

    }

    //=============================

    // 函数名:InOrder

    // 功能:从给定节点开始先序遍历其子树

    // 注意:使用的时候请根据数据类型T适当修改输出方式

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::InOrder(BinaryTreeNode<T> *root)    const

    {

        if (NULL != root)

        {

            InOrder(root->GetLeftChild());

            //cout << root->GetData();      // NOTE!

            InOrder(root->GetRightChild());

        }

     

        return;

    }

    //=============================

    // 函数名:PostOrder

    // 功能:从给定节点开始后序遍历其子树

    // 注意:使用的时候请根据数据类型T适当修改输出方式

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::PostOrder(BinaryTreeNode<T> *root)  const

    {

        if (NULL != root)

        {

            PostOrder(root->GetLeftChild());

            PostOrder(root->GetRightChild());

            //cout << root->GetData();      // NOTE!

        }

     

        return;

    }

    //=============================

    // 函数名:PreOrder

    // 功能:从给定节点开始先序遍历其子树

    // 注意:使用的时候请根据数据类型T适当修改输出方式

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::PreOrder(BinaryTreeNode<T> *root)   const

    {

        if (NULL != root)

        {

            //cout << root->GetData();      // NOTE!

            PreOrder(root->GetLeftChild());

            PreOrder(root->GetRightChild());

         }

     

        return;

    }

    //=============================

    // 函数名:LevelOrder

    // 功能:从给定节点开始按层遍历其子树(需要一个队列的支持)

    // 注意:使用的时候请根据数据类型T适当修改输出方式

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::LevelOrder(BinaryTreeNode<T> *root) const

    {

        queue<BinaryTreeNode<T> *> q;

     

        if (NULL != root)

        {

            q.push(root);

        }

     

        while (!q.empty())

        {

           root = q.front(), q.pop();

            //cout << p->GetData();         // NOTE!

            if (root->GetLeftChild())

            {

              q.push(root->GetLeftChild());

            }

           if (root->GetRightChild())

           {

               q.push(root->GetRightChild());

            }

        }

     

        return;

    }

    //=============================

    // 函数名:LevelOrderTraverse

    // 功能:基于函数LevelOrder按层遍历遍历整棵二叉树

    // 输入参数:void

    // 输出参数:void

    void BinaryTree<T>::LevelOrderTraverse(void)    const

    {

        LevelOrder(m_root);

     

        return;

    }

    //=============================

    // 函数名:PostOrderTraverse

    // 功能:基于函数PostOrder后序遍历遍历整棵二叉树

    // 输入参数:void

    // 输出参数:void

    void BinaryTree<T>::PostOrderTraverse(void)     const

    {

       PostOrder(m_root);

     

       return;

    }

     

    //=============================

    // 函数名:InOrderTraverse

    // 功能:基于函数InOrder中序遍历遍历整棵二叉树

    // 输入参数:void

    // 输出参数:void

    void BinaryTree<T>::InOrderTraverse(void)       const

    {

        InOrder(m_root);

     

        return;

    }

    //=============================

    // 函数名:PreOrderTraverse

    // 功能:基于函数PreOrder中序遍历遍历整棵二叉树

    // 输入参数:void

    // 输出参数:void

    void BinaryTree<T>::PreOrderTraverse(void)       const

    {

        PreOrder(m_root);

     

        return;

    }

    //=============================

    // 函数名:DeleteLeftChild

    // 功能:基于函数Destroy删除给定节点的左孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::DeleteLeftChild(BinaryTreeNode<T> *p)

    {

        Destroy(p->GetLeftChild());

     

        return;

    }

    //=============================

    // 函数名:DeleteRightChild

    // 功能:基于函数Destroy删除给定节点的右孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:void

    void BinaryTree<T>::DeleteRightChild(BinaryTreeNode<T> *p)

    {

        Destroy(p->GetRightChild());

     

        return;

    }

    //=============================

    // 函数名:InsertLeftChild

    // 功能:基于二叉树节点类型里的函数SetLeftChild设置给定节点的左孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    //        const T &d:设置到左孩子的数据

    // 输出参数:void

    void BinaryTree<T>::InsertLeftChild(BinaryTreeNode<T> *p, const T &d) const

    {

        BinaryTreeNode<T> *q = new BinaryTreeNode<T>(d);

     

        q->SetLeftChild(p->GetLeftChild());

        p->SetLeftChild(q);

     

        return;

    }

    //=============================

    // 函数名:InsertRightChild

    // 功能:基于二叉树节点类型里的函数SetRightLeftChild设置给定节

    //       点的右孩子

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    //        const T &d:设置到右孩子的数据

    // 输出参数:void

    void BinaryTree<T>::InsertRightChild(BinaryTreeNode<T> *p, const T &d) const

    {

        BinaryTreeNode<T> *q = new BinaryTreeNode<T>(d);

     

        q->SetRightChild(p->GetRightChild());

        p->SetRightChild(q);

     

        return;

    }

    //=============================

    // 函数名:Assign

    // 功能:基于二叉树节点类型里的函数SetData设置给定节点的数据

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    //        const T &d:设置到该节点的数据

    // 输出参数:void

    void BinaryTree<T>::Assign(BinaryTreeNode<T> *p, const T &d) const

    {

        p->SetData(d);

     

        return;

    }

     

    //=============================

    // 函数名:Retrieve

    // 功能:基于二叉树节点类型里的函数GetData返回给定节点的数据

    // 输入参数:BinaryTreeNode<T> *p:给定p指向树中的一个节点

    // 输出参数:T:返回的数据

    T BinaryTree<T>::Retrieve(BinaryTreeNode<T> *p) const

    {

        return p->GetData();

    }

    //=============================

    // 函数名:RightChild

    // 功能:基于二叉树节点类型里的函数GetRightChild返回给定节点的

    //     右子树根指针

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:给定节点的右子树根指针或是空值

    BinaryTreeNode<T>* BinaryTree<T>::RightChild(BinaryTreeNode<T> *root) const

    {

        return root == NULL ? NULL:root->GetRightChild();

    }

    //=============================

    // 函数名:LeftChild

    // 功能:基于二叉树节点类型里的函数GetLeftChild返回给定节点的

    //     左子树根指针

    // 输入参数:BinaryTreeNode<T> *root:给定root指向树中的一个节点

    // 输出参数:BinaryTreeNode<T>*:给定节点的左子树根指针或是空值

    BinaryTreeNode<T>* BinaryTree<T>::LeftChild(BinaryTreeNode<T> *root) const

    {

        return root == NULL ? NULL:root->GetLeftChild();

    }

    //=============================

    // 函数名:CreateRoot

    // 功能:根据输入数据建立整棵树的根节点

    // 输入参数:const T &data:给定的数据

    // 输出参数:void

    void BinaryTree<T>::CreateRoot(const T &data)

    {

        m_root = new BinaryTreeNode<T>(data);

     

        return;

    }

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    各子程序间的调用关系图

     

     

    三、典型测试案例

    案例1

    #include "BinaryTreeNode.h"

    #include "BinaryTree.h"

     

    int main(int argc, char* argv[])

    {

            BinaryTree<int> myBinTree;

     

            myBinTree.CreateRoot(0);

     

            for (int i = 1; i < 9; i += 2)

            {

                    myBinTree.InsertLeftChild(myBinTree.GetRoot(), i);

                    myBinTree.InsertRightChild(

    myBinTree.GetRoot(), i + 1);

            }

     

            cout << "Is Empty? : " << myBinTree.IsEmpty() << endl;

     

    cout << "Root data: " <<myBinTree.Retrieve(myBinTree.GetRoot());

            cout << endl << "Assign root with 9!";

            myBinTree.Assign(myBinTree.GetRoot(), 9);

            cout << "Current root dadta: "

                 << myBinTree.Retrieve(myBinTree.GetRoot()) << endl;

     

            cout << "LevelOrder: ";

            myBinTree.LevelOrderTraverse();

     

            cout << "PreOrder: ";

            myBinTree.PreOrderTraverse();

     

            cout << endl << "InOrder: ";

            myBinTree.InOrderTraverse();

     

            cout << endl << "PostOrder: ";

            myBinTree.PostOrderTraverse();

     

            cout << endl;

     

            return 0;

    }

     

    测试结果:

       

    经分析,此测试结果无误。

     

    案例2

    #include "BinaryTreeNode.h"

    #include "BinaryTree.h"

     

    int main(int argc, char* argv[])

    {

            BinaryTree<char> myBinTree;

     

            myBinTree.CreateRoot('a');

     

            for (int i = 1; i < 9; i += 2)

            {

                    myBinTree.InsertLeftChild(myBinTree.GetRoot(), i+65);

                    myBinTree.InsertRightChild(

    myBinTree.GetRoot(), i + 66);

            }

     

            cout << "Is Empty? : " << myBinTree.IsEmpty() << endl;

     

            cout << "Root data: "

    << myBinTree.Retrieve(myBinTree.GetRoot());

            cout << endl << "Assign root with A!";

            myBinTree.Assign(myBinTree.GetRoot(), 'A');

            cout << "Current root dadta: "

                 << myBinTree.Retrieve(myBinTree.GetRoot()) << endl;

     

            cout << "LevelOrder: ";

            myBinTree.LevelOrderTraverse();

     

            cout << "PreOrder: ";

            myBinTree.PreOrderTraverse();

     

            cout << endl << "InOrder: ";

            myBinTree.InOrderTraverse();

     

            cout << endl << "PostOrder: ";

            myBinTree.PostOrderTraverse();

     

            cout << endl;

     

            return 0;

    }

    测试结果:

    经分析,此测试结果无误。

     
    validate