rambo

二叉搜索树(一)递归方式

树是一种非常有用的数据结构。几乎所有的编译器都需要实现一个表达式树(expression tree);文件压缩所用的哈夫曼算法(Huffman's algorithm)需要用到树状结构;数据库所用的B-Tree则是一种相当复杂的树状结构。

QQ截图20150806171302

二叉树:

任何节点最多只允许有两个子节点。如果以递归方式来定义二叉树,则可以说“一个二叉树如果不为空,便是由一个根节点和左右两个子树构成;左右子树都可能为空”。

二叉搜索树:

可提供对数时间的元素插入和访问。二叉搜索树的结点放置规则是:任何节点的键值一定大于其左子树中的每一个节点的键值,并小于其右子树中的每一个节点的键值。这个性质非常有用,因为从根节点一直往左走,直至叶节点,即得最小元素;从根节点一直往右走,直至叶节点,即得最大元素;

QQ截图20150806230753

 

二叉搜索树允许我们通过一个简单的递归算法来按序输出二叉所所述的所有关键字。

  • 中序遍历(inorder tree walk)。输出的子树根的关键字位于其左子树的关键字值和右子树的关键字值间。
  • 先序遍历(preorder tree walk)。输出的根的关键字在其左右子树的关键字值之前。
  • 后序遍历(postorder tree walk)。输出的根的关键字在其左右子树的关键字值之后。

28194749-e5484b8b65c5413b99ec931a44b51ae1

遍历一棵有n个节点的二叉搜索树需要耗费\Theta(n)的时间。因为初次调用之后,对于树中的每个结点这个过程恰好要自己调用两次:一次是它的左孩子,另一次是它的右孩子。

时间复杂度:

二叉搜索树的基本操作所花费的时间与这棵树的高度成正比。最坏情况下,如果这棵树是一条n个结点组成的线性链,那么需要花费\Theta(n)的运行时间。一棵随机构造的二叉搜索树的期望高度为O(lgn)平均运行时间为\Theta(lgn)

递归方式二叉搜索树操作

采用递归方式来进行插入、中序遍历等。递归的应用和函数调用栈紧密联系,我们需要清除的知道每一步递归,其入口地址的保存。

中序遍历结果:

QQ截图20150815214936

我们可以从汇编源码看到  引用参数在每一次递归时保存到一个栈中,然后顺序出栈。

先序遍历和后序遍历的递归版本

递归查找

递归地建立二叉搜索树,特别声明,只有这种数据结构才可以比较容易的建立,只有BinaryTree。而不是把它分成如下形式,这样实际实现时非常麻烦。我们会在下面看到这种方式适用于非递归迭代地建立二叉树。

 

非递归方式建立二叉树

 

 

有根树的表示

用域p、left、right来存放指向二叉树T中的父亲、左儿子、右儿子。如果x.p=NULL,则x是根节点。属性T.root指向整棵树T的根结点。如果T.root=NULL,则该树为空树。

 

QQ截图20150814165735

 

相关问题:

12.1-2 二叉搜索树性质与最小堆性质有什么不同?能使用最小堆性质在O(n)时间内按序输出一个有n个结点树的关键字吗?

二叉搜索树:左子树关键字<根结点关键字<右子树关键字

最小堆:除了根节点以外的所有结点i都要满足:A[PARENT(i)]<=A[i]。(堆中的最小元素存放在根节点中)。

不能。原因是含有n个结点的最小堆的结点key大小是根<左<右或者根<右<左,左右子树是无序的。导致结果就是不能按照树的前中后序遍历在O(n)时间内来有序的输出他们。而二叉搜索树,按照中序遍历,正好是左<根<右,他们是有序的。