12.1 二叉查找树 定义:设x为二叉查找树中的一个结点。如果y是x的左子树中的一个结点,则key[y]≤key[x]。如果y是x的右子树中的一个结点,则key[x]≤key[y]. 前序遍历:先遍历根再遍历左右子树,简称根-左-右。 中序遍历:先遍历左子树再遍历根再遍历右子树,简称左-根-右。 后序遍历:先遍历左右子树再遍历根,简称左-右-根。 书中中序遍历代码: //中序遍历 void INORDER-TREE-WALK(struct Tree *p) { if (p->key) { INORDER-TR…

2014年6月6日 0条评论 9点热度 阅读全文

二叉查找树是一种应用十分广泛的数据结构,它在算法中应用十分广泛,二叉查找树支持多种动态集合的操作,这些操作主要包括: 1、查找某个特定值: 2、二叉查找树中最小值: 3、二叉查找树中最大值: 4、某个节点的前驱: 5、某个节点的后继: 6、插入特定值: 7、删除特定值: 一般情况下,我们为了保持查找和删除情况的唯一性,假设二叉查找树中各个元素的key值不想等。 下面一一剖析二叉查找树的结构与方法: 1、二叉查找树的数据结构: // 构造二叉查找数的内部类,这就相当于C语言中的结构体 private class Tr…

2014年4月2日 0条评论 6点热度 阅读全文