二叉树实验报告二叉树实验报告总结.docx

1、二叉树实验报告二叉树实验报告总结二叉树实验报告二叉树实验报告总结 题目： 编程实现二叉查找树的建立、中序遍历、元素查找等功能，要求解释实现过程及演示实际例子的运行结果。 算法描述： 首先创建二叉树结点类，其主要包括：二叉树结点数据域，指向左、右子树的指针，构造函数，设置当前结点左、右子树、数据域以及判断当前结点是否为叶子结点等。然后进行二叉树类定义，其私有部分为定义二叉树根结点指针，公有部分主要包括：构造函数、析构函数、判断二叉树是否为空树、先，中，后序遍历的递归与非递归、二叉树删除、层序遍历以及二叉树搜索等。接下来将对一些重要函数算法进行描述： isLeaf函数：若该结点的左子树和右子树都为

2、空，则为叶子结点。 isEmpty函数：根结点为空则为空树。 Parent函数：首先判断给定结点是否有双亲，根结点和空结点一定无双亲，初始化一个临时变量，用于跟进查找双亲结点，查找到后其保存的便是双亲结点。先递归在左子树中查找，如果找到，便结束递归且返回双亲结点指针；如果没有找到，再递归在右子树中查找。如果都没有找到，说明给定结点的双亲结点不在该二叉树中。 LeftSibling（RightSibling）函数：首先找到当前结点的双亲，然后判断双亲结点左右子树是否为空，其中必然有一个不为空，返回另一个子树指针即可。 DeleteBinaryTree函数：首先判断是否为空树，若为空，则返回，然后

3、递归删除左子树，递归删除右子树，最后删除根结点。 PreOrder函数：首先判断是否为空树，若为空，则返回，然后访问根结点，递归遍历左子树，递归遍历右子树，结束。 7、PreOrderWithoutRecusion函数：使用栈来模拟递归过程，首先申请栈，用于保存结点指针序列，申请指针pointer保存当前根指针，然后判断栈是否为空，若栈为空且pointer为空，跳出函数，否则若pointer不为空，访问pointer所指结点，pointer入栈，pointer指向其左子树；若pointer为空，弹出栈顶元素赋给pointer，pointer指向其右子树，结束。 8、CreateTree函数：采

4、用先序遍历序列构造二叉树，设0为空结点，输入非0数，生成新结点，递归创建左子树和右子树。 9、Search函数：采用先序遍历查找给定元素是否在二叉树中，首先判断树是否是空树，若是空树，则返回空指针。然后初始化临时指针temp，查找成功后temp即为所给元素所在结点的指针。如果当前结点为空，则返回；否则判断当前结点是否为目标结点，如果是，记住结点位置，返回；否则，递归地在左子树中查找，如果找到，记住结点位置，返回；否则，递归地在右子树中查找。判断temp是否为空，若为空，则未查找到给定元素。 10、LevelOrder函数：利用队列记录二叉树每一层，首先申请队列，申请指针pointer保存根结点

5、，然后判断pointer是否为空，若不为空，则pointer入队。如果队列为空，跳出函数。队列首元素出队，赋给pointer，访问pointer所指结点，如果pointer所指结点的左子树不为空，则左子树根结点指针入队；如果pointer所指结点的右子树不为空，则右子树根结点指针入队，结束。 先序遍历，后序遍历思想与中序遍历一致，这里不再一一分析。最后创建一颗二叉树，用以检验各函数的功能。 源程序： #includeiostream #includestack #includequeue #include cstdlib using namespace std; template class

6、T class BinaryTree; template class T class BinaryTreeNode friend class BinaryTree T /friend class BinarySearchTree T private: T data; /二叉树结点数据域 BinaryTreeNode T * left; /二叉树结点指向左子树的指针 BinaryTreeNode T * right; /二叉树结点指向右子树的指针 public: BinaryTreeNode(); /默认构造函数 BinaryTreeNode(const T ele) :left(NULL),

7、right(NULL) data = ele; /给定数据的构造函数 BinaryTreeNode(const T ele,BinaryTreeNode T * l,BinaryTreeNode T * r); /给定数据的左右指针的构造函数 BinaryTreeNode(); /析构函数 T value() constreturn data; /返回当前结点的数据 BinaryTreeNode T operator=(const BinaryTreeNode T Node)this=Node; /重载赋值操作符 BinaryTreeNode T * leftchild() constretu

