二叉树的一些题目

二叉树的一些算法

• 二叉树的共同祖先问题
• 二叉树的深度及结点最远距离
• 二叉树叶子节点统计与左右子树交换
• 中序线索化二叉树

二叉树的共同祖先问题

【输入形式】二叉树的前序和中序遍历序列，用以创建该二叉树的链式存储结构；以及二叉树的两个结点数据 x 和 y

【输出形式】结点数据值为 x 和结点数据值为 y 的最近的共同祖先
核心算法：

BiTree backtracking(BiTree root, char ch1, char ch2)
{
	if (root == NULL || root->data == ch1 || root->data == ch2){
		return root;
	}
	BiTree left = backtracking(root->LChild, ch1, ch2);
	BiTree right = backtracking(root->RChild, ch1, ch2);
	if (right && left) return root;
	return left ? left : right;
}

这个算法也算是回溯，停止条件是root为空或者找到了任意一个节点，然后返回。如果同时找到了两个节点就退出，若只找到left就返回left，没找到left就返回right。
完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include 
using namespace std;
typedef struct Node {
	char data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode, * BiTree;
BiTree TreeCreate(char pre[], char in[], int l1, int r1, int l2, int r2)
{
	if (l1 > r1) return NULL;
	BiTNode* s = new BiTNode;
	s->LChild = s->RChild = NULL;
	s->data = pre[l1];
	int i;
	for (i = l2; i <= r2; ++i)
	{
		if (in[i] == pre[l1])	break;
	}
	s->LChild = TreeCreate(pre, in, l1 + 1, l1 + i - l2, l2, i - 1);
	s->RChild = TreeCreate(pre, in, l1 + i - l2 + 1, r1, i + 1, r2);
	return s;
}
BiTree backtracking(BiTree root, char ch1, char ch2)
{
	if (root == NULL || root->data == ch1 || root->data == ch2){
		return root;
	}
	BiTree left = backtracking(root->LChild, ch1, ch2);
	BiTree right = backtracking(root->RChild, ch1, ch2);
	if (right && left) return root;
	return left ? left : right;
}

int main()
{
	BiTree bt;
	char pre[1000], in[1000];
	cin >> pre >> in;
	char ch1, ch2;
	cin >> ch1 >> ch2;
	int ml = strlen(pre), nl = strlen(in);
	bt = TreeCreate(pre, in, 0, ml - 1, 0, nl - 1);
	BiTree bt1 = bt;
	bt = backtracking(bt, ch1, ch2);
	if (bt1->data == ch1 || bt1->data == ch2) {
		cout << "NULL";
	}
	else
	{
		cout << bt->data;
	}
}

二叉树的深度及结点最远距离

【输入形式】拓展的前序遍历序列

【输出形式】深度和节点最远距离

【样例输入】AB#C##DE#G#H##F##

【样例输出】5 6
求深度就是让树走到最底层然后逐层向上返回，哪边更高就返回哪边，并加上1：

int depth(BiTree bt)
{
	if (bt == NULL) {
		return 0;
	}
	else {
		int a = depth(bt->LChild);
		int b = depth(bt->RChild);
		return (a > b) ? (a + 1) : (b + 1);
	}
}

求结点最远距离把上面求深度的代码改一下，分别求左右两边的深度然后相加，就是题目所求的结点最远距离：

int distance(BiTree bt)
{
	BiTree root = bt;
	int a, b;
	if (bt == NULL) {
		return 0;
	}
	else {
		a = depth(bt->LChild);
		b = depth(bt->RChild);
		if (bt != root) {
			return (a > b) ? (a + 1) : (b + 1);
		}
	}
	return a + b;
}

主函数与第一题相似，这里不再赘述。

二叉树叶子节点统计与左右子树交换

叶子节点统计我用的是递归方法，将树走到最底层，然后统计每一层的叶子节点个数并向上走，走到顶端时结束统计，最后的值就是叶子节点个数：

int count(BiTree bt)
{
	int cou = 0;
	int temp1, temp2;
	if (bt == NULL) {
		return 0;
	}
	if (bt!=NULL)
	{
		temp1 = count(bt->LChild);
		temp2 = count(bt->RChild);
		if (bt->LChild == NULL && bt->RChild == NULL) {
			cou++;
		}
	}
	cou += temp1 + temp2;
	return cou;
}

左右子树交换是从上到下的交换，我设置了一个temp节点，用类似于冒泡排序的办法：

void exchange(BiTree *bt)
{
	if ((*bt) == NULL) {
		return;
	}
	BiTree temp = NULL;
	if ((*bt)->LChild != NULL || (*bt)->RChild != NULL) {
		temp = (*bt)->LChild;
		(*bt)->LChild = (*bt)->RChild;
		(*bt)->RChild = temp;
		exchange(&((*bt)->LChild));
		exchange(&((*bt)->RChild));
	}
	return;
}

有个之前没注意的细节是，这个时候要传入树指针的指针，因为要对这个树的头结点进行 *** 作。如果只需要对头结点的后续结点进行 *** 作的话，就可以只传入树指针就行

中序线索化二叉树

【问题描述】创建一棵二叉树，接着中序线索化该二叉树，然后编写相应函数遍历该中序线索二叉树

【输入形式】二叉树拓展的前序遍历序列

【输出形式】中序遍历序列

【样例输入】AB#D##CE###

【样例输出】BDAEC

#include 
using namespace std;
typedef struct Node {
	int Ltag, Rtag;
	char data;
	struct Node* LChild;
	struct Node* RChild;
}BiTNode, * BiTree;
void CreateBitree(BiTree* bt)
{
	char ch;
	ch = getchar();
	if (ch == '#')	*bt = NULL;
	else
	{
		*bt = (BiTree)malloc(sizeof(BiTNode));
		(*bt)->data = ch;
		CreateBitree(&((*bt)->LChild));
		CreateBitree(&((*bt)->RChild));
	}
}
BiTree pre = NULL;
void Inthread(BiTree root)
{
	if (root != NULL)
	{
		Inthread(root->LChild);
		if (root->LChild == NULL) {
			root->Ltag = 1; root->LChild = pre;
		}
		if (pre != NULL && pre->RChild == NULL) {
			pre->RChild = root; pre->Rtag = 1;
		}
		pre = root;
		Inthread(root->RChild);
	}
}

BiTree left(BiTree bt)
{
	while (bt != NULL && bt->Ltag != 1 && bt->LChild != NULL)
	{
		bt = bt->LChild;
	}
	return bt;
}

void inprint(BiTree bt)
{
	BiTree p = left(bt);
	while (p != NULL)
	{
		cout << p->data;
		if (p->Rtag == 1) {
			p = p->RChild;
		}
		else {
			p = left(p->RChild);
		}
	}
}
int main()
{
	BiTree bt;
	CreateBitree(&bt);
	Inthread(bt);
	inprint(bt);
}

Inthread函数：把树线索化，如果左子树是空，就让左子树指向上一个，如果右子树空，就让右子树指向下一个结点，顺序是按照中序遍历二叉树的来的
left函数：寻找左边的结点直到这个结点的左子树是空的