二叉树的存储结构
顺序存储根据完全二叉树的性质:
结点 i 的的双亲结点为 向下取整(i/2)
结点 i 的左孩子为 2i
结点 i 的右孩子为 2i+1
所以完全二叉树可以很容易的确定结点间的关系,如找双亲,找左子节点,找右子节点,找兄弟节点
因此可以将一颗普通二叉树转换成完全二叉树用一维数组来储存
优点查 ...
二叉树以及完全二叉树的性质
二叉树的性质(一)第 i 层 最多有 2i-1 个结点
证明:略
(二)深度为 k 的二叉树,至多 2k - 1 个结点,至少 k 个结点至多:满二叉树时
证明:略
至少:每层只有一个结点
证明:略
(三)度为0的结点个数(叶子结点数) = 度为2的结点个数 + 1
证明:
除了根结点,每个结 ...
二叉树的定义和特点以及术语
二叉树定义度大于等于0且小于等于2的树(每个结点没有子结点或至多2个子结点)
二叉树的五种形态
空树(根结点也没有)
只有根结点
根节点只有左子树
根结点只有右子树
根结点既有左子树又有右子树
斜二叉树定义:所有结点都只有左子树称为左斜二叉树;所有结点都只有右子树称为右 ...
树的存储结构
双亲表示法
特点一般采用数组储存根结点的双亲规定为-1根结点储存在数组下标0的位置
优点求某结点的双亲和查找根结点很方便
缺点
查找某结点的孩子结点要遍历整个数组(看哪个结点的父结点等于要找的结点)
兄弟结点的位置关系不明确,如不知道是左孩子结点还是右孩子结点
随机删除和添加结点复杂
数据 ...
树的定义和特点以及术语
定义在树中常将数据元素称为结点,树是n个结点的有限集合(n>=0),n=0时称为空树
优点以数组实现的顺序表获取快,删除和添加慢。链表添加和删除快,获取慢。树能做到获取和添加删除都比较快。
非空树特点
没有父结点的结点为根结点;
每个结点有零个或多个子结点;
每个非根结点只有一个父结点;
每个 ...
单链表的反转
方法一从第二个节点开始,依次把节点变成头个节点。
java1234567891011121314151617//链表无辅助头节点public void 反转(){ if(_头指针 == null){ return; } 节 ...
链表的快慢指针问题
求链表的中间值list 中一般有 size 这个成员数属性,要求链表的中间值,只要遍历 size/2 次即可,但是如果没有这个 size 属性该如何求链表的中间值呢?
可以定义两个指针,开始都指向链表的头节点,然后慢指针每次移动一个节点,快指针每次移动两个节点,当快指针移动到元素末尾时,慢指针刚好 ...
ArrayList 源码阅读
主要 APIjava12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747 ...
常见排序算法的稳定性
定义数组arr中有若干元素,其中A元素和B元素相等,并且A元素在B元素前面,如果使用某种排序算法排序后,能够保证A元素依然在B元素的前面,可以说这个该算法是稳定的。
意义比如手机有销量和价格,先对价格排序,再对销量排序,如果排序算法是稳定的,当两手机销量相同时,那么价格也会是有序的。
常见排序算法的 ...
快速排序
图示
基本原理
两边扫描交换法
两边扫描填坑法之基点元素暂存
两边扫描填坑法之基点元素每次交换
单边扫描法
原理Code12341.首先设定一个分界值,通过该分界值将数组分成左右两部分; 2.将大于分界值的数据放到到数组右边,小于或等于分界值的数据放到数组的左边。此时左边部分中各元素 ...
