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

#include#include#include#include1.h#include2.h#include3.hvoid main()BiTreeNode *root;MakeCharTree(root);coutroot树为：endl;PrintVTree(root);coutendl;coutbuf; check(buf);path(root,buf); 上述程序保存在主程序a.cpp中#include#includetemplate class LinQueue;templateclass QueueNodefriend class LinQueue;private:QueueNode *next;public:T data;QueueNode(const T& item,QueueNode *ptrNext=NULL)data=item;next=ptrNext;QueueNode();templateclass LinQueueprivate:QueueNode * front;QueueNode * rear;int size;public:LinQueue(void);LinQueue(void);void QInsert(const T& item);T QDelete(void);T QFront(void)const;int QueueEmpty(void)constreturn size=0;void ClearQueue(void);int GetSize(void)constreturn size;templateLinQueue:LinQueue()front=rear=NULL;size=0;templateLinQueue:LinQueue(void)ClearQueue();front=rear=NULL;templatevoid LinQueue:QInsert(const T& item)QueueNode * newNode=new QueueNode(item,NULL);if(rear!=NULL) rear-next=newNode;rear=newNode;if(front=NULL) front=newNode;size+;templateT LinQueue:QDelete(void)if(size=0)cout队列已空无元素可删！endl;exit(0);QueueNode *p=front-next;T data=front-data;delete front;front=p;size-;return data;templateT LinQueue:QFront(void)constreturn front-data;templatevoid LinQueue:ClearQueue(void)QueueNode *p,*p1;p=front;while(p!=NULL)p1=p;p=p-next;delete p1;size=0; 以上程序保存在LinQueue.h中#include#includetemplate class BiTreeNodeprivate:BiTreeNode *leftChild; /左子树指针BiTreeNode *rightChild; /右子树指针public:T data; /数据元素 /构建函数和析构函数 BiTreeNode():leftChild(NULL),rightChild(NULL);BiTreeNode(T item,BiTreeNode *left=NULL,BiTreeNode *right=NULL):data(item),leftChild(left),rightChild(right);BiTreeNode();/结点操作的成员函数BiTreeNode * &Left(void) /返回值类型为指针的引用类型return leftChild;BiTreeNode * &Right(void) /返回值类型为指针的引用类型return rightChild;/定义一个右结点构造二叉树的外部函数templateBiTreeNode *GetTreeNode(T item,BiTreeNode *left=NULL,BiTreeNode *right=NULL)BiTreeNode *p;p=new BiTreeNode(item,left,right);if(p=NULL)cout内存分配失败！n;exit(0);return p; 上述二叉树的结点类设计代码保存在文件“1.h”中#include#include#include /包含有pow（）函数#includeLinQueue.hchar buffer100;int bb=-1;struct Infoint xIndent; /结点的x坐标int yLevel; /结点的y坐标;templatevoid PrintVTree(BiTreeNode * &t)int screenWidth=64; /screenWidth为屏幕的宽度int dataWidth=2; /dataWidth为孩子结点偏移量的倍数LinQueueBiTreeNode * Q; /Q是BiTreeNode类型指针的队列LinQueue QI; /Qi是元素为Info类型数据的队列BiTreeNode *p;Info s,s1,s2;int offset,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) /该层结点第一次显示coutn第s.yLevel层;level=s.yLevel;for(i=0;is.xIndent-1;i+)cout ;else /该层结点以后的显示for(i=0;is.xIndent-s2.xIndent;i+) cout ;coutdata; /显示结点信息buffer+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); /该结点坐标入队列void check(char buf)for(int a=0;a=100)cout您要查找的节点不在本二叉树中！endl;return;templatevoid path(BiTreeNode * &t,char buf)char cache100;int k=0; cache0=buf;while(buf!=t-data) LinQueueBiTreeNode *q; BiTreeNode *p; q.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(int g=k;g=0;g-) if(g!=0) coutcacheg;else coutcacheg;coutendl; 上述讨论的二叉树函数保存在文件“2.h”中#include#includevoid MakeCharTree(BiTreeNode * &root)BiTreeNode *b,*c,*d,*e,*f,*g,*h,*i;BiTreeNode *j,*k,*l,*m,*n,*o,*null=NULL;h=GetTreeNode(H);i=GetTreeNode(I);d=GetTreeNode(D,h,i);j=GetTreeNode(J);k=GetTreeNode(K);e=GetTre