二叉樹---還原二叉樹---二叉搜尋樹

1，還原二叉樹

先序周遊的特點：先周遊根結點，再周遊左子樹，最後再周遊右子樹

中序周遊的特點：先周遊左子樹，再周遊根結點，最後再周遊右子樹

後序周遊的特點：先周遊左子樹，再周遊右子樹，最後再周遊根結點

1. 舉例

   先序周遊：A B D F G H I E C

   中序周遊：F D H G I B E A C

   如上，根據先序周遊以及中序周遊的特點，也就是說先序周遊的第一個為根結點，在中序周遊中找到根結點，則在中序周遊中根結點左邊為左子樹，根結點右邊為右子樹。

   如下圖，根據上述分解完後再将分解出的序列看作一組新的先序序列和中序序列，繼續分解，直到序列中隻有一個元素

   

#include<iostream>
using namespace std;
int g = 1;
typedef struct Node {
	char data;
	struct Node *left, *right;
}Node;
Node* restore(char *a, char *b,int n)   
{ 
	Node *p = (Node*)malloc(sizeof(Node));
	if (n == 0) return NULL;    //遞歸邊界
	p->data = *a;        //插入新結點
	p->left = NULL;
	p->right = NULL;
	if (n == 1) return p;     //遞歸邊界
	int k;
	for(int i=0;i<n;i++)    //尋找根結點
		if(*a==*(b+i))
		{
			k = i; break;
		}
	p->left = restore(a + 1, b, k);    //左子樹分解
	p->right = restore(a + k + 1, b + k + 1, n - k - 1);   //右子樹分解
	return p;
}
void preorder(Node *bt)     //先序周遊二叉樹
{
	if (g == 1)
		printf("先序周遊序列為：\n");
	g = g + 1;
	if (bt)
	{
		printf("%6c", bt->data);
		preorder(bt->left);
		preorder(bt->right);
	}
	else
		if (g == 2) printf("空樹\n");
}
int height(Node *p)    //深度的計算
{
	if (p == NULL)
		return 0;
	int Max = height(p->left);      
	if (Max < height(p->right))    //比較左右子樹的深度，傳回較大的值
		Max = height(p->right);
	return Max + 1;
}
int main()
{
	Node *p;
	char a[101], b[101];
	int n;
	cin >> n;
	cin >> a >> b;
	if (strcmp(a, b))
	{
		p = restore(a, b, n);
		preorder(p);
	}
	else
		cout << n << endl;
	cout << endl;
	cout << height(p) << endl;
	return 0;
}
           

二叉搜尋樹

二叉搜尋樹的原則：任意一個結點的左子樹均小于該結點，任意一個結點的右子樹均大于該結點。

特點：二叉搜尋樹的中序周遊為非遞增序列。

二叉搜尋樹其實質也就是有序數列的二分搜尋的過程。

直接給代碼，

#include<iostream>
# include <cstdio>
# include <cstring>
# include <algorithm>
using namespace std;
int cnt;
int a[1000];
struct node {
	int data;
	node *l, *r;
};
node *newnode() {     //生成結點
	node *t;
	t = (node *)malloc(sizeof(node));
	t->l = t->r = NULL;
	return t;
}
void jianshu(node *T, int d) {    //插入結點
	if (d>T->data) {
		if (!T->r) {
			T->r = newnode();
			T->r->data = d;
			return;
		}
		else {
			jianshu(T->r, d);
		}
	}
	else if (d<T->data) {
		if (!T->l) {
			T->l = newnode();
			T->l->data = d;
			return;
		}
		else {
			jianshu(T->l, d);
		}
	}
	else
		return;
}
void bianli(node *T) {   //先序周遊二叉樹
	if (T) {
		a[cnt++] = T->data;
		bianli(T->l);
		bianli(T->r);
	}
}
int main() {
	char flage;
	int num, i;
	node *T;
	T = newnode();
	cin >> num;
	flage = getchar();
	T->data = num;
	while (flage == ' ') {   //輸入序列
		cin >> num;
		jianshu(T, num);
		flage = getchar();
	}
	cnt = 0;
	bianli(T);
	for (i = 0; i <= cnt - 1; i++) {   //輸出序列
		if (i != cnt - 1) { 
			printf("%d ", a[i]);
		}
		else {
			printf("%d", a[i]);
		}
	}
	return 0;
}
           

希望能對你有一定的幫助，望大佬指正