二叉树
二叉树
定义
二叉树是每个节点最多有两个子树的树结构。它有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空。
基本术语
- 度：节点所拥有子节点的个数
- 叶子节点：度为0的节点，即是没有子节点的节点
- 分支节点：度不为0的节点
- 根节点： 没有父节点的节点
- 层次：根节点的层次为1，其余节点的层次等于该双亲节点的层次加1
- 深度：树中节点的最大层次
性质
- 性质1：二叉树第i层上的结点数目最多为
2^{i-1}(i≥1)。 - 性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
- 性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
- 性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
满二叉树
定义
- 除了最后一层，所有分支节点的子节点个数为2
特点
- 叶子只能出现在最后一层。
- 非叶子结点度一定是2.
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。
完全二叉树
定义
- 若设二叉树的深度为h，除第 h 层外，其它各层 (1~h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
- 完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
- 一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，而在最后一层上，右边的若干结点缺失的二叉树，则此二叉树成为完全二叉树。
判断完全二叉树
- 完全二叉树：
叶节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树 - 满二叉树必然是完全二叉树，完全二叉树不一定是满二叉树
特点
- 叶子结点只可能在最大的两层上出现,对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L 或 L+1;
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
- 只允许最后一层有空缺结点且空缺在右边，即叶子结点只能在层次最大的两层上出现
- 对任一结点，如果其右子树的深度为j，则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个
二叉查找树
定义
- 二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
- 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
插入节点
12345678910111213141516171819202122232425262728293031323334353637383940414243 | /** * 插入节点 * @param value 节点的值 */ public void insertNode(int value){ //如果根节点为null if (root==null) { root=new Node(value,null,null); //创建根节点,此时没有左右子节点 return; //返回即可，表示插入成功，这个插入的节点就是根节点 } //如果根节点已经存在，那么就需要从根节点开始比较大小 Node currentNode=root; //当前节点 Node parentNode=root; //当前节点的父节点，需要保存这个节点 boolean isLeftChild=true; //记录待插入的数是parentNode的左节点还是右节点 //当当前节点不为空，表示没有找到插入的位置，当currentNode节点为null的时候，那么这个就是待插入的位置 while(currentNode!=null){ parentNode=currentNode; //保存当前节点的父节点 //如果待插入的值小于当前值，那么到当前节点的左子树中查找 if (value<currentNode.getValue()) { currentNode=currentNode.getLeftChild(); //当前节点继续向下成为左子节点 isLeftChild=true; //左节点 }else if (value>currentNode.getValue()) { //如果待插入的数大于当前节点的值，那么到当前节点的右边查找 currentNode=currentNode.getRightNode(); isLeftChild=false; }else { //value和currentNode.value相等，不允许插入 System.out.println(value+"已经存在，不允许插入"); return; //直接返回，后面的数字不用插入了 } } //循环结束，此时的parentNode就是待插入数字的父节点 //如果待插入的节点是左子节点 if (isLeftChild) { Node node=new Node(value, null, null); parentNode.setLeftChild(node); //设置左节点 }else { //是右子节点 Node node=new Node(value, null, null); parentNode.setRightNode(node); //设置右节点 } } |
|---|
查找指定值
- 比较需要查找的值，如果大于当前节点的值，在其右子树中查找，如果小于当前节点的值，在其左子树中查找
123456789101112131415161718 | /** * 在二叉查找树中查找指定的值 * @param value * @return 返回的找到的节点，如果为null表示没有找到 * 从根节点查找，比较值，如果大于，在右子树中查找，如果小于在左子树中查找 */public Node findValue(int value){ Node currentNode=this.root; //从根节点开始查找 //如果currentNode不为null并且值不相等，跳出循环的条件是：要么没有找到，返回null，要么找到了，值相等 while(currentNode!=null&¤tNode.value!=value){ if (value<currentNode.getValue()) { currentNode=currentNode.getLeftChild(); }else { currentNode=currentNode.getRightNode(); } } return currentNode;} |
|---|
删除节点
- 分为三种：
- 删除叶子节点
- 删除只有一个子节点的节点
- 删除含有两个子节点的节点
参考文章
二叉树的遍历
前序遍历
- 访问顺序： 先访问父结点，再
前序遍历左子树，最后再前面序遍历右子树，即是： 父节点 – 左 子树 — 右子树
- 图中遍历的结果是：
- 从根节点开始，访问1
- 访问2，此时的2作为父节点，访问左子树
- 访问4，此时的4作为父节点，访问左子树，没有左子树，访问右子树，也没有右子树，此时开始访问父节点4的右子树
- 访问5，此时的5作为父节点，访问左子树
- 访问7，此时的7作为父节点，访问左子树，没有，访问右子树
- 访问8 ，此时的8作为父节点，访问左子树，没有，访问右子树没有，此时以1作为父节点，开始访问有节点
- 访问3，此时的3作为父节点，访问左子树，没有，访问右子树
- 访问6，此时的6作为父节点，左右节点都没有，访问结束
- 最后的前序遍历为：1，2，4，5，7，8，3，6。
- 递归调用的算法如下：
123456789101112131415161718 | //前序遍历对外的方法 public void PreOrder(){ PreOrder(this.root); //从根节点开始访问 } /** * 前序遍历 * 递归 * @param node 父节点 */ private void PreOrder(Node node){ //如果节点不为null if (node!=null) { System.out.println(node.getValue()); //输出值 PreOrder(node.getLeftChild()); //访问左子树 PreOrder(node.getRightNode()); //访问右子树 } } |
|---|
中序遍历
- 先中序遍历左子树，然后再访问根结点，最后再中序遍历右子树即左—根—右
- 总的来说，把当前节点看成是根节点，如果这个根节点还存在左子树，继续向下，直到当前节点不存在左子树，那么输出当前节点即可，然后输出父节点的值，然后输出右子树的值，如此反复即可
- 中序遍历的规则是【左根右】，我们从root节点A看起； 此时A是根节点，遍历A的左子树； A的左子树存在，找到B，此时B看做根节点，遍历B的左子树； B的左子树不存在，返回B，根据【左根右】的遍历规则，记录B，遍历B的右子树； B的右子树存在，找到C，此时C看做根节点，遍历C的左子树； C的左子树存在，找到D，由于D是叶子节点，无左子树，记录D，无右子树，返回C，根据【左根右】的遍历规则，记录C，遍历C的右子树； C的右子树不存在，返回B，B的右子树遍历完，返回A； 至此，A的左子树遍历完毕，根据【左根右】的遍历规则，记录A，遍历A的右子树； A的右子树存在，找到E，此时E看做根节点，遍历E的左子树； E的左子树不存在，返回E，根据【左根右】的遍历规则，记录E，遍历E的右子树； E的右子树存在，找到F，此时F看做根节点，遍历F的左子树； F的左子树存在，找到G，此时G看做根节点，遍历G的左子树； G的左子树存在，找到H，由于H是叶子节点，无左子树，记录H，无右子树，返回G，根据【左根右】的遍历规则，记录G，遍历G的右子树； G的右子树存在，找到K，由于K是叶子节点，无左子树，记录K，无右子树，返回G，根据【左根右】的遍历规则，记录F，遍历F的右子树； F的右子树不存在，返回F，E的右子树遍历完毕，返回A； 至此，A的右子树也遍历完毕；
- 详细的算法如下：
123456789101112 | //中序遍历对外的方法 public void InOrder(){ InOrder(this.root); //传入根节点 } private void InOrder(Node node){ if (node!=null) { InOrder(node.getLeftChild()); //先遍历左子树 System.out.println(node.getValue()); InOrder(node.getRightNode()); //遍历右子树 } } |
|---|
后续遍历
- 先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。
- 总的来说，把当前节点当做根节点，只要是存在左右子树的继续向下，不输出当前节点的值，直到没有左右子树才输出，再返回，如此反复即可
- 总结： 当根据顺序访问的时候，只要当前节点没有左右节点或者左右节点已经输出过了，才可以输出当前节点的值
- 详细过程如下：
- 从根节点1开始，访问左子树2，把2当成根节点，访问左子树4，把4当成根节点，访问左子树，没有，输出4
- 返回父节点2，把2当成根节点，此时的左子树4已经输出了，那么开始访问右子树5，把5当成根节点，访问左子树7，把7当成根节点，访问左子树，没有，但是存在右子树8，把8当成根节点，访问左子树，没有，访问右子树，没有，此时输出8
- 返回父节点7，发现不存在左节点，右节点8已经输出了，因此输出7
- 返回父节点5，发现左节点7已经输出了，并且没有右子树，因此输出5
- 返回父节点2，发现左右节点都输出了，因此继续返回父4节点1
- 把1当成根节点，发现左子树已经遍历完成，访问左子树3，把当前的3当成根节点，访问左子树，没有，访问右子树6，把6当成根节点，发现左右子树都不存在，输出6
- 返回父节点3，发现没有左子树，并且右节点6已经输出了，因此输出3
- 返回父节点1，输出1
- 最终的顺序为：4,8,7,5,6,3,1
- 详细算法如下：
12345678910111213 | //后序遍历对外的方法 public void PostOrder(){ this.PostOrder(this.root); //从根节点开始 } //后序遍历 private void PostOrder(Node node){ if(node!=null){ PostOrder(node.getLeftChild()); //遍历左子树 PostOrder(node.getRightNode()); //遍历右子树 System.out.println(node.getValue()); //输出 } } |
|---|