一、引言 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; } 测试结果： 经分析，此测试结果无误。
|
