什么是树？如何表示和实现？树又有什么样性质？常见的应用有哪些？

引言

在了解树之前，先了解一下树在生活中的应用，比如：人类社会的家谱、社会组织结构和图书信息管理。这类信息结构都有一个共同点，那就是内部的不同事物之间都具有层次关系。

查找

查找是计算机中的基础操作，所谓基础，即是指查找操作广泛使用在计算机的各个应用，优秀的查找算法对于提高程序查找效率很有帮助。

查找：根据某个给定关键字 K ，从集合 R 中找出关键字与K相同的记录，查找可以分为两类：

静态查找：集合中记录是固定的，没有插入和删除操作，只有查找
动态查找：集合中记录是动态变化的，除查找操作外，还可能会有插入和删除操作

下面仅就静态查找展开讨论。

静态查找

静态查找的方法，根据存储结构的不同有着多种多样的方法，下面以数组为例来展开讨论。

顺序查找

利用数组下标来作为循环的边界，也可以通过**“哨兵”**的设计技巧来避免使用下标作为边界值，具体而言，即当前下标的数组值与哨兵的值相等时，跳出循环，代码如下：

int SequentialSearch(StaticTable *Tbl, ElementType K) {
	int i;
	Tbl->ElementType[0] = K;
	for(i = Tbl->Length; Tbl->ElementType[i] != K; i--);
	return i;
}

显然，顺序查找算法的时间复杂度为$O(n)$。

二分查找

二分查找在第一周的作业题中已经见过了。实际上，二分查找是有前提的：

序列有序
存储在数组中

在有序的基础下，假若要查找值X，分别设置left、mid、right三个下标值。每次时，查找mid = (left + right)/2，如若array[mid] > X，则有mid = right - 1，如若array[mid] < X，则有mid = left + 1，当left <= right这个条件不成立时，跳出循环。

注意：每次更新的left和right不能为mid。

二分查找的过程实际上可以构造出一棵二分查找判定树，而在这棵判定树上，每个结点需要查找的次数刚好为该节点所在的层数。也就是说，查找成功时的查找次数不会超过判定树的深度，从而可以得到，n 个结点的判定树的深度为$[log_{2}n] + 1$，这里就又有了一个新的概念 — ASL, Average Search Length，平均查找次数（也叫平均查找长度，后面单独讲查找时会再次遇到） ,可得：$ASL = (4 \times 4 + 4 \times 3 + 2 \times 2 + 1) \div 11 = 3$。

代码如下：

int BinarySearch(StaticTable *Tbl, ElementType K) {
	int left, right, mid, NotFound = -1;
	left = 1;
	right = Tbl->Length;
	while(left <= right) {
		mid = (left + right) / 2;
		if(K < Tbl->ElementType[mid]) right = mid - 1;
		else if(K > Tbl->ElementType[mid]) left = mid + 1;
		else return mid;
	}
	return NotFound;
}

二分查找的时间复杂度前面已经分析过了是$O(logN)$。

树

定义

树（Tree）：n（n≥0）个结点构成的有限集合，当n=0时，称为空树，对于任何一棵非空树，它具备以下性质：

树中有一个称为**“根（root）”**的特殊节点，用r表示
其余结点可分为m（m＞0）个互不相交的有限集$T_1, T_2, \ldots, T_m$，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”。
注意：
子树不能相交
除了根节点，每个节点有且仅有一个父节点
一棵N个节点的树有N-1条边
树是保证连通且边数最少的一种连接方式

基本术语

与树相关的基本术语如下：

结点的度（Degree）：结点的子树个数
树的度：树的所有结点中最大的度数
叶结点（Leaf）：度为 0 的结点
父结点（Parent）：有子树的结点是其子树的的根结点的父结点
子结点（Child）：若 A 结点是 B 结点的父结点，则称 B 结点是 A 结点的子结点，子结点也称为孩子结点
兄弟结点（Sibling）：具有同一父结点的各结点彼此是兄弟结点
路径和路径长度：从结点 $n_1$ 到 $n_k$ 的路径为一个结点序列 $n_1, n_2, \ldots, n_k, n_i$ 是 $n_{i+1}$ 的父结点，路径所包含的个数为路径的长度。
祖先结点（Ancestor）：沿树根到某一结点路径上所有结点都是这个结点的祖先结点
子孙结点（Descendant）：某一结点的子树中的所有结点都是这个结点的子孙
结点的层次（Level）：规定根节点在1层，其他任一结点的层数是其父结点层数加1
树的深度（Depth）：树中所有结点中的最大层次是这棵树的深度

