二叉树应用之二叉树基本算法的实现

1、二叉树应用二叉树基本算法的实现【功能要求】实现 Create 方法，要求键盘输入二叉树结点序列，创建一棵二叉树(提示：前 序递归)实现 SwapTree 方法，以根结点为参数，交换每个结点的左子树和右子树(提示： 前序递归)增加 InorderTree 方法，采用非递归方法实现二叉树的中序遍历 你可以选择：对 BinaryTree 模板进行功能扩充； 自己定义并实现二叉树类 要求键盘输入二叉树结点序列 结点序列可以是前序，也可以是层次 空结点以#表示【代码实现】/ 二叉树 01.cpp : Defines the entry point for the console application.

2、/#include stdafx.h#include using namespace std;templateclass BinaryTreeNode;templateclass BinaryTreepublic:BinaryTree()root=0;BinaryTree(const BinaryTree &Tree ) copy(Tree.root,root);BinaryTree();bool IsEmpty()constreturn (root)?false:true);void Creat();bool Root (T&x)const;void MakeTree(const T&ele

3、ment,BinaryTree&left,BinaryTree&right);void BreakTree( T&element,BinaryTree&left,BinaryTree&right);void PreOrder(void (*Visit)(BinaryTreeNode*u)PreOrder(Visit,root);void InOrder(void (*Visit)(BinaryTreeNode*u)InOrder(Visit,root);void PostOrder(void (*Visit)(BinaryTreeNode*u)PostOrder(Visit,root);voi

4、d LevelOrder(void(*Visit)(BinaryTreeNode*u);void PreOutput()PreOrder(Output,root);coutendl;void InOutput()InOrder(Output,root);coutendl;void Postput()PostOrder(Output,root);coutendl;void LevelOutPut()LevelOrder(Output);coutendl;void Delete()PostOrder(Free,root);root=0;int Height()constreturn Height(

5、root);int Size()constreturn Size(root);BinaryTreeNode*iCreat();bool equal(BinaryTree&Tree)return compare(root,Tree.root);void swap() swap(root);int leave()return leave(root);int noleave()return noleave(root);private:BinaryTreeNode*root;void PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);v

6、oid InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t);void PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t); static void Output(BinaryTreeNode* t) coutdata ;static void Free(BinaryTreeNode*t)delete t;int Height(BinaryTreeNode*t)const;int Size(BinaryTreeNode*t)const;bool compare(Bina

7、ryTreeNode*t1,BinaryTreeNode*t2);void copy(const BinaryTreeNode*t1,BinaryTreeNode*&t2);void swap(BinaryTreeNode*t);int leave(BinaryTreeNode*t);int noleave(BinaryTreeNode*t); template class LinkedQueue; template class Node friend LinkedQueue; private:T data;Node*link; template class LinkedQueue publi

8、c:LinkedQueue() front=rear=0; LinkedQueue(); bool IsEmpty()constreturn (front)?false:true);bool IsFull()const;T First()const;T Last()const;LinkedQueue&Add(const T &x);LinkedQueue&Delete(T&x); private:Node*front; Node*rear; template bool BinaryTree:Root(T&x)const if(root)x=root-data;return true;else

9、return false;templatevoid BinaryTree:MakeTree(const T&element ,BinaryTree&left,BinaryTree&right)root=new BinaryTreeNode(element,left.root,right.root); left.root=right.root=0;templatevoidBinaryTree:BreakTree(T&element ,BinaryTree&left,BinaryTree&right) element=root-data;left.root=root-LeftChild; righ

10、t.root=root-RightChild;delete root;root=0;templatevoidBinaryTree:PreOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode *t)if(t)Visit(t);PreOrder(Visit,t-LeftChild);PreOrder(Visit,t-RightChild);templatevoidBinaryTree:InOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode* t)if(t)InOrder(Visit,t-LeftC

11、hild);Visit(t);InOrder(Visit,t-RightChild);templatevoidBinaryTree:PostOrder(void(*Visit)(BinaryTreeNode*u),BinaryTreeNode*t)if(t)PostOrder(Visit,t-LeftChild);PostOrder(Visit,t-RightChild);Visit(t);templatevoid BinaryTree:LevelOrder(void(*Visit)(BinaryTreeNode*u)LinkedQueueBinaryTreeNode* Q;BinaryTre

12、eNode*t;t=root;while(t)Visit(t);if(t-LeftChild) Q.Add(t-LeftChild);if(t-RightChild) Q.Add(t-RightChild);if(Q.IsEmpty() return ;else Q.Delete(t);templateint BinaryTree:Height(BinaryTreeNode*t)constif(!t) return 0;int hl=Height(t-LeftChild);int hr=Height(t-RightChild);if(hlhr) return +hl;else return +

13、hr; template int BinaryTree:Size(BinaryTreeNode*t)const if(!t) return 0;int sl=Size(t-LeftChild);int sr=Size(t-RightChild);return (1+sl+sr); template BinaryTreeNode*BinaryTree:iCreat( )T ch;cinch;BinaryTreeNode * root;if(ch=#)root=NULL;elseroot=new BinaryTreeNode; root-data=ch;root-LeftChild=this-iC

14、reat(); root-RightChild=this-iCreat();return root;templatevoid BinaryTree:Creat()this-root = iCreat(); template bool BinaryTree:compare(BinaryTreeNode *t1, BinaryTreeNode *t2) if (t1=NULL&t2=NULL) return true;else if (t1!=NULL&t2=NULL) return false;else if (t1=NULL&t2!=NULL) return false;else if (t1

15、-data!=t2-data) return false;else return(compare(t1-leftChild,t2-leftChild)&compare(t1-RightChild,t2-RightChi ld); template void BinaryTree:copy(const BinaryTreeNode*t1,BinaryTreeNode*&t2) if(t1)t2=new BinaryTreeNode; t2-data=t1-data;copy(t1-LeftChild,t2-LeftChild); copy(t1-RightChild,t2-RightChild)

16、; template void BinaryTree:swap(BinaryTreeNode *t)BinaryTreeNode *temp;if(!t) return;elsetemp=t-LeftChild; t-LeftChild=t-RightChild; t-RightChild=temp;swap(t-leftChild); swap(t-RightChild); template int BinaryTree:leave(BinaryTreeNode*t)if(!t) return 0;if(t-LeftChild=0&t-RightChild=0)return 1;int le

17、afl=leave(t-LeftChild);int leafr=leave(t-RightChild);return leafl+leafr; template int BinaryTree:noleave(BinaryTreeNode *t) if(!t) return 0;if(!t-LeftChild&!t-RightChild)return 0;int leafl=noleave(t-LeftChild);int leafr=noleave(t-RightChild);return leafl+leafr+1; template class BinaryTree; template

18、class BinaryTreeNodefriend BinaryTree;public:BinaryTreeNode()LeftChild=RightChild=0;BinaryTreeNode(const T&e)data=e;LeftChild=RightChild=0;BinaryTreeNode(const T&e,BinaryTreeNode *l,BinaryTreeNode *r) data=e;LeftChild=l;RightChild=r;private:T data; BinaryTreeNode*LeftChild,*RightChild;template LinkedQueue:LinkedQueue()Node*next;while(front) next=front-link; delete front; front=next; template LinkedQueue&LinkedQueue:Add(const T &x) Node*p=new Node; p-data=x;p-link=0;if (front) rear-link=p;else front=p;