平衡二叉树介绍 平衡二叉树,是一种二叉排序树,其中每一个节点的左子树和右子树的高度差最多等于1。由3位科学家共同发明,用他们首字母命名 又被称为AVL树。从平衡二叉树的名称,你也可以体会到它是一种高度平衡的二叉排序树。我们将二叉树上结点的左子树深度减去右子树的深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只能是-1,0,1。 平衡二叉树的实现原理 平衡二叉树构建的基本思想就在在构建二叉排序树的过程中,每当插入一个结点时,先检查否是因为插入而破坏了树的平衡性,若是,这找出最小不平衡树,在满足二叉排序树…

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

平衡二叉树介绍 平衡二叉树,是一种二叉排序树,其中每一个节点的左子树和右子树的高度差最多等于1。由3位科学家共同发明,用他们首字母命名 又被称为AVL树。从平衡二叉树的名称,你也可以体会到它是一种高度平衡的二叉排序树。我们将二叉树上结点的左子树深度减去右子树的深度的值称为平衡因子BF,那么平衡二叉树上的所有结点的平衡因子只能是-1,0,1。 平衡二叉树的实现原理 平衡二叉树构建的基本思想就在在构建二叉排序树的过程中,每当插入一个结点时,先检查否是因为插入而破坏了树的平衡性,若是,这找出最小不平衡树,在满足二叉排序树…

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

插值查找算法介绍 插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中的占比哟。所以mid的计算公式为: (high-low)*(key-arr[low])/(arr[high]-arr[low])。对比折半查找的mid = (high-low)/2。 代码和折半查找一模一样,唯独mid的计算方式发生改变。这样的好处在于,对表长较…

2018年2月27日 0条评论 0点热度 阅读全文

插值查找算法介绍 插值查找(Interpolation Search)是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法,其核心就在于插值的计算公式key-arr[low]/arr[high]-arr[low]。细看是不是key在整序列中的占比哟。所以mid的计算公式为: (high-low)*(key-arr[low])/(arr[high]-arr[low])。对比折半查找的mid = (high-low)/2。 代码和折半查找一模一样,唯独mid的计算方式发生改变。这样的好处在于,对表长较…

2018年2月27日 0条评论 0点热度 阅读全文

实现思路 我们来看看下图的二叉链表 如何实现层序遍历。 层序遍历顺序:ABECDG A为B、E的双亲结点,遍历顺序是 根->左->右 是不是。 而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。A->出队 队列:E、B B->出队 队列:D、C、E E->出队 队列:G、D、C C->出队 队列:G、D …

2018年2月26日 0条评论 2点热度 阅读全文

实现思路 我们来看看下图的二叉链表 如何实现层序遍历。 层序遍历顺序:ABECDG A为B、E的双亲结点,遍历顺序是 根->左->右 是不是。 而且每个结点都是这样的遍历顺序 有木有。那么我们完全可以采用队列的数据结构呗。A入队->然后出队,出队时将其左右孩子入队,循环队列进行出队,每次出队将其左右孩子入队。当队列为空时,整棵树层序遍历完毕。还没明白请看下面过程。A->出队 队列:E、B B->出队 队列:D、C、E E->出队 队列:G、D、C C->出队 队列:G、D …

2018年2月26日 0条评论 5点热度 阅读全文

二叉链表介绍 二叉树每个结点最多有2个孩子,所以为它设计一个数据域和2个指针域是比较自然的想法,我们称这样的链表叫做二叉链表。 二叉链表思路 二叉链表的数据结构,数据域,左右孩子指针域。每个树结点都有左右孩子,如果没有孩子那么孩子指针域为NULL。我们用char类型的数据来模拟二叉链表的创建和遍历。 我们知道二叉链表的遍历有3种,前序遍历,中序遍历,后序遍历。那么创建链表的时候同样我们可以约定是前序、中序还是后序的形式进行进创建树结点。以下图为例,我们使用前序遍历的形式创建二叉链表,然后将用3种遍历形式输出。如图按…

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