表示

树的表示方法有多种，因需要表示其中的逻辑关系，一般会用链表实现，数组无法表示其中的逻辑关系。

儿子-兄弟表示法

利用两个指针来保存逻辑关系，即：FirstChild指针用来保存第一个孩子结点的地址，NextSibling指针用来保存下一个兄弟结点的地址。这样，每个结点需要 2 个指针域，一棵树共有 $n-1$ 条边，这样浪费的指针域个数为 $2n - (n-1) = n+1$。

二叉树表示法

二叉树简言之就是度为2的树，但相较度为 2 的树而言，二叉树的子树有左右之分。一般而言，所有能用儿子-兄弟表示法表示的树都可以用二叉树来表示，只需将儿子-兄弟表示法得到的树旋转 45° 即可得对应的二叉树。

二叉树

前面提到过了用二叉树来表示树，但实际上二叉树自身也具有十分独特的性质。

定义

二叉树T：一个有穷的结点集合。
这个集合可以为空（空二叉树），若不为空，则它是由根结点和称为其**左子树$T_L$和右子树$T_R$**的两个不相交的二叉树组成。
二叉树有五种基本形态：空树、单结点树、左子树为空的树、右子树为空的树和左右子树都不空的树。

注意：二叉树与普通度为2的树的区别在于，二叉树的子树有左右之分。

特殊二叉树（题目中也可能会出现）：

斜二叉树（Skewed Binary Tree）：只有左（右）子树，形状上呈现一边倒的样子，类似链表
完美二叉树（Perfect Binary Tree），也叫满二叉树（Full Binary Tree）：除了叶结点外，每一个结点都有两个儿子结点
完全二叉树（Complete Binary Tree）：有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号，编号为i（1≤i≤n）结点与满二叉树中编号为i结点在二叉树中位置相同。

性质

二叉树的几个重要性质：

一个二叉树第 i 层的最大结点数为：$2^{i-1}, i \ge 1$。
深度为 k 的二叉树有最大结点树为：$2^k-1, k \ge 1$。
对任何非空二叉树T，若$n_0$表示叶结点的个数、$n_2$是度为2的非叶结点个数，那么两者满足关系$n_0 = n_2 + 1$，这个结论可证明。

二叉树抽象数据类型描述

类型名称：二叉树
数据对象集：一个有穷的结点集合，若不为空，则由根结点和其左、右二叉子树组成。
操作集：BT ∈ BinTree，Item∈ ElementType，重要操作有：

Boolean IsEmpty(BinTree BT)，判别BT是否为空
void Traversal(BinTree BT)，遍历，按照某顺序访问每个结点
BinTree CreatBinTree()，创建一个二叉树。

常见的遍历方法有：

void PreOrderTraversal(BinTree BT)，先序遍历，根→左→右
void InOrderTraversal(BinTree BT)，中序遍历，左→根→右
void PostOrderTraversal(BinTree BT)，后序遍历，左→右→根
void LevelOrderTraversal(BinTree BT)，层次遍历，从上到下，从左到右

二叉树的顺序存储结构

二叉树顺序存储一般直接使用（结构）数组实现，而完全二叉树直接用一维数组即可实现，也易于操作。
对于使用数组表示的完全二叉树而言，可以通过结点的序号（数组的下标）中的规律来帮助反映结点之间的父子（逻辑）关系，具体如下：

非根结点（序号$i＞1$）的父结点的序号是$\lfloor i/2 \rfloor$
结点（序号为$i$）的左孩子结点的序号是$2i$，若$2i \geqslant n$，否则没有左孩子
结点（序号为$i$）的左孩子结点的序号是$2i+1$，若$2i+1 \geqslant n$，否则没有右孩子

