二叉树类型设计

一、引言

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;

}

测试结果：

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