二叉树.cpp

定时电路设计问题：定时电路是一个VLSI 芯片的关键部件

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_SIZE 20 //代表循环队列的大小
#define n 7        //代表二叉树的所有节点数量

typedef struct BiTNode  //定义树的节点
{ 
    int data;  //data代表从上一节点到本节点的权值
	int wi;    //wi代表从本节点到叶节点的路径最大值
    struct BiTNode *Lchild;
    struct BiTNode *Rchild;
}BiTNode,*BiTree;


typedef struct{ //定义一个循环队列的节点
	BiTree data[MAX_SIZE]; 
	int front, rear;
}sQueue;

void clearQueue(sQueue *q){ //清空队列
	q -> front = q -> rear = 0;
}

bool isQueueEmpty(sQueue *q){//判断循环队列是否为空
	if(q -> front == q -> rear) return true;
	else return false;
}

int enQueue(sQueue *q, BiTree chr){//将一个值插入循环队列
	if((q -> rear + 1) % MAX_SIZE == q -> front){
		printf("栈满\n");
		return 1;
	} else {
		q -> rear = (q -> rear + 1)	% MAX_SIZE;
		q -> data[q -> rear] = chr;
		return 0;
	}
}

BiTree deQueue(sQueue *q){//第一个元素出循环队列
	if(isQueueEmpty(q)) return NULL;
	else {
		q -> front = (q -> front + 1) % MAX_SIZE;
		return q -> data[q -> front];
	}
}

BiTree getQueueTop(sQueue *q){//取出循环列表的第一个值
	if(isQueueEmpty(q)) return NULL;
	else {		
		return q -> data[(q -> front + 1) % MAX_SIZE];
	}
}


int Max(int a,int b){  //求大小，返回较大的值
	if(a>b) return a;
	else return b;
}

BiTree CreateBiTree(sQueue *sq,int a[]){ //建立二叉树
	int i=0;
	BiTree p,q,BT,r;
	BT=NULL;
	while(i<n){
		p=NULL;
		if(i<n){
			p=(BiTree)malloc(sizeof(BiTNode));
			p->data=a[i];
			p->wi=0;
			p->Lchild=p->Rchild=NULL;
		}
		i++;
		enQueue(sq, p);	
		r=getQueueTop(sq);
        if(i==1) BT=p;
		else{
		  q=getQueueTop(sq);
		  if(p&&q){
			  if(i%2==0) q->Lchild=p;
			  else q->Rchild=p;
		  }
		  if(i%2==1) deQueue(sq);
		}
	}
   return BT;
}


int visit(int data,int wi) //访问该树节点
{
    printf("data=%d,",data);
	printf("wi=%d   ",wi);
    return 1;
}

void PostOrderTraverse(BiTNode *Bp)//后序遍历二叉树，并计算每个节点的wi值
{
    if(Bp){
		PostOrderTraverse(Bp->Lchild);
		PostOrderTraverse(Bp->Rchild);
		/*如果不是叶节点，则该节点wi值为它的左右子树wi+data中较大的一个*/
		if((Bp->Lchild!=NULL)&&(Bp->Rchild!=NULL)){
			int x=Bp->Lchild->data+Bp->Lchild->wi;//计算左子树wi+data
			int y=Bp->Rchild->data+Bp->Rchild->wi;//计算右子树wi+data
			Bp->wi=Max(x,y); //求较大的一个
			}else{
			Bp->wi=0;//如果是叶子节点 wi=0
		}
		visit(Bp->data,Bp->wi);
	}
}

void PreOrderTraverse(BiTNode *Bp){//中序遍历,修改需要改变的data值
	if(Bp){
		if((Bp->Lchild!=NULL)&&(Bp->Rchild!=NULL)){
			/*
			   如果该节点的wi减去左子树的wi值 大于左子树的data值 
			   则将左子树的data值修改为 该节点的wi减去左子树的wi值
			   否则data值不变不变
			*/
			if((Bp->wi-Bp->Lchild->wi)>Bp->Lchild->data){
			   Bp->Lchild->data=Bp->wi-Bp->Lchild->wi;
			}
			if((Bp->wi-Bp->Rchild->wi)>Bp->Rchild->data){
			    Bp->Rchild->data=Bp->wi-Bp->Rchild->wi;
			}
		}
		visit(Bp->data,Bp->wi);
		PreOrderTraverse(Bp->Lchild);
		PreOrderTraverse(Bp->Rchild);
	}
}

void LayOrderTraverse(BiTNode *Bp,sQueue *sq){//按层遍历输出二叉树
	BiTree p;
	int i=0;
	int j=1;
	if(Bp){
		clearQueue(sq);
	    enQueue(sq, Bp);
		while(!isQueueEmpty(sq)){
			i++;
			p=deQueue(sq);
			visit(p->data,p->wi);
			if(i==(pow(2.0,j)-1)){
				printf("第%d层\n",j-1);
				j++;
			}
			if(p->Lchild) enQueue(sq,p->Lchild);
			if(p->Rchild) enQueue(sq,p->Rchild);
		}
	}
}

int main(){
    int a[n]={0,2,1,2,1,2,1};
	//int a[n]={0,2,2,2,1,2,1,3,2,2,2,3,1,2,3};//按层给出各节点的初始data值
    BiTNode *Bp=NULL;
    sQueue *sq,*lq;
    sq=(sQueue *)malloc(sizeof(sQueue));
	lq=(sQueue *)malloc(sizeof(sQueue));
	clearQueue(sq);
    clearQueue(lq);
	Bp=CreateBiTree(sq,a); //建立二叉树
	printf("初始化二叉树:\n");
	LayOrderTraverse(Bp,lq);//按层遍历输出初始化的二叉树
	printf("\n");
	printf("后序遍历求得各节点到叶节点的值(wi值):\n");
    PostOrderTraverse(Bp);//后序遍历求得各节点到叶节点的值，即各节点的wi值
	printf("\n");
	printf("中序遍历改变其中的某些节点的权值(data值):\n");
    PreOrderTraverse(Bp);//中序遍历改变其中的某些节点的data值
	printf("\n");
	printf("最后的结果:\n");
    LayOrderTraverse(Bp,lq);//按层遍历输出最后结果
	printf("\n");
	return 0;
}