二叉搜索树

原文地址

三叉搜索树是用来解决字典树的内存问题的数据结构。为了避免不需要的节点的内存占用，每个字典树节点不再使用数组，而是使用“树中有树”的结构。在三叉搜索树中，字典树节点的每个非空指针得到它自己。

例如，有四个单词，AB、ABBA、ABCD和BCD，它的三叉搜索树结构如下： 

三叉搜索树包括三种箭头。第一种，向下的虚线箭头。遍历这种箭头，就能得到相匹配的单词。第二种，左右箭头。当当前位置字符不满足需要时，遍历这种箭头。当当前位置字符小于需求时，遍历右箭头；反之，左箭头。

例如， 
绿色箭头展示了如何确认三叉搜索树是否包含单词ABBA： 

下面这幅图展示如何发现三叉搜索树不包含单词ABD： 

二叉搜索树

原文：http://www.cnblogs.com/studyhs/p/6290302.html