java实现常见查找算法(5)

public class SearchBST {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = { 62, 88, 58, 47, 35, 73, 51, 99, 37, 93 };
		for (int i = 0; i < a.length; i++) {
			generateBST(a[i]);
			System.out.println();
		}
	}
	
	static BinTree newTree = new BinTree();
	/** 全局变量 存放查找到的关键字所在的父节点 */
	static BinTree parentNode = new BinTree();
	/**
	 * 二叉排序树
	 * 
	 * @param bt
	 *            待查询二叉排序树
	 * @param key
	 *            查找关键字
	 * @param parent
	 *            指向bt的双亲，其初始调用值为null
	 * @return 查找关键字key成功 返回true，并把树结点赋值给全局变量result，查找失败，返回false
	 */
	public static boolean searchBST(BinTree bt, int key, BinTree parent) {
		if (null == bt || 0 == bt.data) {// 树节点不存在，返回
			parentNode = parent;
			return false;
		} else if (key == bt.data) {// 查找成功
			parentNode = bt;
			return true;
		} else if (key < bt.data) {// 关键字小于根节点则查找左子树
			return searchBST(bt.lchild, key, bt);
		} else// 关键字大于根节点则查找右子树
			return searchBST(bt.rchild, key, bt);
	}
	/** 生成二叉排序树 */
	public static boolean generateBST(int key) {
		if (!searchBST(newTree, key, null)) {
			BinTree s = new BinTree();
			s.data = key;
			s.lchild = s.rchild = null;
			if (null == parentNode)// 不存在，则表明是父节点，将s指向bt成为新的根节点
				newTree = s;
			else if (key < parentNode.data)
				parentNode.lchild = s;// 当key小于子根结点，则插入为左孩子
			else
				parentNode.rchild = s;// 当key大于子根结点，则插入为右孩子
			preOrderTraverse(newTree);
			return true;
		} else
			System.out.println("该节点已存在!");
		return false;
	}
	/** 中序遍历打印线索二叉树 */
	static void preOrderTraverse(BinTree t) {
		if (null == t || 0 == t.data)
			return;
		if (null != t.lchild)
			preOrderTraverse(t.lchild);/* 接着中序遍历左子树 */
		if (0 != t.data)
			System.out.print("[" + t.data + "]");/* 显示当前结点数据 */
		if (null != t.rchild)
			preOrderTraverse(t.rchild);/* 最后遍历右子树 */
	}
	/**
	 * 二叉树 数据结构
	 */
	private static class BinTree {
		int data;
		BinTree lchild;
		BinTree rchild;
	}
}

8 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，ll, lr, rr, rl 旋转, 插入算法，时间复杂性分析，b树，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理，开放寻址，链接。(2) 线性表adt顺序存储实现中的创建、查找、插入和删除等基本操作及相关算法，线性表adt链式存储实现中单链表、循环链表和双向链表的创建、查找、插入和删除等基本操作及相关算法。常见的综合应用题考点包括：二叉树的遍历算法，遍历基础上针对二叉树的一些统计和操作(比如结点数统计、左右子树对换等等)，判断某棵二叉树是否二叉排序树，以上这些都要求能用递归的和非递归的算法解决，特别要重视非递归的算法，线索化后二叉树的遍历算法，如查找某结点线索化后的前驱或后继结点的算法以及给出huffman编码等等。

如果需要查找并删除如37、51、73、93这些在二叉排序树中是叶子的结点，那是很容易的，毕竟删除它们对整棵树来说，其他结点的结构并未受到影响，如图所示 。

对于要删除的结点只有左子树或只有右子树的情况，相对也比较好解决。那就是结点删除后，将它的左子树或右子树整个移动到删除结点的位置即可，可以理解为独子继承父业。比如下图所示，就是先删除35和99结点，再删除58结点的变化图，最终，整个结构还是一个二叉排序树。

供选择的答案： a：①是特殊的树②不是树的特殊形式③是两棵树的总称④是只有二个根结点的树形结构 b：①左子结点②右子结点③左子结点或者没有右子结点 ④兄弟 c～d： ①最左子结点②最右子结点③最邻近的右兄弟④最邻近的左兄弟⑤最左的兄弟⑥最右的兄弟e：①o(n)②o(n)③o(log2n)④o(log2n) 15、每一棵树都能唯一地转换为它所对应的二叉树，树的这种二叉树表示对树的运算带来很大的好是 n在原树里对应结点的__a__,而 n 的右子女是原树里对应结点的__b__。

