4.二叉树

1. 有序数组插入数据和删除数据太慢，链表查找数据太慢，而树就结合这两点之间的优势。

树：

根：树最上面的节点称为根节点
父节点：节点向上连接到另外一个节点，那么这个顶点称为父节点
子节点：反之，该节点称为该节点的子节点

二叉树：树的每一个节点最多只能有两个子节点的树

代码实现：

class Node1 {

   public Node1(Integer id, String name) {
       this.id = id;
       this.name = name;
   }

   private Integer id;

   private String name;

   private Node1 left;

   private Node1 right;

   public Integer getId() {
       return id;
   }

   public void setId(Integer id) {
       this.id = id;
   }

   public String getName() {
       return name;
   }

   public void setName(String name) {
       this.name = name;
   }

   public Node1 getLeft() {
       return left;
   }

   public void setLeft(Node1 left) {
       this.left = left;
   }

   public Node1 getRight() {
       return right;
   }

   public void setRight(Node1 right) {
       this.right = right;
   }

   @Override
   public String toString() {
       return "Node1{" +
               "id=" + id +
               ", name='" + name + '\'' +
               ", left=" + left +
               ", right=" + right +
               '}';
   }
}

public class MyTwoTree {
   public void insert(Integer id, String name) {
       Node1 n1 = new Node1(id, name);
       Node1 current = root;
       Node1 parent;
       if (root == null) {
           root = n1;
       } else {
           while (true) {
               parent = current;
               if (current.getId() > id) {
                   current = current.getLeft();
                   if (current == null) {
                       parent.setLeft(n1);
                       return;
                   }
               } else {
                   current = current.getRight();
                   if (current == null) {
                       parent.setRight(n1);
                       return;
                   }
               }
           }
       }
   }

   public Node1 find(Integer id) {
       Node1 current = root;
       while (!id.equals(current.getId())) {
           if (current.getId() > id) {
               current = current.getLeft();
           } else {
               current = current.getRight();
           }
           if (current == null) {
               return null;
           }

       }
       return current;
   }
}

2 遍历

(1)前序遍历
先访问树的顶点，再依次访问左节点，右节点

    /**
     * 前序遍历
     *
     * @param node
     */
    public void forntSort(Node1 node) {
        if (node != null) {
            System.out.println(node.getId() + ":" + node.getName());
            forntSort(node.getLeft());
            forntSort(node.getRight());
        }
    }

(2) 中序遍历
先左节点再顶点再右节点，遍历结果是从小到大依次排序的

    /**
     * 中序遍历
     *
     * @param node
     */
    public void inSort(Node1 node) {
        if (node != null) {
            inSort(node.getLeft());
            System.out.println(node.getId() + ":" + node.getName());
            inSort(node.getRight());
        }
    }

(3)后序遍历

   /**
    * 后序遍历
    *
    * @param node
    */
   public void laterSort(Node1 node) {
       if (node != null) {
           laterSort(node.getLeft());
           laterSort(node.getRight());
           System.out.println(node.getId() + ":" + node.getName());

       }
   }

3 删除节点

public boolean delete(Integer id) {
        //引用当前节点，从根节点开始
        Node1 current = root;

        //应用当前节点的父节点
        Node1 parent = root;
        //是否为左节点
        boolean isLeftChild = true;

        while (!id.equals(current.getId())) {
            parent = current;
            //进行比较，比较查找值和当前节点的大小
            if (current.getId() > id) {
                current = current.getLeft();
                isLeftChild = true;
            } else {
                current = current.getRight();
                isLeftChild = false;
            }
            //如果查找不到
            if (current == null) {
                return false;
            }
        }

        //删除叶子节点，也就是该节点没有子节点
        if (current.getLeft() == null && current.getRight() == null) {
            if (current == root) {
                root = null;
            } else if (isLeftChild) {
                parent.setLeft(null);
            } else {
                parent.setRight(null);
            }
        } else if (current.getRight() == null) {
            if (current == root) {
                root = current.getLeft();
            } else if (isLeftChild) {
                parent.setLeft(current.getLeft());
            } else {
                parent.setRight(current.getLeft());
            }
        } else if (current.getLeft() == null) {
            if (current == root) {
                root = current.getRight();
            } else if (isLeftChild) {
                parent.setLeft(current.getRight());
            } else {
                parent.setRight(current.getRight());
            }
        } else {
            Node1 inRep = getInRep(current);
            if (current == root) {
                root = inRep;
            } else if (isLeftChild) {
                parent.setLeft(inRep);
            } else {
                parent.setRight(inRep);
            }
            inRep.setLeft(current.getLeft());
        }

        return true;
    }