线索二叉树、二叉排序树
1，什么是线索二叉树？
2，为什么要建立线索二叉树？
3，如何将二叉树线索化？
4，线索二叉树的常见操作及实现思路？
一 、什么是线索二叉树
在有n个结点的二叉链表中必定存在n+1个空指针域，因此可以利用这些空指针域存放指向结点的某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树被称为线索二叉树。
二、为什么要建立线索二叉树
有了二叉树不就足够了吗？那为什么还要弄个线索二叉树出来呢？
在原来的二叉链表中，查找结点的左，右孩子可以直接实现，可是如果要找该结点的前趋和后继结点呢？这就变得非常困难，所以为了实现这个常见的需求，我们要在每个结点中增加两个指针域来存放遍历时得到的前趋和后继结点，这样就可以通过该指针直接或间接访问其前趋和后继结点。
三，如何将二叉树线索化
按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。
下面是线索二叉树和线索二叉链表示意图，它可以帮助我们更好地理解线索二叉树。
四，线索二叉树的常见操作及实现思路
1，二叉树线索化
实现思路：按某种次序遍历二叉树，在遍历过程中用线索取代空指针即可。
a). 若上次访问到的结点的右指针为空，则将当前访问到的结点地址填入，并置右标志域为 1
b). 若当前访问到的结点的左指针为空，则将上次访问到的结点地址填入，并置左标志域为 1
2，查找后继节点
实现思路：分两种情况，一，没有右孩子，直接获取。二，有右孩子，中序遍历查找右子树中序遍历的第一个节点即为当前节点的后继节点。
3，查找前驱节点
实现思路：同样也分两种情况，一，没有左孩子，依据线索直接获取。二，有左孩子，中序遍历左子树中往右链中第一个没有右孩子的节点即为前驱节点(左子树中序遍历的最后一个节点)
4，遍历
实现思路：以中序遍历为例，首先找到中序遍历的开始节点，然后利用线索依次查找后继节点即可。
1. 二叉排序树定义
二叉排序树(Binary Search Tree)是一种动态树表。 二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：
⑴ 若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
⑵ 若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
⑶ 左、右子树本身又各是一棵二叉排序树。二叉排序树的性质： 按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。
2. 二叉排序树的插入
在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。
插入过程：
- 若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；
- 当非空时，将待插结点关键字S->key和树根关键字t->key进行比较：
若s->key = t->key,则无须插入，若s->key< t->key,则插入到根的左子树中，
若s->key> t->key,则插入到根的右子树中。
而子树中的插入过程和在树中的插入过程相同，
如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。(待插入的节点，从根节点开始，依次与现有节点比较)。