数据结构 关于树的几个证明题及代码实现_数据结构证明题

一、求二叉树的深度

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
int depth(BTNode *T){
	if(!T)
		return 0;
	
	int ldepth = depth(T->lchild);
	int rdepth = depth(T->rchild);
	
	return ldepth>rchild ? (ldepth+1) : (rdepth+1);
}

二、判断一棵树是否是排序二叉树（递归实现）

思路是：中序遍历排序二叉树，遍历序列有序

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
int preVal = MIN;		//MIN表示int变量所能表示的最小值
 
bool isBST(BTNode *T){
	if (!T)
		return true;
	
	bool l = isBST(T->lchild);
	
	if (preVal > T->data)
		return false;
	else
		preVal = T->data;
	
	bool r = isBST(T->rchild);
	
	return l&&r;
}

三、判断一棵树是否是排序二叉树（非递归实现）

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
bool isBST(BTNode *T){
	BTNode* stack[NODE_NUM];
	int top = -1;
	
	while(T || top != -1){
		while(T){
			stack[++top] = T;
			t = t->lchild;
		}
		
		T = stack[top--];
		
		if (T->data > stack[top]->data)
			return false;
		
		T = stack[top--]->rchild;
	}
	
	return true;
}

四、求Haffman树的带权路径长度

带权路径长度：树中每个  叶子节点的权值 *该叶子节点到根节点的路径长度（边数）  之和

思路：采用层序遍历，通过层数可以知道该层上的叶子节点的路径长度

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
int method(BTNode *T){
	BTNode* Q[NODE_NUM];
	int front = 0,rear = 0,sum = 0,level,node_num;	//level为当前遍历的层数，node_num为当前层的结点数
	
	//树为空或者仅有一个根节点，则带权路径为0
	if(!T || (!T->lchild && !T->rchild))
		return 0;
	
	Q[rear++] = Q->lchild;
	Q[rear++] = Q->lchild;
	level = 2;
	node_num = 2;
	
	while(isNotEmpty(Q)){
		int num = 0;		//用来记录下一层的结点个数
		BTNode* p;
		for(int i=0;i<node_num;i++){
			p = Q[front--];
			if (!p->lchild)
				sum += (level-1) *p->weight;
			else{
				Q[rear++] = Q->lchild;
				Q[rear++] = Q->lchild;
				num += 2;
			}
		}
		level++;
		node_num = num;
	}
	
	return sum;
}

五、用递归算法判断叶子结点的个数

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
int count;		//结点总数
 
void method(BTNode *T){
	if (T){
		method(T->lchild);
		if (!T->lchild && !T->rchild)
			count++;
		method(T->rchild);
	}
}

六、判断一棵二叉树是否平衡

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
bool main(BTNode *T){
	int depth = 0;
	return method(T,&depth);
}
 
bool method(BTNode *T){
	if (!T){
		&depth = 0;
		return true;
	}
	
	//存储每颗子树的高度
	int ldepth,rdepth;
	bool l = method(T->lchild,*ldepth);
	bool r = method(T->rchild,*rdepth);
	
	//如果有一颗子树不平衡，或者以当前递归结点为根的根树不平衡，则返回false，只要有一个false，
	//则会一直返回false，直到退出程序
	if (!(l&&r) || (ldepth-rdepth)<-1 || (ldepth-rdepth)>1)
		return false;
	
	//根树平衡，则算出该树的高度
	*depth = ldepth>rdepth ? (ldepth+1) : (rdepth+1);
	return true;
		 
}

七、非递归算法求二叉树只有一个孩子的结点个数（单分支）

typedef struct BTNode BTNode{
	Elemtype data;
	struct BTNode *lchild,*rchild;
} BTNode;
 
bool method(BTNode *T){
	BTNode* stack[NODE_NUM];
	int top = -1,count = 0;
	
	if (!T)
		return 0;
	
	while (T || top != -1){
		while(T){
			stack[++top] = T;		//入栈
			T = T->lchild;
		}
		
		T = stack[top--];
		
		if ((!T->lchild && T->rchild) || (T->lchild && !T->rchild))
			count++;
		
		T = T->rchild;
	}
	
	return count;	 
}

八、骑士巡游（java）

#include <stdio.h>
 
const int n = 8;	//棋盘的行列数
int chess[n][n];	//1代表已遍历，0代表未遍历
int traverse[n*n];	//存放遍历路径，坐标(x,y)代表chess中：从上往下，从左往右的第x*8+y+1个位置
int index = 0;	
int step = n*n;	
 
bool move(int,int);
 
int main(){
	int x=0,y=1;
	
	if (move(x,y)){
		//输出遍历序列
		for (int i=0;i<index;++i)
			printf("%d ",traverse[i]);
		printf("\n index = %d",index);
		return 0;
	}else {
		printf("遍历失败！");
		return 0;
	}
	
	return 0;
}
 
//x，y∈[0,7]
bool move (int x,int y){
	if (chess[x][y] || x<0 || x>7 || y<0 ||y>7)
		return false;
	
	--step;
	chess[x][y] = 1;
	traverse[index++] = x*8+y+1;
	
	if (step==0)
		return true;
	
	if (move(x-1,y-2))
		return true;
	if (move(x-2,y-1))
		return true;
	if (move(x-2,y+1))
		return true;
	if (move(x-1,y+2))
		return true;
	if (move(x+1,y-2))
		return true;
	if (move(x+2,y-1))
		return true;
	if (move(x+2,y+1))
		return true;
	if (move(x+1,y+2))
		return true;
	
	return false;
}

九、证明：正则二叉树只有奇数个定点，偶数条边

证：由定义可知，正则二叉树结点的度要么为0，要么为2，设Ni为度为i的结点个数，令结点总数为n，则有：

        N0 = N2 + 1 ,  N0 + N2 = N ，推得：2 * N2 + 1 = n，故有奇数个顶点，又边数 = 顶点数 - 1，则有

        偶数条边