二叉树结点路径求解源程序清单

二叉树结点路径求解源程序清单#include#include#include#include1.h#include2.h#include3.hvoidmain(){BiTreeNodeMakeCharTree(root);coutPrintVTree(root);coutcoutcharbuf;cinbuf;check(buf);path(root,buf);}………………………………………上述程序保存在主程序a.cpp中#include#includetemplatetemplateclassQueueNode{friendclassLinQueueprivate:QueueNode*next;public:Tdata;QueueNode(constT&item,QueueNode{data=item;next=ptrNext;}~QueueNode(){};};templateclassLinQueue{private:QueueNodeQueueNodeintsize;public:LinQueue(void);~LinQueue(void);voidQInsert(constT&item);TQDelete(void);TQFront(void)const;intQueueEmpty(void)const{returnsizevoidClearQueue(void);intGetSize(void)const{returnsize;};};templateLinQueue{front=rear=NULL;size=0;}templateLinQueue{ClearQueue();front=rear=NULL;}templatevoidLinQueue{QueueNodeif(rear!=NULL)rear-next=newNode;rear=newNode;if(front==NULL)front=newNode;size++;}templateTLinQueue{if(size==0){coutexit(0);}QueueNodeTdata=front-data;deletefront;front=p;size--;returndata;}templateTLinQueue::QFront(void)const{returnfront-data;}templatevoidLinQueue{QueueNodep=front;while(p!=NULL){p1=p;p=p-next;deletep1;}size=0;}……………………………………………以上程序保存在LinQueue.h中#include#includetemplate{private:BiTreeNodeBiTreeNodepublic:Tdata;//数据元素//构建函数和析构函数BiTreeNode():leftChild(NULL),rightChild(NULL){};BiTreeNode(Titem,BiTreeNode*left=NULL,BiTreeNode*right=NULL):data(item),leftChild(left),rightChild(right){};~BiTreeNode(){};//结点操作的成员函数BiTreeNode{returnleftChild;};BiTreeNode{returnrightChild;};};//定义一个右结点构造二叉树的外部函数templateBiTreeNode{BiTreeNodep=newBiTreeNodeif(p==NULL){coutexit(0);}returnp;}………………………上述二叉树的结点类设计代码保存在文件“1.h”中#include#include#include#includeLinQueue.hcharbuffer[100];intbb=-1;structInfo{intxIndent;//结点的x坐标intyLevel;//结点的y坐标};templatevoidPrintVTree(BiTreeNode{intscreenWidth=64;//screenWidth为屏幕的宽度intdataWidth=2;//dataWidth为孩子结点偏移量的倍数LinQueueInfos,s1,s2;intoffset,level=-1,i;Q.QInsert(t);//根结点指针入队列s.xIndent=screenWidth/dataWidth;//计算根结点的x坐标s.yLevel=0;//结点y的坐标QI.QInsert(s);//根结点的坐标信息入队列while(!Q.QueueEmpty()&&!QI.QueueEmpty())//当队列不空时{s2=s;p=Q.QDelete();//结点指针出队列s=QI.QDelete();//结点坐标出队列//走过空格if(s.yLevel!=level)//该层结点第一次显示{coutlevel=s.yLevel;for(i=0;i}else//该层结点以后的显示for(i=0;icoutbuffer[++bb]=p-data;if(p-Left()!=NULL)//当前结点的左孩子结点非空时{Q.QInsert(p-Left());//左孩子结点指针入队列s1.yLevel=s.yLevel+1;//y坐标为双亲结点的y坐标加1//计算第i层结点的偏移量offset=screenWidth/pow(dataWidth,s1.yLevel+1);//计算第i层左孩子结点的x坐标；s.xIndent为双亲结点的x坐标s1.xIndent=s.xIndent-offset;QI.QInsert(s1);//该结点坐标入队列}if(p-Right()!=NULL)//当前结点的右孩子结点非空时{Q.QInsert(p-Right());//右孩子结点指针入队列s1.yLevel=s.yLevel+1;//y坐标为双亲结点的y坐标加1//计算第i层结点的偏移量offset=screenWidth/pow(dataWidth,s1.yLevel+1);//计算第i层右孩子结点的x坐标；s.Indent为双亲结点的x坐标s1.xIndent=s.xIndent+offset;QI.QInsert(s1);//该结点坐标入队列}}}voidcheck(charbuf){for(inta=0;aif(buffer[a]==buf)break;}if(a=100){coutreturn;}}templatevoidpath(BiTreeNode{charcache[100];intk=0;cache[0]=buf;while(buf!=t-data){LinQueueBiTreeNodeq.QInsert(t);while(!q.QueueEmpty()){p=q.QDelete();if(p-Left()-data==buf||p-Right()-data==buf){cache[++k]=p-data;buf=p-data;break;}if(p-Left()!=NULL)q.QInsert(p-Left());if(p-Right()!=NULL)q.QInsert(p-Right());}}for(intg=k;g=0;g--){if(g!=0)coutelsecout}cout}…………………………………上述讨论的二叉树函数保存在文件“2.h”中#include#includevoidMakeCharTree(BiTreeNode{BiTreeNodeBiTreeNodeh=GetTreeNode('H');i=GetTreeNode('I');d=GetTreeNode('D',h,i);j=GetTreeNode('J');k=GetTreeNode('K');e=GetTreeNode('E',j,k);b=GetTreeNode('B',d,e);l=GetTreeNode('L');m=GetTreeNode('M');f=GetTreeNode('F',l,m);n=GetTreeNode('N');o=GetTreeNode('O');g=GetTreeNode('G',n,o);c=GetTreeNode('C',f,g);root=GetTreeNode('A',b,c);}………………………………………上述函数保存在文件“3.h”中