数据结构二叉树二叉搜索树堆相关C++代码.docx

Main.cpp# include #include# include CLASS.h# include MEAU.husing namespace std;void main ()class Tree tree; /实例化功能类system(cls);mainmenu(tree);CLASS.h# include # include# include#include #include using namespace std;template /功能类的声明class Tree;template class TreeNode /数据类friend class Tree;private:T element; /数据值TreeNode * Left;/左孩子结点TreeNode * Right;/右孩子结点public:TreeNode() /无参构造函数element=0;Left=Right=NULL;TreeNode(const T& ele) / 数据参数构造函数element=ele;TreeNode(const T & ele,TreeNode * l,TreeNode * r)/ 数据参数与孩子指针构造函数element=ele;Left=l;Right=r;void Setleft(TreeNode * l)/设置左孩子指针Left=l;void Setright(TreeNode * r)/设置右孩子指针Right =r;void Setele(const T& ele )/设置数据值element=ele;TreeNode * Getleft()const /读取左孩子return Left;TreeNode* Getright()const/ 读取右孩子return right;T Getele()const /读取数据return element;bool Isleaf()const /判断是否为叶子结点if(Left=Right & Left=NULL)return true;elsereturn false;template class MaxHeapfriend class Tree;private:T * HeapArray;int currentsize;int Maxsize;public:MaxHeap()currentsize=0;Maxsize=20;HeapArray=new TMaxsize;virtual MaxHeap()delete HeapArray;/筛选法回朔void SiftDown(int pointer)int i=pointer;/父节点int j=2*i+1;/左孩子T temp=HeapArrayi;/记录父结点关键码while(jcurrentsize)if(jcurrentsize-1 & HeapArrayjHeapArrayj+1)j+;/孩子中最大的一个if(tempHeapArrayj)HeapArrayi=HeapArrayj;HeapArrayj=temp;i=j;j=2*j+1;else break;/建立堆void BuildHeap()T temp;int i=0;couttemp;while(temp!=0 & temp!=0)HeapArrayi+=temp;currentsize+;cintemp;for(i=currentsize/2-1;i=0;i-)SiftDown(i);/输出堆void showHeap()if(currentsize=0)cout堆中无元素！endl;elseint i=0;cout堆中元素：;for(i=0;icurrentsize;i+)coutHeapArrayi ;coutendl;/删除堆顶T RemoveMax()if(currentsize=0)cout堆中无元素！ 1)SiftDown(0);return temp;/删除元素void Removeheapelement(int i)HeapArrayi=HeapArraycurrentsize-1;currentsize-;if(currentsize 1)SiftDown(i);/插入元素void InsertHeap()coutHeapArraycurrentsize;currentsize+;int temp=HeapArraycurrentsize-1;int i,j;j=currentsize-1;/子结点i=(j-1)/2;/父节点while(j0 & HeapArrayjHeapArrayi)/子结点大于父结点或者到顶HeapArrayj=HeapArrayi;HeapArrayi=temp;j=i;i=(j-1)/2;/查找元素int find(int temp)int i=0;while(HeapArrayi!=temp & icurrentsize)i+;if(HeapArrayi=temp)return i;elsereturn -1;templateclass Tree /功能类private:TreeNode * root; /根结点MaxHeap * top;/堆顶int d1;int d2;int d0;int high;int width;T max;TreeNode * creat() /结点构造函数TreeNode * temp;T ele;cinele;/max=(maxele)?max:ele;if(ele=0 | ele=0)return NULL;else temp=new TreeNodesizeof(TreeNode);temp-Setele(ele);cout输入Getele()Setleft(creat();elsetemp-Setleft(NULL);cout输入Getele()Setright(creat();elsetemp-Setright(NULL);return temp;int count(TreeNode *pointer,int &d0,int &d1,int &d2,T &max)int i,j;if(!pointer)return 0;elsemax=(maxpointer-element)?max:pointer-element;if(pointer-Left=NULL) & (pointer-Right=NULL)d0+;else if(pointer-Left !=NULL) & (pointer-Right !=NULL)d2+;elsed1+;i=count(pointer-Left,d0,d1,d2,max);j=count(pointer-Right,d0,d1,d2,max);return (ij)?(i+1):(j+1);int Width(TreeNode* pointer,int i) int static n20;/向量存放各层结点数int static maxw=0;/最大宽度if(pointer)if(i=1) maxw=1;for(int k=0;kLeft)ni+;if(pointer-Right)ni+;elseif(pointer-Left)ni+;if(pointer-Right) ni+;if(maxwni)maxw=ni;/coutelement:ni iLeft)Width(pointer-Left,i+1);if(pointer-Right)Width(pointer-Right,i+1);return maxw;void exchange1(TreeNode * pointer)if(pointer)TreeNode* temp;temp=pointer-Left;pointer-Left=pointer-Right;pointer-Right=temp;if(pointer-Left)exchange1(pointer-Left);if(pointer-Right)exchange1(pointer-Right);void dleaves(TreeNode*pre,TreeNode*pointer,int flag)/flag为标记，0左1右if(pointer-Isleaf()if(pre=pointer)delete pointer;root=NULL;elsedelete pointer;pointer=NULL;if(!flag)pre-Left=NULL;elsepre-Right=NULL;elseif(pointer-Left)dleaves(pointer,pointer-Left,0);if(pointer-Right)dleaves(pointer,pointer-Right,1);bool IscompleteTree()int flag=0; /未出现叶子结点using std:queue;queueTreeNode* nodeQueue;TreeNode* pointer=root;if(pointer)nodeQueue.push(pointer);while(!nodeQueue.empty()pointer=nodeQueue.front();nodeQueue.pop();if(pointer-Left=NULL & pointer-Right!=NULL)/出现只有右结点的结点return false;if(flag=0)if(pointer-Isleaf()flag=1; /叶子结点出现if(pointer-Left!=NULL & pointer-Right=NULL)/出现度为1的结点flag=1;elseif(pointer-Isleaf()=false)return false;if(pointer-Left)nodeQueue.push(pointer-Left);if(pointer-Right)nodeQueue.push(pointer-Right);return true;public:Tree() /构造函数root=NULL;top=NULL;d1=d2=d0=high=width=0;max=0;void features()if(root=NULL)cout树空！endl;elsecout度为0的结点数：d0endl;cout度为1的结点数：d1endl;cout度为2的结点数：d2endl;cout结点最大值：maxendl;cout树的高度：highendl;cout树的宽度：widthendl;if(IscompleteTree()cout是完全二叉树！endlendl;elsecoutBU,BU,BU,不是完全二叉树！endl;void CreatTree()/创建树if(root=NULL)cout 创建二叉树endl;cout输入根结点值：;root=creat();cout创建结束endl;d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1);elsechar c;coutc;if(c=y | c=Y)cout输入根结点值：;root=creat();cout覆盖创建结束endl;d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1);elsecout保留原树Isleaf()reutrn true;else return false;TreeNode * Getroot()/返回根结点return root;void visit(TreeNode * pointer) /访问结点值coutelement ;void Preorder() /前序遍历if(root=NULL)cout树空！endl;return ;cout前序遍历：;using std:stack;stackTreeNode * nodeStack;TreeNode* pointer =root;/保留根结点while(!nodeStack.empty() | pointer)/栈空为止if(pointer)visit(pointer);/访问元素if(pointer-Right != NULL)/右结点入栈nodeStack.push(pointer-Right);pointer=pointer-Left;/转向访问左子树else/左树为空，转向右树pointer=nodeStack.top();nodeStack.pop();/删除栈顶coutendl;void Inorder()/中序遍历if(root=NULL)cout树空！endl;return ;cout中序遍历：;using std:stack;stackTreeNode * nodeStack;TreeNode* pointer =root;while(!nodeStack.empty() | pointer)/栈空为止if(pointer)nodeStack.push(pointer);/结点入栈pointer=pointer-Left;/转向左树elsepointer=nodeStack.top();/左树为空时，访问栈顶(左边最小左子树头结点)nodeStack.pop();visit(pointer);pointer=pointer-Right;/转向其右子树coutendl;void Postorder()/后序遍历if(root=NULL)cout树空！endl;return ;cout后序遍历：;using std:stack;stackTreeNode * nodeStack;TreeNode* pointer =root;TreeNode* pre =root;/记录之前访问的结点while(pointer)while(pointer-Left!=NULL)/左结点持续入栈nodeStack.push(pointer);pointer=pointer-Left;while(pointer!= NULL & (pointer-Right=NULL | pointer-Right = pre)/左子树空并且（右子树空或者右子树刚被访问 ）visit(pointer);/访问子树头结点pre=pointer;/更新pre位置if(nodeStack.empty()/栈空函数结束coutRight;coutendl;void Levelorder()/广度优先遍历if(root=NULL)cout树空！endl;return ;cout层次遍历：;using std:queue;queueTreeNode* nodeQueue;TreeNode* pointer=root;if(pointer)/根结点入队nodeQueue.push(pointer);while(!nodeQueue.empty()pointer=nodeQueue.front();visit(pointer);/访问队头元素nodeQueue.pop();if(pointer-Left)/队头元素左右结点入队nodeQueue.push(pointer-Left);if(pointer-Right)nodeQueue.push(pointer-Right);coutendl;void Showtree() /凹凸法if(root=NULL)cout树空！endl;return ;cout凹入法展示：;using std:stack;stackTreeNode * nodeStack;stack count;stack flag;TreeNode* pointer =root;int n=0;int f=0;coutendl;while(!nodeStack.empty() | pointer)if(pointer)for(int i=0;in;i+)cout ;visit(pointer);for(int i=0;i40-n;i+)cout*;if(f=0)coutROOT;else if(f=1)coutLEFT;else if(f=2)coutRIGHT;coutRight != NULL)nodeStack.push(pointer-Right);count.push(n+4);flag.push(2);pointer=pointer-Left;n=n+4;f=1;elsepointer=nodeStack.top();nodeStack.pop();/删除栈顶n=count.top();count.pop();f=flag.top();flag.pop();void exchange()if(root=NULL)cout树空！Isleaf()=true)cout一个结点！endl;elseexchange1(root);cout交换完成！endl;void delete_leaves()if(root=NULL)cout数空！endl;elsedleaves(root,root,0);cout函数已执行endl;d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1);int* Show1(TreeNode* pointer,int i) int static n20;/存放各层结点数if(pointer)if(i=1) for(int k=0;kLeft)ni+;if(pointer-Right)ni+;elseif(pointer-Left)ni+;if(pointer-Right) ni+;/coutni: niLeft)Show1(pointer-Left,i+1);if(pointer-Right)Show1(pointer-Right,i+1);return n;void Show()if(root=NULL)cout树空！endl;return ;cout树形输出：endl;high=count(root,d0,d1,d2,max);width=Width(root,1);using std:queue;queueTreeNode* nodeQueue;queuecount;TreeNode* pointer=root;int n=1,k=0,prek=0; /标记元素int *N,m=1; /记录每轮的元素个数int counter=0; /记录每轮打印的个数N=Show1(root,1);int x=0,y=0;/记录距离if(pointer)/根结点入队nodeQueue.push(pointer);count.push(n);while(!nodeQueue.empty()pointer=nodeQueue.front();nodeQueue.pop();k=count.front();count.pop();if(counter=0)x=pow(2,high-m+1)-1;/记录下一个打印距本次打印的距离y=pow(2,high-m)-1;/本次打印的基数for(int i=0;iy+(k-pow(2,m-1)*(x+1);i+)cout ;prek=k;elsefor(int i=0;i(k-prek)*x+(k-prek-1);i+)cout ;prek=k;coutelement;/访问队头元素counter+;if(counter=Nm)coutLeft)/队头元素左右结点入队nodeQueue.push(pointer-Left);count.push(n);n=n+1;if(pointer-Right)nodeQueue.push(pointer-Right);count.push(n);/前序中序TreeNode* Preincreattree(T *pre,T *in,int length)TreeNode*temp;if(length=0)temp=NULL;elsetemp=new TreeNodesizeof(TreeNode);temp-element=*pre;int Leftlength=strchr(in,*pre)-in;temp-Left=Preincreattree(pre+1,in,Leftlength);/左子树int Rightlength=length-Leftlength-1;temp-Right=Preincreattree(pre+1+Leftlength,in+1+Leftlength,Rightlength);/右子树return temp;void PreIncreat()cout我们假设没有重复元素，且先序与中序匹配endl;T pre20,in20;int length;coutpre;coutin;length=strlen(pre);root=Preincreattree(pre,in,length);/参数d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1); /中序后序TreeNode* Inpostcreattree(T *post,T *in,int length)TreeNode*temp;if(length=0)temp=NULL;elsetemp=new TreeNodesizeof(TreeNode);temp-element=postlength-1;int Leftlength=strchr(in,postlength-1)-in;temp-Left=Inpostcreattree(post,in,Leftlength);/左子树int Rightlength=length-Leftlength-1;temp-Right=Inpostcreattree(post+Leftlength,in+1+Leftlength,Rightlength);/右子树return temp;void InPostcreat()cout我们假设没有重复元素，且中序与后序匹配endl;T post20,in20;int length;coutin;coutpost;length=strlen(post);root=Inpostcreattree(post,in,length);/参数d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1);/二叉搜索树函数void insertcreat(T &value)TreeNode *pointer =root,*prev=NULL; /prev记录pointer的父节点while(pointer)/pointer到二叉树的底部prev=pointer;if(pointer-element value)pointer=pointer-Left;elsepointer=pointer-Right;if(root=NULL)/root为空，则直接插入到rootroot=new TreeNode1;root-element=value;else if(prev-element value)/判断value应该存放的位置prev-Left=new TreeNode1;prev-Left-element=value;elseprev-Right=new TreeNode1;prev-Right-element=value;void Creatsearchtree()T value;if(root!=NULL)cout覆盖创建二叉搜索树endl;root=NULL;coutvalue;while(value!=0 & value!=0)insertcreat(value);coutvalue;d1=d2=d0=high=width=max=0;high=count(root,d0,d1,d2,max);width=Width(root,1);cout创建完毕endl;TreeNode* search(TreeNode* pointer,T key)/搜索函数while(NULL != pointer & key != pointer-element)pointer=(key element)? search(pointer-Left,key):search(pointer-Right,key);return pointer;void Searchtreesearch()/搜索调用函数TreeNode* pointer;T value;coutvalue;pointer=search(root,value);if(pointer)cout找到:elementendl;elsecout该元素不存在！endl;/合并删除void deleteByMerging()/合并删除TreeNode *temp,*pointer,*pre;T value;coutvalue;/输入要删除的结点值pointer=pre=root;/prev为其父结点int flag=1;while(pointer & flag)if(value=pointer-element)/找到后flag记为0flag=0;else if(value element)pre=pointer;pointer=pointer-Left;else if(value pointer-element)pre=pointer;pointer=pointer-Right;if(pointer=NULL)/遍历后没有找到cout元素不存在Left=NULL & pointer-Right=NULL)/要删除的结点是叶子结点if(pointer=root)/删除根结点root=NULL;else if(pre-Left=pointer)/父结点的左结点pre-Left=NULL;else if(pre-Right=pointer)/父结点的右结点pre-Right=NULL;delete pointer;else if(pointer-Left=NULL | pointer-Right=NULL)/要删除的结点只有一个孩子if(pointer = root)/删除根结点 if(pointer-Left = NULL)root = pointer-Right;elseroot = pointer-Left; elseif(pre-Left = pointer & pointer-Left)/pointer是父结点的左孩子，讨论pointer的孩子pre-Left=pointer-Left;else if(pre-Left = pointer & pointer-Right)pre-Left = pointer-Right; else if(pre-Right = pointer & pointer-Left)/pointer是父结点的右孩子，讨论pointer的孩子pre-Right = pointer-Left;elsepre-Right = pointer-Right; delete pointer; else/pointer有两个孩子if(pre=pointer)/删除根结点temp=pointer-Left;/找到左树中最大的结点