1. 预备知识
- 一棵树是 \(N\) 个节点和 \(N-1\) 条边的集合，因为除了根（root）节点外，其余节点都有唯一一条边指向其父（parent）节点
- 没有儿子的节点称为叶（leaf）节点；具有相同父节点的节点称为兄弟（sibling）节点
- 对任意节点 \(n_i\)，\(n_i\) 的深度（depth）为从根节点到 \(n_i\) 的唯一路径的长度；故根的深度为 0
- 对任意节点 \(n_i\)，\(n_i\) 的高（height）是从 \(n_i\) 到一片树叶的最长路径的长度；故叶的高度为0；一棵树的高等于它的根的高
1.1 树的实现
typedef struct TreeNode* PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FristChild;
PtrToNode NextSibling;
}
此种方法存的是指向兄弟节点和子节点的链表而非指针，节省了空间（因每个节点的子节点数目并不一致）。
1.2 树的遍历及应用
流行的用法之一就是包括 UNIX，VAX/VMS 和 DOS 在内的许多常用操作系统中的目录结构。（严格来讲，UNIX 文件系统还存在指向该目录本身和指向该目录父目录的项，故为类树 treelike）。
- 前序遍历：根结点 \(\longrightarrow\) 左子树 \(\longrightarrow\) 右子树
- 中序遍历：左子树 \(\longrightarrow\) 根结点 \(\longrightarrow\) 右子树
- 后序遍历：左子树 \(\longrightarrow\) 右子树 \(\longrightarrow\) 根结点
- 层次遍历：只需按层次遍历即可
- 前序遍历：1 2 4 5 7 8 3 6
- 中序遍历：4 2 7 5 8 1 3 6
- 后序遍历：4 7 8 5 2 6 3 1
- 层次遍历：1 2 3 4 5 6 7 8
2. 二叉树（binary tree）
二叉树的一个性质是平均二叉树的深度要比 \(N\) 小得多。分析表明，这个平均深度为 \(O(\sqrt N)\)；而对于特殊类型的二叉树，即二叉查找树（binary search tree），其深度的平均值为 \(O(\log N)\)；不幸的是，二叉树的最大深度可以达到 \(N-1\)。
2.1 实现
typedef struct TreeNode* PtrToNode;
typedef struct PtrToNode Tree;
struct TreeNode
{
ElementType Element;
Tree Left;
Tree Right;
}
类似双链表的声明。
2.2 表达式树（expression tree）
树叶为操作数，其他节点为操作符。
2.3 二叉树的遍历
2.3.1 前序遍历
前序遍历：根结点 \(\longrightarrow\) 左子树 \(\longrightarrow\) 右子树。
递归实现
void PreOrder(TreeNode *root)
{
if (root == NULL) return;
cout << root->val;
PreOrder(root->left);
PreOrder(root->right);
}
非递归实现
对于任一结点 \(P\)：
1) 访问结点 \(P\)，并将结点 \(P\) 入栈
2) 判断结点 \(P\) 的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点 \(P\)，循环至 1)；若不为空，则将 \(P\) 的左孩子置为当前的结点 \(P\)
3) 直到 \(P\) 为 NULL 并且栈为空，则遍历结束
void PreOrderDev(TreeNode *root)
{
if (root == NULL) return;
// 保存节点
stack<TreeNode *> nstack;
// 备份根节点
TreeNode *node = root;
// 开始遍历整个二叉树
while (node != NULL || nstack.empty() != true) {
// 输出当前子树的根节点，然后递归直至最左
while (node != NULL) {
cout << node->val;
nstack.push(node);
node = node->left;
}
// 此时循环结束时，当前栈顶节点已经是最左节点
// 此时递归开始返回，开始出栈，并输出节点的右节点
if (nstack.empty() != true) {
node = nstack.top();
nstack.pop();
node = node->right;
}
}
}
2.3.2 中序遍历
中序遍历：左子树 \(\longrightarrow\) 根结点 \(\longrightarrow\) 右子树
递归实现
void InOrder(TreeNode *root)
{
if (root == NULL) return;
InOrder(root->left);
cout <<root->val;
InOrder(root->right);
}
非递归实现
对于任一结点 \(P\)：
1) 若其左孩子不为空，则将 \(P\) 入栈并将 \(P\) 的左孩子置为当前的 \(P\)，然后对当前结点 \(P\) 再进行相同的处理
2) 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的 \(P\) 置为栈顶结点的右孩子
3) 直到 \(P\) 为 NULL 并且栈为空则遍历结束
void InOrderDev(TreeNode *root)
{
if (root == NULL) return;
// 保存节点
stack<TreeNode *> nstack;
// 备份根节点
TreeNode *node = root;
// 开始遍历整个二叉树
while (node != NULL || nstack.empty() != true) {
// 不输出当前根节点，但是递归直至当前根节点 node 的最左端
while (node != NULL) {
nstack.push(node);
node = node->left;
}
// 此时栈顶的元素是当前最左元素
// 它应该被输出
if (nstack.empty() != true) {
node = nstack.top();
cout << node->val;
nstack.pop();
node = node->right;
}
}
}
2.3.3 后序遍历
后序遍历：左子树 \(\longrightarrow\) 右子树 \(\longrightarrow\) 根结点
递归实现
void PostOrder(TreeNode *root)
{
if (root == NULL) return;
PostOrder(root->left);
PostOrder(root->right);
cout << root->val;
}
非递归实现
后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点，这就为流程的控制带来了难题。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点 \(P\)，先将其入栈。如果 \(P\) 不存在左孩子和右孩子，则可以直接访问它；或者 \(P\) 存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将 \(P\) 的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
void PostOrderDev(TreeNode *root)
{
if (root == NULL) return;
stack<TreeNode *> nstack;
TreeNode *cur; //当前结点
TreeNode *pre = NULL; //前一次访问的结点
nstack.push(root);
while (nstack.empty() != true) {
cur = nstack.top();
if ((cur->left == NULL && cur->right == NULL)
// 左右还是均为 NULL, 可以被输出
|| (pre != NULL && ((pre == cur->left || pre == cur->right)))
// 左右还是被输出了, 递归返回
// 其实当前节点要是想被输出, 要么
// 1--其左右孩子均为 NULL
// 2--其左孩子刚被输出，而其右孩子为 NULL
// 3--其右孩子刚被输出
//
// 但是这里有一个优化，入栈时候，先是根入栈，然后是右孩子，然后是左孩子，因此当跟元素位于栈顶的时候，其左右孩子必然已经弹出，即被输出，也就是说, 即后序遍历中当前栈顶元素要是想被输出
// 1--其左右孩子均为 NULL
// 2--其孩子（不论左右）刚被输出即可
{
cout << cur->val; //如果当前结点没有孩子结点或者孩子节点都已被访问过
nstack.pop();
pre = cur;
}
else
{
// 由于栈是先进后出，因此先入右孩子, 再左孩子可以保证递归返回时先遍历左孩子
if (cur->right != NULL)
{
nstack.push(cur->right);
}
if (cur->left != NULL)
{
nstack.push(cur->left);
}
}
}
}
2.3.4 层次遍历
双指针法
void TreeNode::LevelOrderUsePoint(TreeNode *root)
{
vector<TreeNode*> vec;
vec.push_back(root);
int cur = 0;
int end = 1;
while (cur < vec.size())
{
end = vec.size(); /// 新的一行访问开始，重新定位last于当前行最后一个节点的下一个位置
while (cur < end)
{
cout << vec[cur]->val; /// 访问节点
if (vec[cur]->left != NULL) /// 压入左节点
{
vec.push_back(vec[cur]->left);
}
if (vec[cur]->right != NULL) /// 压入右节点
{
vec.push_back(vec[cur]->right);
}
cur++;
}
cout << endl;
}
}
3. 查找树 ADT——二叉查找树
使二叉树成为二叉查找树的关键性质是：对于树中每个节点 \(X\)，它的左子树中所有关键字值小于 \(X\) 的关键字值，而它的右子树中所有关键字值大于 \(X\) 的关键字值。