8、rn left; /返回当前结点指向左子树的指针 BinaryTreeNode T * rightchild() constreturn right; /返回当前结点指向右子树的指针 void setLeftchild(BinaryTreeNode T * l)left = l; /设置当前结点的左子树 void setRightchild(BinaryTreeNode T * r)right = r; /设置当前结点的右子树 void setValue(const T val)data = val; /设置当前结点的数据域 bool isLeaf() const; /判定当前结点是否为叶子结

9、点，若是则返回true ; template class T BinaryTreeNode T :BinaryTreeNode(const T ele,BinaryTreeNode T * l,BinaryTreeNode T * r) /给定数据的左右指针的构造函数 data = ele; left = l; right = r; template class T bool BinaryTreeNode T :isLeaf() const /判定当前结点是否为叶子结点，若是则返回true if(data-left = NULL data-right = NULL) /若左子树和右子树都为空，

10、则返回true return true; else return false; template class T class BinaryTree protected: BinaryTreeNode T * ROOT; /二叉树根结点指针 public: BinaryTree()ROOT=NULL; /构造函数 BinaryTree(BinaryTreeNode T * r)ROOT = r; BinaryTree()DeleteBinaryTree(ROOT); /析构函数 bool isEmpty() const; /判断二叉树是否为空树 void visit(const T data)c

