一、二叉树理解
1、以前学习链表的时候，一个节点只有一个数据；现在学习的二叉树，一个节点好比有三个数据，分别为：根节点数据、左节点数据、右节点数据。
2、这样的比喻对我来说比较好理解。
3、一些示意图：图一是单个，图二是多个连接起来。
图一：
图二：
二、二叉树的代码实现(自己根据思想写的)
public class BiTree { BiTreeNode root; BiTree(Integer root){ this.root=new BiTreeNode(root); } BiTree(){ this.root=null; } //树的节点类 public class BiTreeNode { public Integer data; public BiTreeNode lchild,rchild,parent; public BiTreeNode(){} public BiTreeNode(Integer data){ this(); this.data=data; this.lchild=null; this.rchild=null; this.parent=null; } public BiTreeNode(Integer data,BiTreeNode lchild,BiTreeNode rchild,BiTreeNode parent){ this(); this.data=data; this.lchild=lchild; this.rchild=rchild; this.parent=parent; } } /* * 查找某个节点，我们必须从根节点开始遍历。 ①、查找值比当前节点值大，则搜索右子树； ②、查找值等于当前节点值，停止搜索（终止条件）； ③、查找值小于当前节点值，则搜索左子树； */ public BiTreeNode find(Integer key){ BiTreeNode curNode=this.root; while(curNode!=null){ if((int)curNode.data>(int)key){ curNode=curNode.lchild; } else if((int)curNode.data<(int)key){ curNode=curNode.rchild; } else{ return curNode; } } return null; } /* * 要插入节点，必须先找到插入的位置。与查找操作相似，由于二叉搜索树的特殊性， * 待插入的节点也需要从根节点开始进行比较，小于根节点则与根节点左子树比较，反之则与右子树比较，直到左子树为空或右子树为空，则插入到相应为空的位置， * 在比较的过程中要注意保存父节点的信息 及 待插入的位置是父节点的左子树还是右子树，才能插入到正确的位置。 */ public boolean insert(BiTree bt,Integer value){ BiTreeNode curNode=bt.root; BiTreeNode newNode=new BiTreeNode(value); BiTreeNode parentNode=null; //判断当前是不是空树 if(curNode==null){ bt.root=newNode; return true; } while(curNode!=null){ parentNode=curNode; //这里插入比较只支持int类型的 if((int)curNode.data>(int)value){ curNode=curNode.lchild; if(curNode==null){ parentNode.lchild=newNode; newNode.parent=parentNode; return true; } } else{ curNode=curNode.rchild; if(curNode==null){ parentNode.rchild=newNode; newNode.parent=parentNode; return true; } } } return false; } /* * 查找最小结点：返回tree为根结点的二叉树的最小结点。 */ public BiTreeNode minimum(BiTreeNode tree) { if(tree==null) return null; while(tree.lchild!=null){ tree=tree.lchild; } return tree; } /* * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。 */ public BiTreeNode successor(BiTreeNode x){ if(x.rchild!=null){ return minimum(x.rchild); } BiTreeNode y=x.parent; while((y!=null)&&(y.rchild==x)){ x=y; y=y.parent; } return y; } /* * 三种情况： * 1、要删除节点无子节点 * 2、有左节点或右节点 * 3、左、右节点都有 */ private void deleteNoChild(BiTreeNode node ){ //判断是不是根节点 if(node.parent==null) root=null; //判断是左节点还是右节点，然后将他删除 if(node==node.parent.lchild) node.parent.lchild=null; else{ node.parent.rchild=null; } } private void deleteHaveOneChild(BiTreeNode node ){ //判断是不是根节点 if(node.parent==null){ if(node.lchild!=null){ root=node.lchild; } else{ root=node.rchild; } } else{ if(node==node.parent.lchild){ //判断有左节点，还是有右节点 if(node.lchild!=null){ //设置该节点的左孩子 为该节点的父节点的左孩子 node.parent.lchild=node.lchild; //设置该节点的左孩子的父节点 为 该节点的父节点 node.lchild.parent =node.parent; } else{ node.parent.lchild=node.rchild; node.rchild.parent =node.parent; } } else{ //判断有左节点，还是有右节点 if(node.lchild!=null){ //设置该节点的左孩子 为该节点的父节点的右孩子 node.parent.rchild=node.lchild; //设置该节点的左孩子的父节点 为 该节点的父节点 node.lchild.parent =node.parent; } else{ node.parent.rchild=node.rchild; node.rchild.parent =node.parent; } } } } //查找出要删除节点的后续节点，，将后续节点的值保留， 再将后续节点删除，再将后续节点的值赋值到要删除的节点的值上。(就是将问题改变成了上面的两种情况) private void deleteHaveLRChild(BiTreeNode node){ //要删除节点的后继节点 BiTreeNode successor = successor(node); node.data=successor.data; //后续节点是否为 待删除节点的右节点 if(successor ==node.rchild){ //后续节点没有子节点 if(successor.lchild==null && successor.rchild==null){ node.rchild=null; return ; } else{ //后续节点只有一个右节点 node.rchild=successor.rchild; successor.rchild.parent=node; return; } } if(successor.lchild==null && successor.rchild==null){ successor.parent.lchild=null; return; } else{ successor.parent.lchild=successor.rchild; successor.rchild.parent=successor.parent; return; } } public boolean delete(Integer key){ BiTreeNode node=find(key); if(node!=null){ //1、 if(node.lchild==null && node.rchild==null){ deleteNoChild(node); } //2、 else if(node.lchild!=null && node.rchild!=null){ deleteHaveLRChild(node); } //3、 else{ deleteHaveOneChild(node); } return true; } return false; } //前序遍历的递归方式 public void preRootTraverse(BiTreeNode bt){ if(bt==null) return; System.out.print(bt.data+" "); preRootTraverse(bt.lchild); preRootTraverse(bt.rchild); } //中序遍历：左子树——》根节点——》右子树 public void inRootTraverse(BiTreeNode bt){ if(bt==null) return; inRootTraverse(bt.lchild); System.out.print(bt.data+" "); inRootTraverse(bt.rchild); } //后续遍历 public void posRootTraverse(BiTreeNode bt){ if(bt==null) return; posRootTraverse(bt.lchild); posRootTraverse(bt.rchild); System.out.print(bt.data+" "); } }
三、过程总结
a、删除节点比较麻烦，节点有三种情况。
1、待删除节点无子节点；2、待删除节点只有一个子节点；3、待删除节点有两个子节点（找到它的后继节点，然后将后继节点的值赋值给待删除节点，然后删除后继节点就好了，这时就会变成前面两种情况）；
2、自己画的图例：
3、参考链接：https://blog.csdn.net/isea533/article/details/80345507
b、根据删除节点的思想，自己写一遍就很容易理解网上简洁的代码了。
四、网上的完整二叉树代码（简洁版）
public class BSTree<T extends Comparable<T>> { BSTNode<T> mRoot; // 根结点 public class BSTNode<T extends Comparable<T>> { T key; // 关键字(键值) BSTNode<T> left; // 左孩子 BSTNode<T> right; // 右孩子 BSTNode<T> parent; // 父结点 public BSTNode(T key, BSTNode<T> parent, BSTNode<T> left, BSTNode<T> right) { this.key = key; this.parent = parent; this.left = left; this.right = right; } public T getKey() { return key; } public String toString() { return "key:"+key; } } public BSTree() { mRoot=null; } /* * 前序遍历"二叉树" */ private void preOrder(BSTNode<T> tree) { if(tree != null) { System.out.print(tree.key+" "); preOrder(tree.left); preOrder(tree.right); } } public void preOrder() { preOrder(mRoot); } /* * 中序遍历"二叉树" */ private void inOrder(BSTNode<T> tree) { if(tree != null) { inOrder(tree.left); System.out.print(tree.key+" "); inOrder(tree.right); } } public void inOrder() { inOrder(mRoot); } /* * 后序遍历"二叉树" */ private void postOrder(BSTNode<T> tree) { if(tree != null) { postOrder(tree.left); postOrder(tree.right); System.out.print(tree.key+" "); } } public void postOrder() { postOrder(mRoot); } /* * (递归实现)查找"二叉树x"中键值为key的节点 */ private BSTNode<T> search(BSTNode<T> x, T key) { if (x==null) return x; int cmp = key.compareTo(x.key); if (cmp < 0) return search(x.left, key); else if (cmp > 0) return search(x.right, key); else return x; } public BSTNode<T> search(T key) { return search(mRoot, key); } /* * (非递归实现)查找"二叉树x"中键值为key的节点 */ private BSTNode<T> iterativeSearch(BSTNode<T> x, T key) { while (x!=null) { int cmp = key.compareTo(x.key); if (cmp < 0) x = x.left; else if (cmp > 0) x = x.right; else return x; } return x; } public BSTNode<T> iterativeSearch(T key) { return iterativeSearch(mRoot, key); } /* * 查找最小结点：返回tree为根结点的二叉树的最小结点。 */ private BSTNode<T> minimum(BSTNode<T> tree) { if (tree == null) return null; while(tree.left != null) tree = tree.left; return tree; } public T minimum() { BSTNode<T> p = minimum(mRoot); if (p != null) return p.key; return null; } /* * 查找最大结点：返回tree为根结点的二叉树的最大结点。 */ private BSTNode<T> maximum(BSTNode<T> tree) { if (tree == null) return null; while(tree.right != null) tree = tree.right; return tree; } public T maximum() { BSTNode<T> p = maximum(mRoot); if (p != null) return p.key; return null; } /* * 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。 */ public BSTNode<T> successor(BSTNode<T> x) { // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。 if (x.right != null) return minimum(x.right); // 如果x没有右孩子。则x有以下两种可能： // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。 // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。 BSTNode<T> y = x.parent; while ((y!=null) && (x==y.right)) { x = y; y = y.parent; } return y; } /* * 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。 */ public BSTNode<T> predecessor(BSTNode<T> x) { // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。 if (x.left != null) return maximum(x.left); // 如果x没有左孩子。则x有以下两种可能： // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。 // (01) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"。 BSTNode<T> y = x.parent; while ((y!=null) && (x==y.left)) { x = y; y = y.parent; } return y; } /* * 将结点插入到二叉树中 * * 参数说明： * bst 二叉树 * z 插入的结点 */ private void insert(BSTree<T> bst, BSTNode<T> z) { int cmp; BSTNode<T> y = null; BSTNode<T> x = bst.mRoot; // 查找z的插入位置 while (x != null) { y = x; cmp = z.key.compareTo(x.key); if (cmp < 0) x = x.left; else x = x.right; } z.parent = y; if (y==null) bst.mRoot = z; else { cmp = z.key.compareTo(y.key); if (cmp < 0) y.left = z; else y.right = z; } } /* * 新建结点(key)，并将其插入到二叉树中 * * 参数说明： * tree 二叉树的根结点 * key 插入结点的键值 */ public void insert(T key) { BSTNode<T> z=new BSTNode<T>(key,null,null,null); // 如果新建结点失败，则返回。 if (z != null) insert(this, z);//哪个树对象调用这个方法，就传该树对象进去 } /* * 和下面的remover方法是一样的效果，这个方法更容易理解点，这个方法一定要好好看，very good */ private BSTNode<T> delete(BSTNode<T> node) { //第 3 种情况，如果同时存在左右子节点 if (node.left != null && node.right != null){ //获取后继结点 BSTNode<T> successor = successor(node); //转移后继结点值到当前节点 node.key = successor.key; //把要删除的当前节点设置为后继结点 node = successor; } //经过前一步处理，下面只有前两种情况，只能是一个节点或者没有节点 //不管是否有子节点，都获取子节点 BSTNode<T> child; if (node.left != null) child = node.left; else child = node.right; //如果 child != null，就说明是有一个节点的情况 if (child != null) //将子节点和父节点关联上 child.parent = node.parent; //如果当前节点没有父节点（后继情况到这儿时一定有父节点） //说明要删除的就是根节点 if (node.parent == null) //根节点设置为子节点 //按照前面逻辑，根只有一个或者没有节点，所以直接赋值 child 即可 mRoot = child; else if (node == node.parent.left)//存在父节点，并且当前节点是左节点时 //将父节点的左节点设置为 child node.parent.left = child; else//右节点时 //将父节点的右节点设置为 child node.parent.right = child; //返回被删除的节点 return node; } //删除指定的值 public void delete(T key) { //获取要删除的节点 BSTNode<T> node = search(mRoot, key); //如果存在就删除 if (node != null) delete(node); } /* * 销毁二叉树 */ private void destroy(BSTNode<T> tree) { if (tree==null) return ; if (tree.left != null) destroy(tree.left); if (tree.right != null) destroy(tree.right); tree=null; } public void clear() { destroy(mRoot); mRoot = null; } /* * 打印"二叉查找树" * * key -- 节点的键值 * direction -- 0，表示该节点是根节点; * -1，表示该节点是它的父结点的左孩子; * 1，表示该节点是它的父结点的右孩子。 */ private void print(BSTNode<T> tree, T key, int direction) { if(tree != null) { if(direction==0) // tree是根节点 System.out.printf("%2d is root ", tree.key); else // tree是分支节点 System.out.printf("%2d is %2d's %6s child ", tree.key, key, direction==1?"right" : "left"); print(tree.left, tree.key, -1); print(tree.right,tree.key, 1); } } public void print() { if (mRoot != null) print(mRoot, mRoot.key, 0); } }