二叉树实验报告

题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。算法描述：首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述：1、 isLeaf函数：若该结点的左子树和右子树都为空，则为叶子结点。2、 isEmpty函数：根结点为空则为空树。3、 Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。4、 LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。5、 DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后递归删除左子树，递归删除右子树，最后删除根结点。6、 PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。8、CreateTree函数：采用先序遍历序列构造二叉树，设0为空结点，输入非0数，生成新结点，递归创建左子树和右子树。9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在结点的指针。如果当前结点为空，则返回；否则判断当前结点是否为目标结点，如果是，记住结点位置，返回；否则，递归地在左子树中查找，如果找到，记住结点位置，返回；否则，递归地在右子树中查找。判断temp是否为空，若为空，则未查找到给定元素。10、LevelOrder函数：利用队列记录二叉树每一层，首先申请队列，申请指针pointer保存根结点，然后判断pointer是否为空，若不为空，则pointer入队。如果队列为空，跳出函数。队列首元素出队，赋给pointer，访问pointer所指结点，如果pointer所指结点的左子树不为空，则左子树根结点指针入队；如果pointer所指结点的右子树不为空，则右子树根结点指针入队，结束。先序遍历，后序遍历思想与中序遍历一致，这里不再一一分析。最后创建一颗二叉树，用以检验各函数的功能。源程序：#include#include#include#include using namespace std;template class BinaryTree;template class BinaryTreeNodefriend class BinaryTree;/friend class BinarySearchTree;private:T data;/二叉树结点数据域 BinaryTreeNode * left; /二叉树结点指向左子树的指针 BinaryTreeNode * right;/二叉树结点指向右子树的指针 public: BinaryTreeNode();/默认构造函数 BinaryTreeNode(const T& ele) :left(NULL), right(NULL) data = ele;/给定数据的构造函数 BinaryTreeNode(const T& ele,BinaryTreeNode * l,BinaryTreeNode * r);/给定数据的左右指针的构造函数 BinaryTreeNode();/析构函数 T value() constreturn data;/返回当前结点的数据 BinaryTreeNode&operator=(const BinaryTreeNode&Node)this=Node;/重载赋值操作符 BinaryTreeNode * leftchild() constreturn left;/返回当前结点指向左子树的指针 BinaryTreeNode * rightchild() constreturn right;/返回当前结点指向右子树的指针 void setLeftchild(BinaryTreeNode * l)left = l;/设置当前结点的左子树 void setRightchild(BinaryTreeNode * r)right = r;/设置当前结点的右子树 void setValue(const T& val)data = val;/设置当前结点的数据域 bool isLeaf() const; /判定当前结点是否为叶子结点，若是则返回true ;template BinaryTreeNode:BinaryTreeNode(const T& ele,BinaryTreeNode * l,BinaryTreeNode * r)/给定数据的左右指针的构造函数data = ele;left = l;right = r;template bool BinaryTreeNode:isLeaf() const/判定当前结点是否为叶子结点，若是则返回trueif(data-left = NULL & data-right = NULL)/若左子树和右子树都为空，则返回true return true;else return false;template class BinaryTreeprotected:BinaryTreeNode * ROOT;/二叉树根结点指针 public:BinaryTree()ROOT=NULL;/构造函数 BinaryTree(BinaryTreeNode * r)ROOT = r;BinaryTree()DeleteBinaryTree(ROOT);/析构函数 bool isEmpty() const;/判断二叉树是否为空树 void visit(const T& data)cout data ;/访问当前结点 BinaryTreeNode * & Root()return ROOT;/返回二叉树的根结点 BinaryTreeNode * Parent(BinaryTreeNode * current);/返回当前结点的双亲结点void Parent_PreOrder(BinaryTreeNode *curroot,BinaryTreeNode *r,BinaryTreeNode *&t);/运用先序遍历的思想查找双亲BinaryTreeNode * LeftSibling(BinaryTreeNode * current);/返回当前结点的左兄弟 BinaryTreeNode * RightSibling(BinaryTreeNode * current);/返回当前结点的右兄弟 void CreateTree(BinaryTreeNode * &r);/根据先序遍历序列构造二叉树 void DeleteBinaryTree(BinaryTreeNode * root);/删除二叉树或其子树 void PreOrder(BinaryTreeNode * root);/先序遍历二叉树或其子树 void InOrder(BinaryTreeNode * root);/中序遍历二叉树或其子树 void PostOrder(BinaryTreeNode * root);/后序遍历二叉树或其子树 void PreOrderWithoutRecusion(BinaryTreeNode * root);/非递归先序遍历二叉树或其子树 void InOrderWithoutRecusion(BinaryTreeNode * root);/非递归中序遍历二叉树或其子树 void PostOrderWithoutRecusion(BinaryTreeNode * root);/非递归后序遍历二叉树或其子树 void LevelOrder(BinaryTreeNode * root);/按层序遍历二叉树或其子树 BinaryTreeNode * Search( T &t, BinaryTreeNode *r );/二叉树搜索 void Search_PreOrder( T &t, BinaryTreeNode *r, BinaryTreeNode *&temp );/运用先序遍历的思想查找给定数据所在结点;template bool BinaryTree:isEmpty() const/判断二叉树是否为空树 if(ROOT = NULL)/若根结点为空，则返回true return true;else return false;template BinaryTreeNode * BinaryTree:Parent( BinaryTreeNode *current ) /返回当前结点的双亲结点 if( !current | !ROOT | current = ROOT )/若当前结点不存在或根结点为空或当前结点为根结点 ，则输出error且跳出函数 cout Errorn;exit(0);BinaryTreeNode *temp = NULL;/初始化临时指针，temp用于保存最后查找到的双亲结点的地址 Parent_PreOrder( ROOT, current, temp );/查找双亲的子程序 if(!temp)/结点不在树中，则双亲不存在 cout Your node doesnt belong to this tree!n;exit(0);return temp;template void BinaryTree:Parent_PreOrder( BinaryTreeNode *curroot,BinaryTreeNode *r, BinaryTreeNode *&t )/运用递归实现先序遍历，在遍历过程中判断是否找到双亲节点 if( !curroot | curroot-isLeaf() ) return;/当前结点为空或叶子结点 if( r = curroot-left | r = curroot-right )/判断双亲结点的条件 t = curroot;/t是对temp的引用，在此修改temp的值 return;elseParent_PreOrder( curroot-left, r, t );/在左子树中查找 if( t ) return; /如果已在左子树中找到，便不必在右子树中查找 Parent_PreOrder( curroot-right, r, t );/ 在右子树中查找 template BinaryTreeNode * BinaryTree:LeftSibling( BinaryTreeNode *current )/返回当前结点的左兄弟 BinaryTreeNode *temp = Parent(current);/先找到给定结点的双亲 if( !temp-left | current = temp-left )/双亲的左孩子若不是结点本身，则是结点的左兄弟cout left;template BinaryTreeNode * BinaryTree:RightSibling( BinaryTreeNode *current )/返回当前结点的右兄弟 BinaryTreeNode *temp = Parent(current);/先找到给定结点的双亲if( !temp-right | current = temp-right )/双亲的右孩子若不是结点本身，则是结点的右兄弟cout right;template void BinaryTree:DeleteBinaryTree(BinaryTreeNode * root)/删除二叉树或其子树 if(root = NULL) return;/判断是否为空树，若为空，则返回 DeleteBinaryTree( root-left );/递归删除左子树 DeleteBinaryTree( root-right );/递归删除右子树 delete root;/删除根结点 cout One node deleted!n;root = NULL;/根结点置为空 template void BinaryTree:PreOrder(BinaryTreeNode * root)/先序遍历二叉树或其子树 if(root = NULL)/判断是否为空树，若为空，则返回 return;visit(root-value();/访问根结点 PreOrder(root-leftchild();/先序遍历左子树 PreOrder(root-rightchild();/先序遍历右子树 template void BinaryTree:PreOrderWithoutRecusion(BinaryTreeNode * root)/非递归先序遍历二叉树或其子树 stack BinaryTreeNode * tStack;BinaryTreeNode * pointer = root;/保存输入参数 while(!tStack.empty()|pointer)if(pointer)visit(pointer-value();/访问当前结点 tStack.push(pointer);/当前结点地址入栈 pointer = pointer-leftchild();/当前链接结构指向左孩子 else/左子树访问完毕，转向访问右子树 pointer = tStack.top();/当前链接结构指向栈顶的元素 tStack.pop();/栈顶元素出栈 pointer = pointer-rightchild();/指向右孩子 template void BinaryTree:InOrder(BinaryTreeNode * root)/中序遍历二叉树或其子树 if(root = NULL)/判断是否为空树，若为空，则返回 return;InOrder(root-leftchild();/中序遍历左子树visit(root-value();/访问根结点 InOrder(root-rightchild();/中序遍历右子树template void BinaryTree:InOrderWithoutRecusion(BinaryTreeNode * root)/非递归中序遍历二叉树或其子树stack BinaryTreeNode * tStack;BinaryTreeNode * pointer = root;while(!tStack.empty()|pointer)if(pointer)tStack.push(pointer);/当前结点地址入栈 pointer = pointer-leftchild(); /当前链接结构指向左孩子 else/左子树访问完毕，转向访问右子树pointer = tStack.top();/当前链接结构指向栈顶的元素visit(pointer-value();/访问当前结点pointer = pointer-rightchild();/指向右孩子tStack.pop();/栈顶元素出栈template void BinaryTree:PostOrder(BinaryTreeNode * root)/后序遍历二叉树或其子树 if(root = NULL)/判断是否为空树，若为空，则返回 return;PostOrder(root-leftchild();/后序遍历左子树 PostOrder(root-rightchild();/后序遍历右子树 visit(root-value();/访问根结点 enum TagL,R;template class StackNodepublic:BinaryTreeNode * pointer;Tag tag;template void BinaryTree:PostOrderWithoutRecusion(BinaryTreeNode * root)/非递归后序遍历二叉树或其子树 stack StackNode tStack;StackNodeNode;BinaryTreeNode * pointer = root;dowhile(pointer != NULL)/将左子树中的结点加Tag=L后压入栈中 Node.pointer = pointer;Node.tag = L;tStack.push(Node);pointer = pointer-leftchild();Node = tStack.top();/栈顶元素出栈 tStack.pop();pointer = Node.pointer;if(Node.tag = R)/如果从右子树回来 visit(pointer-value();/访问当前结点 pointer = NULL;/置pointer为空，以继续弹栈 else/如果从左子树回来 Node.tag = R;/标志域置为R，进入右子树 tStack.push(Node);pointer = pointer-rightchild();while(!tStack.empty()|pointer);template void BinaryTree:CreateTree(BinaryTreeNode * &r) /根据先序遍历序列构造二叉树 int ch;cin ch;if(ch = 0) r = NULL;else/读入非0数 r = new BinaryTreeNode(ch);/生成结点 CreateTree(r-left);/构造左子树 CreateTree(r-right);/构造右子树 template void BinaryTree:LevelOrder(BinaryTreeNode * root)/按层序遍历二叉树或其子树queue BinaryTreeNode * tQueue;BinaryTreeNode * pointer = root;if(pointer) tQueue.push(pointer);/根结点入队列 while(!tQueue.empty()pointer = tQueue.front();/获得队列首结点 tQueue.pop();/当前结点出队列 visit(pointer-value();/访问当前结点 if(pointer-leftchild() != NULL) tQueue.push(pointer-leftchild();/左子树入队列 if(pointer-rightchild() != NULL) tQueue.push(pointer-rightchild();/右子树入队列 template BinaryTreeNode * BinaryTree:Search( T &t, BinaryTreeNode *root ) /二叉树搜索 if( isEmpty() )/判断是否为空，若为空树，则跳出函数 cout The tree is empty!n;exit(0);BinaryTreeNode *temp = NULL;/初始化临时指针，temp用于保存最后查找到的结点地址Search_PreOrder( t, root, temp );if( !temp ) /未查找到对应结点，将返回NULLcout t doesnt exist in the tree!n;return temp;template void BinaryTree:Search_PreOrder( T &t, BinaryTreeNode *root, BinaryTreeNode *&temp )/运用先序遍历的思想查找给定数据所在结点if( !root ) return;/判断是否为空树，若为空，则返回 if( t = root-value()/找到指定结点并用temp保存地址 temp = root;return;Search_PreOrder( t, root-left, temp );/递归左子树 if( temp ) return;/如果已在左子树中找到，则返回temp Search_PreOrder( t, root-right, temp ); /递归右子树 int main()BinaryTree m