11、out data “ ; /访问当前结点 BinaryTreeNode T * Root()return ROOT; /返回二叉树的根结点 BinaryTreeNode T * Parent(BinaryTreeNode T * current); /返回当前结点的双亲结点 void Parent_PreOrder(BinaryTreeNode T *curroot,BinaryTreeNode T *r,BinaryTreeNode T * /运用先序遍历的思想查找双亲 BinaryTreeNode T * LeftSibling(BinaryTreeNode T * current); /

12、返回当前结点的左兄弟 BinaryTreeNode T * RightSibling(BinaryTreeNode T * current); /返回当前结点的右兄弟 void CreateTree(BinaryTreeNode T * /根据先序遍历序列构造二叉树 void DeleteBinaryTree(BinaryTreeNode T * root); /删除二叉树或其子树 void PreOrder(BinaryTreeNode T * root); /先序遍历二叉树或其子树 void InOrder(BinaryTreeNode T * root); /中序遍历二叉树或其子树 vo

13、id PostOrder(BinaryTreeNode T * root); /后序遍历二叉树或其子树 void PreOrderWithoutRecusion(BinaryTreeNode T * root); /非递归先序遍历二叉树或其子树 void InOrderWithoutRecusion(BinaryTreeNode T * root); /非递归中序遍历二叉树或其子树 void PostOrderWithoutRecusion(BinaryTreeNode T * root); /非递归后序遍历二叉树或其子树 void LevelOrder(BinaryTreeNode T *

14、root); /按层序遍历二叉树或其子树 BinaryTreeNodeT * Search( T t, BinaryTreeNodeT *r ); /二叉树搜索 void Search_PreOrder( T t, BinaryTreeNodeT *r, BinaryTreeNodeT *temp ); /运用先序遍历的思想查找给定数据所在结点 ; template class T bool BinaryTree T :isEmpty() const /判断二叉树是否为空树 if(ROOT = NULL) /若根结点为空，则返回true return true; else return fal

15、se; template class T BinaryTreeNodeT * BinaryTreeT:Parent( BinaryTreeNodeT *current ) /返回当前结点的双亲结点 if( !current | !ROOT | current = ROOT ) /若当前结点不存在或根结点为空或当前结点为根结点 ，则输出error且跳出函数 cout Errorn; exit(0); BinaryTreeNodeT *temp = NULL; /初始化临时指针，temp用于保存最后查找到的双亲结点的地址 Parent_PreOrder( ROOT, current, temp )

16、; /查找双亲的子程序 if(!temp) /结点不在树中，则双亲不存在 cout Your node doesnt belong to this tree!n; exit(0); return temp; template class T void BinaryTreeT:Parent_PreOrder( BinaryTreeNodeT *curroot,BinaryTreeNodeT *r, BinaryTreeNodeT *t ) /运用递归实现先序遍历，在遍历过程中判断是否找到双亲节点 if( !curroot | curroot-isLeaf() ) return; /当前结点为空或

17、叶子结点 if( r = curroot-left | r = curroot-right ) /判断双亲结点的条件 t = curroot; /t是对temp的引用，在此修改temp的值 return; else Parent_PreOrder( curroot-left, r, t ); /在左子树中查找 if( t ) return; /如果已在左子树中找到，便不必在右子树中查找 Parent_PreOrder( curroot-right, r, t ); / 在右子树中查找 template class T BinaryTreeNodeT * BinaryTreeT:LeftSibl

18、ing( BinaryTreeNodeT *current ) /返回当前结点的左兄弟 BinaryTreeNodeT *temp = Parent(current); /先找到给定结点的双亲 if( !temp-left | current = temp-left ) /双亲的左孩子若不是结点本身，则是结点的左兄弟 cout This node doesnt have a leftsibling!n; exit(0); return temp-left; template class T BinaryTreeNodeT * BinaryTreeT:RightSibling( BinaryTr

19、eeNodeT *current ) /返回当前结点的右兄弟 BinaryTreeNodeT *temp = Parent(current); /先找到给定结点的双亲 if( !temp-right | current = temp-right ) /双亲的右孩子若不是结点本身，则是结点的右兄弟 cout This node doesnt have a rightsibling!n; exit(0); return temp-right; template class T void BinaryTree T :DeleteBinaryTree(BinaryTreeNode T * root)

20、/删除二叉树或其子树 if(root = NULL) return; /判断是否为空树，若为空，则返回 DeleteBinaryTree( root-left ); /递归删除左子树 DeleteBinaryTree( root-right ); /递归删除右子树 delete root; /删除根结点 cout One node deleted!n; root = NULL; /根结点置为空 template class T void BinaryTree T :PreOrder(BinaryTreeNode T * root) /先序遍历二叉树或其子树 if(root = NULL) /判

21、断是否为空树，若为空，则返回 return; visit(root-value(); /访问根结点 PreOrder(root-leftchild(); /先序遍历左子树 PreOrder(root-rightchild(); /先序遍历右子树 template class T void BinaryTree T :PreOrderWithoutRecusion(BinaryTreeNode T * root) /非递归先序遍历二叉树或其子树 stack BinaryTreeNode T * tStack; BinaryTreeNode T * pointer = root; /保存输入参数

22、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 class T void Binary

23、Tree T :InOrder(BinaryTreeNode T * root) /中序遍历二叉树或其子树 if(root = NULL) /判断是否为空树，若为空，则返回 return; InOrder(root-leftchild(); /中序遍历左子树 visit(root-value(); /访问根结点 InOrder(root-rightchild(); /中序遍历右子树 template class T void BinaryTree T :InOrderWithoutRecusion(BinaryTreeNode T * root) /非递归中序遍历二叉树或其子树 stack B

24、inaryTreeNode T * tStack; BinaryTreeNode T * pointer = root; while(!tStack.empty()|pointer) if(pointer) tStack.push(pointer); /当前结点地址入栈 pointer = pointer-leftchild(); /当前链接结构指向左孩子 else /左子树访问完毕，转向访问右子树 pointer = tStack.top(); /当前链接结构指向栈顶的元素 visit(pointer-value(); /访问当前结点 pointer = pointer-rightchild

25、(); /指向右孩子 tStack.pop(); /栈顶元素出栈 template class T void BinaryTree T :PostOrder(BinaryTreeNode T * root) /后序遍历二叉树或其子树 if(root = NULL) /判断是否为空树，若为空，则返回 return; PostOrder(root-leftchild(); /后序遍历左子树 PostOrder(root-rightchild(); /后序遍历右子树 visit(root-value(); /访问根结点 enum TagL,R; template class T class Stac

26、kNode public: BinaryTreeNode T * pointer; Tag tag; ; template class T void BinaryTree T :PostOrderWithoutRecusion(BinaryTreeNode T * root) /非递归后序遍历二叉树或其子树 stack StackNode T tStack; StackNode T Node; BinaryTreeNode T * pointer = root; do while(pointer != NULL) /将左子树中的结点加Tag=L后压入栈中 Node.pointer = poin

27、ter; 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 =

28、pointer-rightchild(); while(!tStack.empty()|pointer); template class T void BinaryTree T :CreateTree(BinaryTreeNode T * r) /根据先序遍历序列构造二叉树 int ch; cin ch; if(ch = 0) r = NULL; else /读入非0数 r = new BinaryTreeNode T (ch); /生成结点 CreateTree(r-left); /构造左子树 CreateTree(r-right); /构造右子树 template class T void

29、 BinaryTree T :LevelOrder(BinaryTreeNode T * root) /按层序遍历二叉树或其子树 queue BinaryTreeNode T * tQueue; BinaryTreeNode T * 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 class T BinaryTreeNodeT * BinaryTreeT:Search( T t, BinaryTreeNodeT *root ) /二叉树搜索 if( isEmpty() ) /判断是否为空，若为空树，则跳出函数 cout The tree is e