起初的想法，我们当47结点只有一个左子树，那么做法和一个左子树的操作一样，让35及它之下的结点成为58的左子树，然后再对47的右子树所有结点进行插人操作，如下图所示。 这是比较简单的想法，可是47的右子树有子孙共5个结点，这么做效率不高且不说， 还会导致整个二叉排序树结构发生很大的变化，有可能会增加树的高度。增加高度可不是个好事，这我们待会再说，总之这个想法不太好。

删除结点可以通过结点的序号确定要删除的结点，当然也可以通过结点的关键字确定要删除的结点。去线，对树中的每个结点，只保留它与第一个孩子结点的连线，删除与其他孩子结点之间的连线。选中分组树中的通道结点，点击设备配置窗口配置按钮栏的“删除”按钮将选中的通道从分组中删除。

为什么是37和48? 对的，它们正好是二叉排序树中比它小或比它大的最接近47的两个数。也就是说，如果我们对这棵二叉排序树进行中序遍历，得到的序列{29，35，36，37，47，48，49，50，51，56，58，62，73，88，93.99}，它们正好是47的前驱和后继。

如图4.3所示： 图4.3 结点在链表中间插入1操作继续进行，将结点62的后继指针指向结点91，同时去掉它的结点91到46的前驱指针。为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点，如图2-8所示。此外，双链表可以很方便地找到其前驱结点，因此，插入、删除结点算法的时间复杂度仅为o(1)。

根据我们对删除结点三种情况的分析:

• 叶子结点;

• 仅有左或右子树的结点 :

8 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，ll, lr, rr, rl 旋转, 插入算法，时间复杂性分析，b树，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理，开放寻址，链接。定义函数node *del(node *h, int i)，用于删除单链表h中第i个结点，定义两个指针*p，*q，用指针p来从第一个结点开始查找需要删除的结点，指针q是指针p的前驱，查找过程中，不断移动指针p，q，直至找到需要删除的结点，如果*p为空指针，则表示链表中没有需要删除的结点，最后返回头指针。但是，在实验中也遇到了很多问题，例如在写插入、删除操作的代码的时候，虽然看书时已经看懂来插入删除等操作的算法，但是结点之间断链再重连到新结点的操作写不出来，后来看了书上的代码，琢磨了很久才慢慢理解。

public static boolean deleteBST(BinTree bt, int key) {
	if (!searchBST(bt, key, null)) { // 不存在关键字等于key的元素
		return false;
	} else {
		if (bt.data == key) {
			return delete(bt);
		} else if (key < bt.data) {
			return deleteBST(bt.lchild, key);
		} else {
			return deleteBST(bt.rchild, key);
		}
	}
}

以上代码实现了单链表的创建，但是链表的常用操作还有查找、插入、删除等没有讲解，删除操作与插入操作类似，就不在这里一一讲解了，在此我们以查找和插入为例进行讲解，但是读者在编写删除操作的时候别忘了把删除的结点释放掉。8 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，ll, lr, rr, rl 旋转, 插入算法，时间复杂性分析，b树，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理，开放寻址，链接。第8章 查找结构：符号表，二叉查找树，二叉查找树的查找、插入和删除操作，avl树，高度平衡，avl树的插入算法，avl树的时间复杂性分析，m叉查找树，m叉查找树的查找，b树的定义和性质，b树的插入操作，b树的删除操作，静态散列，散列表，散列函数，溢出处理。

/** 从二叉排序树中删除结点p，并重接它的左或右子树 */
public static boolean delete(BinTree bt) {
	BinTree q, s;
	if (null == bt.rchild) {
		bt = bt.lchild; // 右子树为空则只需重接左子树
	} else if (null == bt.lchild) {
		bt = bt.rchild; //// 左子树为空则只需重接右子树
	} else {
		q = bt;
		s = bt.lchild;
		while (null != s.rchild) {// 转左，然后向右到尽头(找到待删结点前驱)
			q = s;
			s = s.rchild;
		}
		bt.data = s.data;// s指向被删除结点的直接前驱
		if (q != bt) {//
			q.rchild = s.lchild;// 重接q的右子树
		} else {// q.data == bt.data，则说明s.rchild == null
			q.lchild = s.lchild; // 重接q的左子树
		}
	}
	return true;
}

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