平衡二叉树 AVL AVL 树是一棵空树或它的左右两个子树的高度差的绝对值不超过 1,并且左右两个子树都是一棵平衡二叉树。同时,AVL 树也是一棵二叉搜索树。 (a)普通二叉搜索树 (b)平衡二叉树 AVL 树可以在 O(logN) 时间复杂度内执行所有搜索、插入和删除操作。 代码实现 /** * 平衡二叉树 */ public class AVLTree<K extends Comparable<K>, V> { private class Node { public K key; pub…

2018年10月18日 0条评论 4点热度 阅读全文

二叉树的重建 二叉树的重建方法: 一、根据前序加中序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据前序序列的第一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在前序序列中确定左右子树的前序序列; 4. 由左子树的前序序列和中序序列建立左子树; 5. 由右子树的前序序列和中序序列建立右子树。 二、根据中序加后序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据后序序列的最后一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在…

2017年10月14日 0条评论 15点热度 阅读全文

二叉树的重建 二叉树的重建方法: 一、根据前序加中序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据前序序列的第一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在前序序列中确定左右子树的前序序列; 4. 由左子树的前序序列和中序序列建立左子树; 5. 由右子树的前序序列和中序序列建立右子树。 二、根据中序加后序遍历重建二叉树 构造该二叉树的过程如下: 1. 根据后序序列的最后一个元素建立根结点; 2. 在中序序列中找到该元素,确定根结点的左右子树的中序序列; 3. 在…

2017年10月14日 0条评论 43点热度 阅读全文

二叉排序树的插入、查找、删除 二叉排序树的定义 二叉排序树右称二叉查找树。或者为空树,或者是具有以下性质: (1)若它的左子树不为空,则左子树所有节点的值小于根结点, (2)若它的右子树不为空,则根结点的值小于所有右子树结点的值 (3)它的左右子树叶分别为二叉排序树   总结起来就是根据结点的值有:左子树<根结点<右子树 如下图就是一棵二叉排序树     它的中序遍历:12、19、23、28、34、36、38、42、53、65、90,刚好是排好序的。   二叉排序…

2017年7月17日 0条评论 22点热度 阅读全文

二叉排序树的插入、查找、删除 二叉排序树的定义 二叉排序树右称二叉查找树。或者为空树,或者是具有以下性质: (1)若它的左子树不为空,则左子树所有节点的值小于根结点, (2)若它的右子树不为空,则根结点的值小于所有右子树结点的值 (3)它的左右子树叶分别为二叉排序树   总结起来就是根据结点的值有:左子树<根结点<右子树 如下图就是一棵二叉排序树     它的中序遍历:12、19、23、28、34、36、38、42、53、65、90,刚好是排好序的。   二叉排序…

2017年7月17日 0条评论 9点热度 阅读全文

C++实现图的构建和遍历操作: 1:图的定义 2:图的初始化 3:BFS遍历 4:DFS遍历 graph.h #ifndef DS_GRAPH_GRAPH_H #define DS_GRAPH_GRAPH_H #include <iostream> using std::cin; using std::cout; using std::endl; #define E 4 //图的边数 #define N 4//图的顶点数 typedef char vextype; //顶点的数据类型 typedef f…

2017年5月29日 0条评论 3点热度 阅读全文

基本思想 1、从图中某个顶点V0出发,并访问此顶点; 2、从V0出发,访问V0的各个未曾访问的邻接点W1,W2,…,Wk;然后,依次从W1,W2,…,Wk出发访问各自未被访问的邻接点; 3、重复步骤2,直到全部顶点都被访问为止。 类似于树的按层次遍历,也就是一层一层地遍历,图的广度优先遍历从图中的某个结点出发,访问它的邻结点再访问邻结点的邻结点,由近及远。 如上图:从A出发,依次访问A结点的邻接点B、C、D,再访问B的邻接E,再访问C的邻接点F,左边访问完后,访问右边D的邻结点G和H,再访问G的邻接点 I, 至此所…

2016年12月20日 0条评论 2点热度 阅读全文

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 比如下面这棵树就是一棵完全二叉树 通过图片我们可以了解到它的创建过程是从上到下,从左至右的,也就是说,它是一层一层建立的。 完全二叉树有以下基本性质: 对于一棵有n个结点的完全二叉树,其任意结点 i (1<=i<=n),如果 i = 1, 则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2. 如果 …

2016年11月5日 0条评论 17点热度 阅读全文

完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 比如下面这棵树就是一棵完全二叉树 通过图片我们可以了解到它的创建过程是从上到下,从左至右的,也就是说,它是一层一层建立的。 完全二叉树有以下基本性质: 对于一棵有n个结点的完全二叉树,其任意结点 i (1<=i<=n),如果 i = 1, 则结点 i 是二叉树的根,无双亲; 如果 i>1,则其双亲parent(i)是结点 i/2. 如果 …

2016年11月5日 0条评论 29点热度 阅读全文

整合自: http://blog.csdn.net/shuangde800/article/details/7341289 http://www.cnblogs.com/Jezze/archive/2011/12/23/2299884.html http://blog.csdn.net/jdhanhua/article/details/6621026 B树介绍:点击打开链接 tire树:点击打开链接    点击打开链接          …

2016年7月24日 0条评论 3点热度 阅读全文