2021-11-27 树与二叉树算法题

2021-11-27 树与二叉树算法题

首先先简单定义一个二叉树及其创建过程：

#include
#include

#define QSize 50
typedef char TElemType;
typedef struct BiTNode {
	TElemType data;
	struct BiTNode* lchid, * rchid;
}BiTNode, * BiTree;

void CreateBiTree(BiTree& T) {
	TElemType a;
	TElemType temp;
	scanf("%c", &a);
	temp = getchar();
	if (a == '.')
		T = NULL;
	else {
		if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))exit(0);
		T->data = a;
		CreateBiTree(T->lchid);
		CreateBiTree(T->rchid);
	}
}

---

1、要求二叉树按二叉链表形式存储，利用队列的基本 *** 作写一个判别给定的二叉树是否是完全二叉树的算法。

解题思路：这道题应该思路蛮多的，这里使用了两种思路。第一种利用“一个结点没有左孩子就不应该有右孩子或一个结点只有左孩子而其兄弟结点就不应该有孩子，否则就不是完全二叉树”这种思路来做。第二种利用二叉树的层次序遍历，将二叉树中的结点逐层进队列，如果队列中有空结点指针则不是完全二叉树这种思路来做。

代码如下：

第一种思路：

bool JudgeComplete_BinTree1(BiTree T) {
	int flag = 0;
	//当一个结点没有左孩子或右孩子时为1，即到了完全二叉树最下方结点区，此时不再往队列中加入孩子结点
	//若一个结点没有左孩子却有右孩子或一个结点只有左孩子而其兄弟结点有孩子就不符合条件
	BiTree t = T, Q[QSize];
	int front = 0, rear = 0;
	if (t == NULL)
		return true;
	Q[rear] = t; rear = (rear + 1) % QSize;
	while (rear != front) {
		t = Q[front]; front = (front + 1) % QSize;
		if (t->lchid && !flag) {
			Q[rear] = t->lchid;
			rear = (rear + 1) % QSize;
		}
		else if (t->lchid)
			return false;
		else
			flag = 1;
		if (t->rchid && !flag) {
			Q[rear] = t->rchid;
			rear = (rear + 1) % QSize;
		}
		else if (t->rchid)
			return false;
		else
			flag = 1;
	}
	return true;
}

第二种思路：

bool JudgeComplete_BinTree2(BiTree T) {
	int flag = 0;//标识遍历状态
	BiTree t = T, Q[QSize];
	int front = 0, rear = 0;
	if (t == NULL)
		return true;
	Q[rear] = t; rear = (rear + 1) % QSize;
	while (rear != front) {
		t = Q[front]; front = (front + 1) % QSize;
		if (t == NULL)
			flag = 1;
		else if (flag)
			return false;
		else {
			Q[rear] = t->lchid; rear = (rear + 1) % QSize;
			Q[rear] = t->rchid; rear = (rear + 1) % QSize;
		}
	}
	return true;
}

运行结果如下：

---

 2、二叉树采用二叉链表存储：

（1）编写计算整个二叉树高度的算法（二叉树的高度也叫二叉树的深度）

（2）编写计算二叉树最大宽度的算法（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）

（1）

解题思路：树为空时，高度为0，用lh记录递归遍历出来的左子树高度，用rh记录遍历出来的右子树高度，二者取最大加一即可。

代码如下：

int BiTreeHeight(BiTree& T) {
	if (T == NULL)
		return 0;
	else {
		int lh = BiTreeHeight(T->lchid);
		int rh = BiTreeHeight(T->rchid);
		return (lh > rh) ? lh + 1 : rh + 1;//要记得加一,否则去往上一个递归中即上一层中高度没变
	}
}

（2）

解题思路：利用二叉树的层次序遍历，将二叉树中的非空结点逐层进队列，每遍历一层就进行一次最大宽度的比较，要使用到队列。

代码如下：

