算法简介

搜索树数据结构支持许多动态收集操作，例如搜索（搜索）二叉排序树查找算法，最小值（最小元素），最大值（最大元素），前任（前任），后继（后继），插入（插入），删除（删除），这些是基本操作，您可以将搜索树用作字典或优先级队列.

12.1什么是二叉搜索树

二进制搜索树由二进制树组织，可以用链表数据结构表示，也称为二进制排序树和二进制搜索树；

每个节点都是一个对象，每个对象都包含多个属性（键: 节点的值，卫星数据: 不清楚，左: 左子节点，右: 右子节点，p: 父对象，看似单亲）.

如节点和父节点不存在，则对应的属性值为NULL；

根节点是树中唯一其父指针为NULL的节点.

二进制搜索树的性质:

让x为二叉搜索树中的一个节点，如果y为x左子树中的一个节点，则y.key <= x.key;如果y是x Point右子树中的一个节点，则y.key> = x.key;

通常来说，二叉搜索树中任何节点的子节点的值都不大于该节点，右子节点的值不小于修改后的节点.

二进制搜索树的关键字是根据二进制搜索树的性质存储的，即，只要数字是二进制搜索树，就必须满足上述属性.

不同的二进制搜索树可以代表相同的一组值.

二叉搜索树的性质使我们能够根据子树根的关键字，通过简单的递归算法（遍历时，从根节点开始）按顺序输出二叉搜索树中的所有关键字. 递归时，与left和right子树关键字的输出顺序不同，有三种便捷的方法:

如果递归遍历期间子树根输出的键位于其左子树的键与右子树的键之间，则称为中间顺序遍历.

如果递归遍历期间子树根输出的键位于其左子树的键和右子树的键之前，则称为前序遍历.

如果递归遍历期间子树根输出的键位于其左子树的键和右子树的键的后面，则称为后顺序遍历.

依次遍历的简单递归过程是:

middleOrder（x）{

如果（x！= null）

middleOrder（x.left）;

打印x.key;

middleOrder（x.right）;

}

预遍历的简单递归过程是:

preOrder（x）{

如果（x！= null）

打印x.key;

preOrder（x.left）;

preOrder（x.right）;

}

依次遍历的简单递归过程是:

afterOrder（x）{

如果（x！= null）

afterOrder（x.left）;

afterOrder（x.right）;

打印x.key;

}

示例如下:

中阶遍历分析:

1. 根据中间顺序递归的执行过程二叉排序树查找算法，可以判断输出从左下角2,5（左子代6的关键字，在这种情况下为子树的根）开始5，这三个数字分别是左子节点，子树根节点，右子节点，根据遍历定义的中间顺序，输出顺序为2、5（子树根），5（右子节点）

2、5、6、7相似，输出5、6、7

3，7（没有左子），直接输出7，8

最终结果是: 2、5（六个左孩子的关键字），5（六个左孩子的关键字），6、7、8

顺序遍历的方法是: 根据顺序递归的过程，先输出子树的根节点，然后递归遍历左右子树的节点. 结果为: 6、5（6个左孩子），2、5（6个左孩子的右边孩子），7、8

后序遍历方法是: 根据后序递归过程，先输出子树根的左右节点，再输出子树根节点. 结果是: 2、5（6的左孩子是右孩子），5、5（6的左孩子），8、7、6

要点: 想象一下递归程序的执行过程来判断输出结果.

定理: 如果x是具有n个节点的子树的根，则调用middleOrder（x）需要Θ（n）时间. 同样，preOrder和afterOrder也是Θ（n）时间.

定理分析: 要证明递归算法需要Θ（n）时间，则需要证明Ω（n）<= T（n）<=Ο（n）

假设遍历单个节点的时间是恒定的，因为它需要遍历n个节点，因此T（n）> =Ω（n），即时间至少为n的线性函数是必需的，并且省略了系数和常数项. 简单来说，它表示所需时间的下限.

T（n）<=Ο（n）被证明省略.

锻炼:

12.1-1对于关键字集{1、4、5、10、16、17、21}，绘制一个高度分别为2、3、4、5、6的二叉搜索树.

分析: 如下所示:

2. 待续，

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-167965-1.html