一般结构的二叉树也可以采用这种结构，但是会造成空间的浪费，因为数组中也存储了空结点。

二叉树的链式存储结构

定义如下：

struct TNode{
	int data;
	struct TNode *left, *right;
};
typedef struct TNode* PtrToTNode;
typedef PtrToTNode Tree;

二叉树的遍历

二叉树的遍历既可以直接用递归的思想完成，也可以借助栈来构造非递归的遍历算法。尽管递归的缺点很明显，但好在易于理解，且形式简单，一般而言都是用递归来遍历二叉树。不过从学习的角度来讲，多探究一下没有任何坏处，所以下面的内容也给出非递归的算法。
注：下面的代码有部分是 C++ 的内容，但并没有特别难于理解地方。

先序遍历

遍历过程：访问根结点 → 先序遍历其左子树 → 先序遍历其右子树

void preorder(Tree root) {
	/* method 1: use recursion
	
	if(!root) return;
	cout << root->data << ' ';
	preorder(root->left);
	preorder(root->right);
	*/
	/* method 2: use loop and stack */
	stack<PtrToTNode> st;
	while(root || !st.empty()) {
		while(root) {
			st.push(root);
			cout << root->data << ' ';
			root = root->left;
		}
		if(!st.empty()) {
			root = st.top();
			st.pop();
			root = root->right;
		}
	} 
}

中序遍历

遍历过程：先序遍历其左子树 → 访问根结点 → 先序遍历其右子树

void inorder(Tree root) {
	/* method 1: use recursion
	
	if(!root) return;
	inorder(root->left);
	cout << root->data << ' ';
	inorder(root->right);
	*/
	/* method 2: use loop and stack */
	stack<PtrToTNode> st;
	while(root || !st.empty()) {
		while(root) {
			st.push(root);
			root = root->left;
		}
		if(!st.empty()) {
			root = st.top();
			st.pop();
			cout << root->data << ' ';
			root = root->right;
		}
	}
}

后序遍历

遍历过程：先序遍历其左子树 → 先序遍历其右子树 → 访问根结点
后序遍历的非递归算法其实有很多，这里举两个例子，分别使用了 2 个栈和 1 个栈来完成，使用双栈的思路较为直观一些，建议动手模拟一下。

void postorder(Tree root) {
	/* method 1: use recursion
	
	if(!root) return;
	postorder(root->left);
	postorder(root->right);
	cout << root->data << ' ';
	*/
	/* method 2: use loop and two stacks 
	
	stack<PtrToTNode> st1, st2;
	while(root || !st1.empty()) {
		while(root) {
			st1.push(root);
			st2.push(root);
			root = root->right;
		}
		if(!st1.empty()) {
			root = st1.top();
			st1.pop();
			root = root->left;
		}
	}
	while(!st2.empty()) {
		root = st2.top();
		st2.pop();
		cout << root->data << ' ';
	}
	*/
	/* method 3: use loop and one stack */
	stack<PtrToTNode> st;
	PtrToTNode pre = NULL, cur = NULL;
	st.push(root);
	while(!st.empty()) {
		cur = st.top();
		if(pre == NULL || pre->left == cur || pre->right == cur) {
			if(cur->left != NULL) st.push(cur->left);
			else if(cur->right != NULL) st.push(cur->right);
		} else if(cur->left == pre) {
			if(cur->right != NULL) {
				st.push(cur->right);
			} 
		} else {
			cout << cur->data << ' ';
			st.pop();
		}
		pre = cur;
	}
}

层序遍历

遍历过程：从第一层开始，从左往右依次访问每个结点。层序遍历一般用队列实现，也可以使用栈来实现。层序遍历一般采用迭代（循环）的思想来实现。

void levelorder(Tree root) {
	queue<PtrToTNode> q;
	q.push(root);
	while(!q.empty()) {
		PtrToTNode front = q.front();
		q.pop();
		cout << front->data << ' ';
		if(front->left) q.push(front->left);
		if(front->right) q.push(front->right);
	}
	cout << endl;
}