int BiTreeWidth(BiTree& T) {
	if (T == NULL)
		return 0;
	else {
		BiTree t = T, Q[QSize];
		int front = 0, rear = 0;
		Q[rear] = T; rear = (rear + 1) % QSize;
		int last = rear;//last记录同层最右结点在队列中的位置
		int temp = 0, maxw = 0;//temp记局部宽度, maxw记最大宽度
		while (rear != front) {
			t = Q[front]; front = (front + 1) % QSize;
			temp++;
			if (t->lchid != NULL) {
				Q[rear] = t->lchid; rear = (rear + 1) % QSize;
			}
			if (t->rchid != NULL) {
				Q[rear] = t->rchid; rear = (rear + 1) % QSize;
			}
			if (front >= last) {//一层结束
				last = rear;
				if (temp > maxw)
					maxw = temp;
				temp = 0;
			}
		}
		return maxw;
	}
}

这两小题的运行结果为：

---

3、请设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。 二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。分析算法的时间复杂度和空间复杂度。

解题思路：设置前驱结点指针pre，初始为空。第一个叶子结点由指针head指向，遍历到叶子结点时，就将它前驱的rchild指针指向它，最后叶子结点的rchild为空。

代码如下：

BiTree head = NULL, pre = NULL;
BiTree InOrderlink(BiTree& T) {
	if (T) {
		InOrderlink(T->lchid);
		if (T->lchid == NULL && T->rchid == NULL) {
			if (pre == NULL) {//处理第一个叶子结点
				head = T;
				pre = T;
			}
			else {
				pre->rchid = T;
				pre = T;
			}
		}
		InOrderlink(T->rchid);
		pre->rchid = NULL;//链表尾置空
	}
	return head;
}

//打印叶子链
void Print(BiTree head) {
	printf("二叉树的叶子结点链为：n");
	for (BiTree p = head; p != NULL; p = p->rchid) {
		printf("%c ", p->data);
	}
}

运行结果如下：

---

 4、设计算法统计一棵二叉树中所有叶结点的数目及非叶结点的数目。

解题思路：在递归的途中判断一下如果是叶子结点或非叶子结点相加就好。

代码如下：

void CountLeaves(BiTree T, int& n0, int& n) {
	if (T) {
		if (T->lchid == NULL && T->rchid == NULL)
			n0++;
		else
			n++;
		CountLeaves(T->lchid, n0, n);
		CountLeaves(T->rchid, n0, n);
	}
}

运行结果为：

---

5、假设非空二叉树bt采用二叉链表存储，其中所有结点数据域为正整数，设计一个递归算法求其中的最大值。

解题思路：这里提供两种做法，一个通过函数返回最大值，一个通过参数返回最大值。

代码如下：（这里我将树的data类型改成了int类型，输入-1代表结束）

第一种思路：

int FindMax1(BiTree T) {
	if (T == NULL)//树为空
		return 0;
	else if (T->lchid == NULL && T->rchid == NULL)//叶子结点
		return T->data;
	else {
		int max = (FindMax1(T->lchid) > FindMax1(T->rchid)) ? FindMax1(T->lchid) : FindMax1(T->rchid);//左子树和右子树取最大值
		return (T->data > max) ? T->data: max;//返回和当前结点比较出来的最大值
	}
}

第二种思路：

void FindMax2(BiTree T, int& max) {
	if (T != NULL) {
		if (T->data > max)
			max = T->data;
		FindMax2(T->lchid, max);
		FindMax2(T->rchid, max);
	}
}

第二种思路调用函数是max赋初值为0

运行结果相同，如下：

---

6、以孩子兄弟链表为存储结构的树，请设计递归算法求树的深度。

解题思路：由孩子兄弟链表表示的树，求高度的递归模型是：若树为空，高度为零；若第一孩子为空，高度为1和兄弟子树的高度的大者；否则，高度为第一孩子树高度加1和兄弟子树高度的大者。其非递归算法使用队列，逐层遍历树，取得树的高度。

代码如下：

int CSTreeHeight(CSTree T) { 
	int hc, hs;
	if (T == NULL) return 0;
	else if (!T->lchid)
		return (1 + CSTreeHeight(T->rsibling)); //孩子空，查兄弟的深度 
	else { //结点既有第一孩子又有兄弟，高度取孩子高度+1和兄弟子树高度的大者
		hc = CSTreeHeight(T->lchid);        //第一孩子树高
		hs = CSTreeHeight(T->rsibling);       //兄弟树高
			if (hc + 1 > hs) return (hc + 1);
			else return hs;
	}
}

运行结果和上方求高度的类似就不搞了

---

本次记录就到这，其实就是个做作业的过程，有参考答案所给的思路和代码