优点:
缺点:如果要检索具体某个值或插入值(按一定顺序)会整体移动,效率较低,如下的示意图
优点:在一定程度上对数组存储方式有优化
例如:插入一个数值节点,只需要将插入节点,链接到链表中即可,同理,删除效率也很好
缺点:检索效率较低
需要从头结点开始遍历查找。
简单说:
那么就出现了 树 这种数据结构
提供数据 存储 、读取 效率。
例如:利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入、删除、修改 的速度
如图所示:
节点:每一个圆圈表示一个节点,也称节点对象
根节点:最上面,最顶部的那个节点,也就是一棵树的入口
父节点:有子节点的节点
子节点
叶子节点:没有子节点的节点
节点的权:可以简单的理解为节点值
有时候也用 路径 来表示
路径:从 root 节点找到该节点的路线
层
子树:有子节点的父子两层就可以称为是一个子树
树的高度:最大层数
森林:多颗子树构成森林
树有很多种,每个节点 最多只能有两个子节点 的一种形式称为 二叉树
二叉树的子节点分为 左节点 和 右节点
如果该二叉树的所有 叶子节点 都在 最后一层,并且 节点总数 = 2^n-1 (n 为层数),则我们称为 满二叉树
如果该二叉树的所有叶子节点都在最 后一层或倒数第二层,而且 最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为 完全二叉树
有三种:
前、中、后序主要区别是输出父节点的时间来区分
前序遍历:
上图的输出顺序为:1、2、3、4
中序遍历:
上图的输出顺序为:2、1、4、3
后序遍历:
上图的输出顺序为:2、4、3、1
//定义节点 class HeroNode{ private int no;//当前节点编号 private String name;//当前节点名字 private HeroNode left;//当前节点左子树 private HeroNode right;//当前节点右子树 public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } //前序遍历 public void preOrder(){ //先输出当前节点 System.out.println(this); //递归遍历左子节点 if(this.left != null){ this.left.preOrder(); } //递归遍历右子节点 if(this.right != null){ this.right.preOrder(); } } //中序遍历 public void infixOrder(){ //先输出左子树 if(this.left != null){ this.left.infixOrder(); } //输出当前节点 System.out.println(this); //输出右子树 if(this.right != null){ this.right.infixOrder(); } } //后序遍历 public void postOrder(){ //先输出左子树 if(this.left != null){ this.left.postOrder(); } //输出右子树 if(this.right != null){ this.right.postOrder(); } //输出当前节点 System.out.println(this); } } //创建二叉树 class BinaryTree{ private HeroNode root; public void setRoot(HeroNode root) { this.root = root; } //前序遍历 public void preOrder(){ if(this.root != null){ this.root.preOrder(); }else{ System.out.println("当前二叉树为空"); } } //中序遍历 public void infixOrder(){ if(this.root != null){ this.root.infixOrder(); }else{ System.out.println("当前二叉树为空"); } } //后序遍历 public void postOrder(){ if(this.root != null){ this.root.postOrder(); }else{ System.out.println("当前二叉树为空"); } } } //创建二叉树 BinaryTree binaryTree = new BinaryTree(); //手动创建二叉树 HeroNode root = new HeroNode(1,"宋江"); HeroNode hero1 = new HeroNode(2,"吴用"); HeroNode hero2 = new HeroNode(3,"卢俊义"); HeroNode hero3 = new HeroNode(4,"林冲"); root.setLeft(hero1); root.setRight(hero2); hero2.setRight(hero3); binaryTree.setRoot(root); //遍历二叉树 System.out.println("前序遍历"); binaryTree.preOrder(); //中序遍历 System.out.println("中序遍历"); binaryTree.infixOrder(); //后序遍历 System.out.println("后序遍历"); binaryTree.postOrder();
要求:
id=5
的节点由于二叉树的查找是遍历查找,所以就简单了,前面遍历规则已经写过了,改写成查找即可
//在节点中增加查找方法 //前序查找 public HeroNode preOrderSearch(int no){ if(this.no == no){ return this; } HeroNode resNode = null; if(this.left != null){ resNode = this.left.preOrderSearch(no); } if(resNode != null){ return resNode; } if(this.right != null){ resNode = this.right.preOrderSearch(no); } return resNode; } //中序查找 public HeroNode infixOrderSearch(int no){ HeroNode resNode = null; if(this.left != null){ resNode = this.left.infixOrderSearch(no); } if(resNode != null){ return resNode; } if(this.no == no){ return this; } if(this.right != null){ resNode = this.right.infixOrderSearch(no); } return resNode; } //后序查找 public HeroNode postOrderSearch(int no){ HeroNode resNode = null; if(this.left != null){ resNode = this.left.postOrderSearch(no); } if(resNode != null){ return resNode; } if(this.right != null){ resNode = this.right.postOrderSearch(no); } if(resNode != null){ return resNode; } if(this.no == no){ return this; } return null; } //在二叉树中增加查找方法 //前序查找 public HeroNode preOrderSearch(int no){ HeroNode resNode = null; if(this.root != null){ resNode = this.root.preOrderSearch(no); }else{ System.out.println("当前二叉树为空"); } return resNode; } //中序 public HeroNode infixOrderSearch(int no){ HeroNode resNode = null; if(this.root != null){ resNode = this.root.infixOrderSearch(no); }else{ System.out.println("当前二叉树为空"); } return resNode; } //后序 public HeroNode postOrderSearch(int no){ HeroNode resNode = null; if(this.root != null){ resNode = this.root.postOrderSearch(no); }else{ System.out.println("当前二叉树为空"); } return resNode; }
可以看出:
要求:
测试:删除 5 号叶子节点和 3 号子树。
说明:目前的二叉树不是规则的,如果不删除子树,则需要考虑哪一个节点会被上提作为父节点。这个后续讲解排序二叉树时再来实现。先实现简单的
思路分析:
由于我们的二叉树是单向的
所以我们判定一个节点是否可以删除,是判断它的 子节点,是否可删除,否则则没法回到父节点删除了,因为要判断被删除的节点满足前面的两点要求
如果前面都没有删除,则继续递归删除。上面的要求是 2 点,实际上是,找到符合条件的节点则直接删除(因为不考虑是否有子树)
如果树只有一个 root 节点,则将 root 节点置空
//节点中增加删除方法 public void delete(int no){ if(this.left != null){ if(this.left.no == no){ this.left = null; return; } } if(this.right != null){ if(this.right.no == no){ this.right = null; return; } } //向左递归 if(this.left != null){ this.left.delete(no); } //向右递归 if(this.right != null){ this.right.delete(no); } } //二叉树中增加删除方法 public void delete(int no){ if(this.root != null){ if(this.root.getNo() == no){ this.root = null; return; }else{ this.root.delete(no); } }else{ System.out.println("当前二叉树为空"); } }
从数据存储来看,数组存储 方式和 树 的存储方式可以 相互转换。即使数组可以转换成树,树也可以转换成数组。如下示意图
上图阅读说明:
现在有两个要求:
arr=[1,2,3,4,5,6,7]
想要 实现上面的两个要求,需要知道顺序存储二叉树的特点:
2*n+1
2*n+2
(n-1)/2
注:n 表示二叉树中的第几个元素(按 0 开始编号)
比如:
2 * 1 + 1 = 3
,对比上图去查看,的确是 32 * 1 + 2 = 4
,也 就是元素 52 * 2 + 1 = 5
,也就是元素 6(2-1)/2= 1/2 = 0
,也就是根节点 1//顺序存储二叉树 class ArrayBinaryTree{ private int[] array; public ArrayBinaryTree(int[] array) { this.array = array; } //前序遍历输出顺序存储二叉树 public void preOrder(int index){ if(array == null || array.length == 0){ System.out.println("数组为空,不能遍历完全二叉树"); } //先输出当前元素 System.out.println(array[index]); //再递归输出左子元素 if((index*2+1) < array.length){ preOrder((index*2 + 1)); } //再递归输出右子元素 if((index*2+2) < array.length){ preOrder((index*2 +2)); } } public void preOrder(){ preOrder(0); } //中序遍历输出顺序存储二叉树 public void infixOrder(int index){ if(array == null || array.length == 0){ System.out.println("数组为空,不能遍历完全二叉树"); } if((index*2 +1) < array.length){ infixOrder((index*2 + 1)); } System.out.println(array[index]); if((index*2 + 2) < array.length){ infixOrder((index*2+2)); } } public void infixOrder(){ infixOrder(0); } //后序遍历顺序存储二叉树 public void postOrder(int index){ if(array == null || array.length == 0){ System.out.println("数组为空,不能遍历完全二叉树"); } if((index*2 + 1) < array.length){ postOrder((index*2+1)); } if((index*2 + 2) < array.length){ postOrder((index*2+2)); } System.out.println(array[index]); } public void postOrder(){ postOrder(0); } }
看如下问题:将数列 {1,3,6,8,10,14}
构成一颗二叉树
可以看到上图的二叉树为一颗 完全二叉树。对他进行分析,可以发现如下的一些问题:
8,3,10,1,14,6
6,8,10,14
这几个节点的左右指针,并没有完全用上如果希望充分利用各个节点的左右指针,让各个节点可以 指向自己的前后节点,这个时候就可以使用 线索化二叉树 了
n 个节点的二叉树链表中含有 n + 1
个空指针域,他的推导公式为 2n-(n-1) = n + 1
。
利用二叉链表中的空指针域,存放指向该节点在 某种遍历次序 *下的 **前驱** 和 **后继** 节点的指针,这种附加的指针称为*「线索」
如下图,在中序遍历中,下图的中序遍历为 8,3,10,1,14,6
,那么 8 的后继节点就为 3,3 的后继节点是 10
这种加上了线索的二叉树链表称为 线索链表(节点存储了下一个节点,组成了链表,并且一般的二叉树本来就是用链表实现的),相应的二叉树称为 线索二叉树(Threaded BinaryTree)。根据线索性质的不同,线索二叉树可分为:前、中、后序线索二叉树。
将上图的二叉树,进行 中序线索二叉树,中序遍历的数列为 8,3,10,1,14,6
。
那么以上图为例,线索化二叉树后的样子如下图
注意:当线索化二叉树后,那么一个 Node 节点的 left 和 right 属性,就有如下情况:
left 指向的是 左子树,也可能是指向 前驱节点
例如:节点 1 left 节点指向的是左子树,节点 10 的 left 指向的就是前驱节点
right 指向的是 右子树,也可能是指向 后继节点
例如:节点 3 的 right 指向的是右子树,节点 10 的 right 指向的是后继节点
//创建节点 class HeroNode{ private int no; private String name; private HeroNode left; private HeroNode right; //左右子树的类型,如果是左右子树就是0,如果是前驱或者后继节点就是1 private int leftType; private int rightType; public HeroNode(int no, String name) { this.no = no; this.name = name; } public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } } //创建线索化二叉树 class ThreadBinaryTree{ private HeroNode root;//表示跟节点 private HeroNode pre;//表示前驱节点 public void setRoot(HeroNode root) { this.root = root; } public void threadedNodes(){ threadedNodes(root); } //中序线索化遍历 public void threadedList(){ if(root == null){ System.out.println("线索化二叉树为空"); return; } HeroNode node = root; while(node != null){ //找到第一个有前驱节点的元素 while(node.getLeftType() != 1){ node = node.getLeft(); } //输出第一个元素 System.out.println(node); //当有后继节点的情况会进入 while(node.getRightType() == 1){ node = node.getRight(); System.out.println(node); } //当一个节点没有后继节点的时候直接获取右子树 node = node.getRight(); } } //中序线索化 public void threadedNodes(HeroNode node){ if(node == null){ return; } //先线索化左子树 threadedNodes(node.getLeft()); //再线索化当前节点 /* * 1.设置前驱节点, * 2.设置后继节点 * */ if(node.getLeft() == null){ node.setLeft(pre); node.setLeftType(1); } //线索化后继节点,需要遍历到下一个节点的时候,通过下一个节点设置 if(pre != null && pre.getRight() == null){ pre.setRight(node); pre.setRightType(1); } //将前驱节点后移 pre = node; //线索化右子树 threadedNodes(node.getRight()); } }
//前序线索化 public void preThreadedNodes(HeroNode node){ if(node == null){ return; } //先序列化自己 if(pre != null && node.getLeft() == null){ node.setLeft(pre); node.setLeftType(1); } if(pre != null && pre.getRight() == null){ pre.setRight(node); pre.setRightType(1); } pre = node; //再序列化递归左子树 if(node.getLeftType() == 0){ preThreadedNodes(node.getLeft()); } //再递归序列化右子树 if(node.getRightType() == 0){ preThreadedNodes(node.getRight()); } } //前序序列化遍历 public void preThreadedList(){ if(root == null){ System.out.println("线索化二叉树为空"); return; } HeroNode node = root; while(node != null){ System.out.println(node); while(node.getLeftType() == 0){ node = node.getLeft(); System.out.println(node); } while (node.getRightType() == 1) { node = node.getRight(); System.out.println(node); } node = node.getRight(); } }