作业

03-1 树的同构

按照这道题目给定的数据形式，用静态链表的方式表示树，解起题来会比较方便（正如姥姥前面说过：合适的数据结构能够帮助我们解决问题），当然也可以动脑子想一想怎么用指针来解决。另外，在判断树是否同构时要注意问题考虑全面（读题仔细），理解递归的含义，“同构
其实并没有要求树的结构完全一致，只要求结点分布一致即可。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define maxn 15
struct TNode{
	char data;
	int left, right;
} T1[maxn], T2[maxn];
void init() {
	int i;
	for(i = 0; i < maxn; i++) {
		T1[i].left = T1[i].right = T2[i].left = T2[i].right = -1;
	}
}
int buildtree(struct TNode T[]) {
	int i, n;
	scanf("%d%*c", &n);
	char data, lc, rc;
	bool isRoot[maxn] = {false};
	for(i = 0; i < n; i++) {
		scanf("%c %c %c%*c", &data, &lc, &rc);
		T[i].data = data;
		if(lc != '-') {
			T[i].left = lc - '0';
			isRoot[lc - '0'] = true;
		}
		if(rc != '-') {
			T[i].right = rc - '0';
			isRoot[rc - '0'] = true;
		} 
	}
	int root = -1;
	for(i = 0; i < n; i++) {
		if(!isRoot[i]) {
			root = i;
			break;
		}
	}
	return root;
}
bool Isomorphic(int root1, int root2) {
	if(root1 == -1 && root2 == -1) return true;
	if((root1 == -1 && root2 != -1) || (root1 != -1 && root2 == -1)) return false;
	if(T1[root1].data != T2[root2].data) return false;
	if(T1[root1].left == -1 && T2[root2].left == -1) {
		return Isomorphic(T1[root1].right, T2[root2].left);
	}
	if((T1[root1].left != -1 && T2[root2].left != -1) && 
	(T1[T1[root1].left].data == T2[T2[root2].left].data)) {
		return Isomorphic(T1[root1].left, T2[root2].left) && 
				Isomorphic(T1[root1].right, T2[root2].right);
	} else return Isomorphic(T1[root1].left, T2[root2].right) && 
					Isomorphic(T1[root1].right, T2[root2].left);
}
int main() {
	init();
	int root1 = buildtree(T1);
	int root2 = buildtree(T2);
	if(Isomorphic(root1, root2)) printf("Yes");
	else printf("No");
	return 0;
}

/*
some samples:
in:
0
0
out: 
Yes

*/

03-2 List Leaves

题目要求找一棵树中的所有叶子结点（无孩子），顺序是从上到下，从左到右。如果要访问所有叶子结点，那么肯定少不了树的遍历。进而可以想到，题目要求的输出顺序与层序遍历的输出顺序是一致的。所以可以借助层序遍历的代码来构造输出叶子结点的算法。由于层序遍历需要用到队列，直接用 C++ 的 STL 内的 Queue。根据题目的形式，还是用静态链表的方法来表示树。

#include <iostream>
#include <queue>
using namespace std;
const int maxn = 20;
struct node{
	int left, right;
} Tree[maxn];
bool isRoot[20] = {false};
void init() {
	for(int i = 0; i < maxn; i++) {
		Tree[i].left = Tree[i].right = -1;
	}
}
void levelorder(int root) {
	queue<int> q;
	q.push(root);
	bool flag = true;
	while(!q.empty()) {
		int tmp = q.front();
		q.pop();
		if(Tree[tmp].left == -1 && Tree[tmp].right == -1) {
			if(flag) {
				cout << tmp;
				flag = false;
			} else {
				cout << ' ' << tmp;
			}
		} 
		if(Tree[tmp].left != -1) q.push(Tree[tmp].left);
		if(Tree[tmp].right != -1) q.push(Tree[tmp].right);
	}
}
int main() {
	init();
	int n;
	cin >> n;
	char c1, c2;
	for(int i = 0; i < n; ++i) {
		cin >> c1 >> c2;
		if(c1 != '-') {
			isRoot[c1 - '0'] = true;
			Tree[i].left = c1 - '0';
		}
		if(c2 != '-') {
			isRoot[c2 - '0'] = true;
			Tree[i].right = c2 - '0';
		}
	}
	int root;
	for(int i = 0; i < n; i++) {
		if(!isRoot[i]) {
			root = i;
			break;
		}
	}
	levelorder(root);
	return 0;
}

