算法与数据结构学习笔记（一）-查找二叉树
一.简介
普通树：https://baike.baidu.com/item/%E6%A0%91%E7%BB%93%E6%9E%84/3399688?fr=aladdin
二叉树：https://baike.baidu.com/item/%E4%BA%8C%E5%8F%89%E6%A0%91
查找二叉树又称搜索二叉树，是一种特殊的二叉树（其实也可以叫被限制的二叉树）。普通的树是即是一种非线性的数据结构，由很多的节点按照父子关系相互关联。对于任意一个节点最多只有2个子节点的树就称为二叉树。
重点！！对于任意一个节点，左子树中任意节点的值都小于该节点的值且右子树中任意节点的值都大于该节点的值，对于瞒住这样条件的二叉树即为查找二叉树
二.性质与作用
性质：
性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。
性质2：深度为k的二叉树最多有2k-1个结点（k≥1）。
性质3：一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。
证：结点总数n = n0 + n1 + n2。设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。综上：n = n0 + n1 + n2 = B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1。
性质4：具有n个结点的完全二叉树的深度为floor(log2n) + 1 。
性质5：如果对一棵有n个结点的完全二叉树（其深度为floor(log2n) + 1 ）的结点按层序编号，则对任一结点i（1≤i≤n）有：
（1） 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲PARENT(i)是结点 floor((i)/2)。
（2）如果2i > n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i。
（3）如果2i + 1 > n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i + 1。
对于上面的这些性质，我也没去验证，网上Copy的
作用：
其他作用不清楚，用来存储是没有问题的。顾名思义，对于一个构建完成的查找二叉树，根据定义可知，从跟节点开始，与查找值进行对比，相等则查找成功，大于则继续查找右子树，小于则继续查找左子树。
而对于查找二叉树，它的时间复杂度为：O(Log2n)到O(n)。原因：因为当二叉树为非常平衡的二叉树（平衡二叉树）时复杂度为O(Log2n)。但是如果二叉树构建得最糟糕时将退化为线性结构。复杂度就为O(n)
三.代码实现
（1）建立实体
首先我们需要两个实体模型来描述该数据结构 1.节点 2.树
public class TreeNode { private int value; public int childrenNum = 0; private TreeNode leftNode; private TreeNode rightNode; public TreeNode(int value) { this.value = value; } //getter setter 省略... }
节点类：具有 值，左子节点，右子节点，子节点数量等属性。
节点重写equals方法
@Override public boolean equals(Object obj) { if (obj == null) { return false; } if (!(obj instanceof TreeNode)) { return false; } TreeNode o = (TreeNode) obj; return this.getValue() == o.getValue(); }
public class BinaryTree { private TreeNode root = null; public BinaryTree() { } }
树类：具有根节点属性
然后对于这个树肯定就有构建树，新增节点，删除节点，查询节点方法。（没修改）当完成这一系列的方法后就实现了查找二叉树。（本次代码的存储数据默认为 int）
应为方法之间存在调用关系，已经公用方法。则将公用方法放在前面
获取节点的父节点：
//第一个参数为树节点，第二参数为查询节点 private TreeNode getParentNode(TreeNode root, TreeNode node) { //当前节点的左右子节点存在与查询节点相同，则返回当前节点。此处的equals需要重写。不重写的话应该用值进行比较 if (node.equals(root.getRightNode()) || node.equals(root.getLeftNode())) { return root; } //根据节点值得比较进行不同方向的递归 if (node.getValue() > root.getValue()) { return getParentNode(root.getRightNode(), node); } else { return getParentNode(root.getLeftNode(), node); } }
添加节点的递归方法
//往传入节点的左边添加节点 private boolean add2Right(TreeNode node, int v) { //传入节点没有右节点则添加节点 if (node.getRightNode() == null) { node.setRightNode(new TreeNode(v)); node.childrenNum++; return true; } //与传入节点的右节点比较，相等抛出异常，大于则递归往右添加，小于则往左添加 if (v > node.getRightNode().getValue()) { return add2Right(node.getRightNode(), v); } else if (v == node.getRightNode().getValue()) { throw new RuntimeException("value empty exception"); } else { return add2Left(node.getRightNode(), v); } } //往传入节点的左边添加节点 private boolean add2Left(TreeNode node, int v) { //传入节点没有左节点则添加节点 if (node.getLeftNode() == null) { node.setLeftNode(new TreeNode(v)); node.childrenNum++; return true; } //与传入节点的左节点比较，相等抛出异常，大于则递归往右添加，小于则往左添加 if (v > node.getLeftNode().getValue()) { return add2Right(node.getLeftNode(), v); } else if (v == node.getLeftNode().getValue()) { throw new RuntimeException("value empty exception"); } else { return add2Left(node.getLeftNode(), v); } }
通过以上两个方法，递归添加子节点
新增节点：
//新增节点 public boolean put(int value) { //判断跟节点是否为空，空则新增并返回成功 if (root == null){ root = new TreeNode(value); return true; } //从根节点递归添加 if (value > root.getValue()) { return add2Right(root, value); } else if (value == root.getValue()) { throw new RuntimeException("value empty exception"); } else { return add2Left(root, value); } }
构建树方法：
//构建 public BinaryTree build(int[] list) { //遍历源数据，新增根节点或调用新增方法插入 for (int t : list) { if (root == null) { root = new TreeNode(t); continue; } put(t); } return this; }
查询节点：
//查询 public TreeNode select(int v) { //从跟节点开始查询 return select(root, v); } private TreeNode select(TreeNode node, int v) { if (node == null) { throw new RuntimeException("value non-existent Exception"); } //根据查询值和当前节点值对比，相同则返回，否则继续递归 if (v > node.getValue()) { return select(node.getRightNode(), v); } else if (v == node.getValue()) { return node; } else { return select(node.getLeftNode(), v); } }
删除节点：删除的时候就比较特殊，首先需要保证两点。1.删除后树不能断，所以就是删除时需要对删除节点的父节点重新设置子节点。2.在重新设置节点时还必须保证查找二叉树的定义。左边的子树节点小于父节点小于右边的子树节点。
//删除 public void deleted(int value) { //从根节点开始排查 deleted(root, value); } private void deleted(TreeNode node, int value) { //当前节点值与删除值相同则执行删除操作 if (value == node.getValue()) { //del TreeNode parentNode = getParentNode(node); if (parentNode == null) { root = null; return; } //判断子节点数量。0的话直接删除 if (node.childrenNum == 0) { if (node.equals(parentNode.getLeftNode())) { parentNode.setLeftNode(null); } else { parentNode.setRightNode(null); } //子节点数量为1时直接删除将本节点的父节点指向本节点的子节点 } else if (node.childrenNum == 1) { TreeNode childrenNode = node.getOnlyChildren(); //判断本节点是父节点的左子节点还是右子节点 if (node.equals(parentNode.getLeftNode())) { parentNode.setLeftNode(childrenNode); } else { parentNode.setRightNode(childrenNode); } }else {//有两种方案，1.把右子树往上提，左子树作为上提后的的最左子树、2.把左子树往上提，右子树作为上提后的最右子树 TreeNode newTreeNode = node.getRightNode(); TreeNode mostLeftNode = newTreeNode.getMostLeftNode(); mostLeftNode.setLeftNode(node.getLeftNode()); if (node.equals(parentNode.getLeftNode())) { parentNode.setLeftNode(newTreeNode); } else { parentNode.setRightNode(newTreeNode); } } } else if (value > node.getValue()) { if (node.getRightNode() != null) { deleted(node.getRightNode(), value); } else { throw new RuntimeException("value empty exception"); } } else { if (node.getLeftNode() != null) { deleted(node.getLeftNode(), value); } else { throw new RuntimeException("value empty exception"); } } }
注意：当删除节点具有两个子节点时，本代码采取的是将右子节点（R）作为新节点连接删除节点（D）的父节点（DP），然后将D节点的左子节点（L）指向R节点树的最左叶子
public TreeNode getMostLeftNode() { if (this.getLeftNode()==null){ return this; }else { return this.getLeftNode().getMostLeftNode(); } }
如上图中假设需要删除10。那么就用11代替10的位置，然后将9这整颗树全部放在11的最左叶子上。因为11本身就是最左子叶子，则直接将9这颗树指作为11的左子树
四.结语
对于这个代码是以int 作为存储值，那么我们有办法存储其他的值么？
答案当然是有的！那就是值为任意对象！！比较判断的时候使用对象的HashCode。使用泛型实现的存储任意对象的代码：
https://github.com/Garfield158/xuexibiji.git
回忆HashMap的实现，jdk1.8后,当数据较少时使用的是数组加链表实现，而当数据较多时则采用红黑树。然后红黑树又是一种极其特殊的二叉树。（后面如果我搞懂了红黑树会记录），是不是通过查找二叉树就可以实现一个自己的HashMap或者HashSet（HashSet底层也是用HashMap实现的）呢。