目录

一、遍历模板

1、先序遍历模板

2、中序遍历模板

3、后序遍历模板

二、例题

 1、表达式(a-(b+c))*(d/e)存储在图6-7所示的一棵以二叉链表为存储结构的二叉树中（二叉树结点的data域为字符型)，编写程序求出该表达式的值（表达式中的操作数都是一位的整数)。

2、写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。

3、在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key 的结点是否存在（找到任何一个满足要求的结点即可)，如果存在，则将q指向该结点，否则q赋值为NULL，假设data为int型。

4、假设二叉树采用二叉链表存储结构存储，编写一个程序，输出先序遍历序列中第k 个结点的值，假设k 不大于总的结点数（结点data域类型为char型)。

一、遍历模板

1、先序遍历模板

//1、先序遍历
void preOrder(BTNode *p)
{
	if(p!=NULL){
		visit(p->data);
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
} 

2、中序遍历模板

//2、中序遍历
void inOrder(BTNode *p)
{
	if(p!=NULL){
		preOrder(p->lchild);
		visit(p->data);
		preOrder(p->rchild);
	}
} 

3、后序遍历模板

//3、后序遍历
void postOrder(BTNode *p)
{
	if(p!=NULL){
		preOrder(p->lchild);
		preOrder(p->rchild);
		visit(p->data);
	}
} 

二、例题

 1、表达式(a-(b+c))*(d/e)存储在图6-7所示的一棵以二叉链表为存储结构的二叉树中（二叉树结点的data域为字符型)，编写程序求出该表达式的值（表达式中的操作数都是一位的整数)。

 
int comp(BTNode *p){
	int A,B;
	if(p!=null){
		if(p->lchild!=NULL && p->rchild!=NULL){		//p要么有左右孩子，要么没有，没有左右孩子结点时，它是根节点，也就是最终计算的值 
			A=comp(p->lchild);
			B=comp(p->rchild);
			return op(lchild,rchild,p->data);
		}else{
			return p->data+'0';		//注意此处的写法，将字符转为数字 
		} 	
	}else{
		return 0;
	} 
}

2、写一个算法求一棵二叉树的深度，二叉树以二叉链表为存储方式。

 
int getDepth(BTNode *p){
	int LD,LR;
	if(p!=null){
		LD=getDepth(p->lchild);
		LR=getDepth(p->rcild);
		return LD>LR ? LD+1 : LR+1;
	}else{
		return 0;
	} 
}

3、在一棵以二叉链表为存储结构的二叉树中，查找data域值等于key 的结点是否存在（找到任何一个满足要求的结点即可)，如果存在，则将q指向该结点，否则q赋值为NULL，假设data为int型。

 

void search(BTNode *p,BTNode *&q, int key){
	if(p!=NULL) {
		if(p->data == key){
			q = p;
		}else{
			serach(p->lchild,q,key);
			search(p->rchild,q,key);
		}
	}	
} 

//改进
 void search(BTNode *p,BTNode *&q, int key){
	if(p!=NULL) {
		if(p->data == key){
			q = p;
		}else{					
			serach(p->lchild,q,key);
			if(q==NULL)                    //加了这一行 
				search(p->rchild,q,key);
		}
	}	
} 

4、假设二叉树采用二叉链表存储结构存储，编写一个程序，输出先序遍历序列中第k 个结点的值，假设k 不大于总的结点数（结点data域类型为char型)。

 

int n=0;
void getValue(BTNode *p,int k){
	if(p!=NULL){
		++n;                        //注意++n的位置，先加n，再与k比较
		if(k==n)
		{
			cout<data<child,k);
		getValue(p->rchild,k); 
	}
} 

//将题目改成中序
int n=0;
void getValueIn(BTNode *p,int k){
	if(p!=NULL){
		getValueIn(p->lchild,k);
		
		n++;
		if(k==n){
			cout<data<rchild,k);
	}
} 

//将题目改成后序 
int n=0;
void getValuePost(BTNode *p,int k){
	if(p!=NULL){
		getValuePost(p->lchild,k);
		getValuePost(p->rchild,k);
		
		n++;
		if(k==n){
			cout<data< 
三、层次遍历 
1、模板 
图6-10所示为二叉树的层次遍历，即按照箭头所指方向，按照1、2、3、4的层次顺序，对二叉树中各个结点进行访问（此图反映的是自左至右的层次遍历，自右至左的方式类似)。
 
 
 

void levelRecurse(BTNode *p){
	//1、定义并初始化一个循环队列
	int front,rear;
	BTNode *que[maxSize];  //maxSize为已定义好的变量，是队列的最大长度
	front=rear=0;			//初始化队列 
	BTNode *q; 
	
	if(p!=NULL){
		//根结点入队 
		rear = (rear+1)%maxSize;		//循环队列，入队出队时，千万别忘了取余MaxSize ！！！ 
		que[rear]=p;
		
		while(front!=rear){				//当队列不为空时进行循环 
			//出队头元素 
			front = (front+1)%maxSize; 
			q=que[front];
			 
			visit(q->data);				//访问队头元素
			
			if(q->lchild !=NULL){		//左孩子不为空
				//左孩子结点入队
				rear =(rear+1)%maxSize;
				que[rear]=q->lchild;				
			}
			
			if(q->rchild !=NULL){	//右孩子不为空
				//右孩子结点入队
				rear =(rear+1)%maxSize;
				que[rear]=q->rchild;				
			}
			 
		} 
		 
	} 
}
 
2、例题（层次遍历的应用） 
假设二叉树采用二叉链表存储结构存储，设计一个算法，求出该二叉树的宽度（具有结点数最多的那一层上的结点个数)。
 
 

typedef struct St		//定义队列中存储的元素的结构体，为结点+结点所在层数 
{
	BTNode *p;
	int levelNum;
}St;					//结构体定义，千万不要忘记最后的结尾！！！ 

int getWidthOfTree(BTNode *b){
	//1、定义并初始化一个队列
	St que[maxSize];
	int front,rear;
	front=rear=0; 
	
	BTNode *q;
	int Lnum=0; //存放最大层数 
	
	if(b!=NULL){	 
		//根节点入队，层数为1 
		rear++;
		que[rear]->p=b;
		que[rear]->levelNum=1； 
		
		while(front!=rear){
			++front;
			q=que[front]->p;
			Lnum=que[front]->levelNum; 
			
			if(q->lchild!=NULL){	//出队结点的左孩子结点及其层数入队 
				++rear;
				que[rear]->p=q->lchild;
				que[rear]->levelNum=Lnum+1;
			}
			if(q->rchild!=NULL){			//出队结点的右孩子结点及其层数入队 
				++rear;
				que[rear]->p=q->rchild;
				que[rear]->levelNum=Lnum+1;
			}
		}//神来之笔！！！循环结束时，Lnum中存放的是二叉树的最大层数，方便后面遍历。
		
		int max=0;//变量max存放最大宽度
		int n; //变量n暂时存放每一层的结点个数 
		for(int i=1;i<=Lnum;++i){		//根据层数遍历 
			n=0; 
			for(int j=0;jlevelNum == i)
					n++;
				if(n>max)
					max=n;
			}
		}
		return max; 	
	}else{
		return 0;
	} 
}