03-3 Tree Traversals Again

题目考察二叉树的先序、中序和后序遍历（一道题目考到了树的三种遍历方法）。

题目背景是二叉树中序遍历的非递归算法的入、出栈顺序，实际上，入栈顺序就是先序序列，出栈顺序就是中序序列。这样可以使用先序序列和中序序列构造树，进而在通过后序遍历来输出后序序列。那么如何表示树呢？由于本题给定的数据并没有给出树的具体结构，实际上用链式结构或者顺序结构的复杂度都是一样的。

不过此题也可以不用构造树，直接通过递归来得到后序序列。不过不是那么好理解，建议手动模拟一下，笔试中也有类似的题目，思路本质上是一样的。

/* method 1: Do not build a tree. use recursion */
#include <iostream>
#include <stack>
using namespace std;
const int maxn = 30 + 5; 
int in[maxn], pre[maxn], post[maxn], n;
void solve(int preL, int inL, int postL, int n) {
	if(n == 0) return;
	if(n == 1) {
		post[postL] = pre[preL];
		return;
	}
	int root = pre[preL], i;
	post[postL + n - 1] = root;
	for(i = 0; i < n; i++) {
		if(in[inL + i] == root) break;
	}
	int L = i, R = n - L - 1;
	solve(preL + 1, inL, postL, L);
	solve(preL + L + 1, inL + L + 1, postL + L, R);
}
int main() {
	string ope;
	int node, cnt1 = 0, cnt2 = 0;
	cin >> n;
	stack<int> st;
	for(int i = 0; i < 2 * n; i++) {
		cin >> ope;
		if(ope == "Push") {
			cin >> node;
			pre[cnt1++] = node;
			st.push(node);
		} else if(ope == "Pop") {
			in[cnt2++] = st.top();
			st.pop();
		}
	}
	solve(0, 0, 0, n);
	for(int i = 0; i < n; i++) {
		cout << post[i];
		if(i != n - 1) putchar(' ');
	}
	return 0;
}

/* method 2: use static tree 
 
#include <iostream>
#include <string>
#include <stack>
using namespace std;
const int maxn = 30 + 5;
struct node{
	int left, right;
	int data;
} Tree[maxn];
int in[maxn], pre[maxn], n;
void init() {
	for(int i = 0; i < maxn; i++) {
		Tree[i].left = Tree[i].right = -1;
	}
}
int buildtree(int preL, int preR, int inL, int inR) {
	if(preL > preR) return -1;
	Tree[preL].data = pre[preL];
	int k;
	for(k = inL; k <= inR; k++) {
		if(in[k] == pre[preL]) break;
	}
	int numLeft = k - inL;
	Tree[preL].left = buildtree(preL + 1, preL + numLeft, inL, k - 1);
	Tree[preL].right = buildtree(preL + numLeft + 1, preR, k + 1, inR);
	return preL;
}
int num = 0;
void postorder(int root) {
	if(root == -1) return;
	postorder(Tree[root].left);
	postorder(Tree[root].right);
	cout << Tree[root].data;
	if(num < n - 1) cout << ' ';
	num++;
}
int main() {
	init();
	string ope;
	int node, cnt1 = 0, cnt2 = 0;
	cin >> n;
	stack<int> st;
	for(int i = 0; i < 2 * n; i++) {
		cin >> ope;
		if(ope == "Push") {
			cin >> node;
			pre[cnt1++] = node;
			st.push(node);
		} else if(ope == "Pop") {
			in[cnt2++] = st.top();
			st.pop();
		}
	}
	buildtree(0, n - 1, 0, n - 1);
	postorder(0);
	return 0;
}

*/

bachzart's Blog

ZJU_DS_03-树（上）

引言

查找