二叉树

1. 简述

一个节点有不超过2个子节点，超过2个是多路树，不属于二叉树。

2. 二叉搜索树

左节点比根节点小，比根节点大的为右节点；

2.1 二叉搜索树的遍历

分为前序，中序和后序，使用最多的是中序；

前序 ： 根节点——->左节点———->右节点；

中序 ： 左节点——-> 根节点———>右节点；

后序 ： 左节点——> 右节点——–>根节点

示例代码：

Node.java

public class Node {
    public int data;
    public Node leftNode;
    public Node rightNode;

    public Node(int data) {
        this.data = data;
    }
}

BinarySearchTree.java

/**
 * 二叉搜索树（Binary Search Tree）
 * 要求是：若他的左子树不为null,则左子树上的所有节点的值均小于根节点；
 * 若右子树不为null，则右子树上的所有节点的值均大于根节点；
 */
public class BinarySearchTree implements ITree {

    //根节点
    private Node root;

    @Override
    public Node find(int key) {
        //查找节点
        Node current = root;
        if(root.data == key){//如果刚好是根节点
            return root;
        }else{
            while(current != null){
                if(current.data > key){
                    //当前节点比查找值大，要去左测节点查找
                    current = current.leftNode;
                }else if(current.data == key){
                    return current;
                }else{
                    current = current.rightNode;
                }
            }
        }
        return null;
    }

    public Node getRoot(){
        return root;
    }
    @Override
    public boolean insert(int key) {
        //要插入新的节点
        Node newNode = new Node(key);
        //如果没有根节点
        if(root == null){
            root = newNode;
            return true;
        }else{
            //如果有根节点，需要判断与根节点的比较大小
            Node current = root;
            Node parentNode = null;
            while(current!=null){
                parentNode = current;
                if(current.data > key){
                    //当前值比插入值大，需要搜索左节点
                    current = current.leftNode;
                    if(current == null){
                        parentNode.leftNode = newNode;
                        return true;
                    }
                }else{
                    //找右节点
                    current = current.rightNode;
                    if(current == null){
                        parentNode.rightNode = newNode;
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //前序
    @Override
    public void preOrder(Node current) {
        //前序是：根节点-左节点-右节点
        //默认从顶部进行遍历
        if(current!= null){
            System.out.println(current.data);
            preOrder(current.leftNode);
            preOrder(current.rightNode);
        }
    }
	//中序
    @Override
    public void middleOrder(Node current) {
        //中序：左节点-根节点-右节点 , 中序是最常用的
        if(current!=null){
            middleOrder(current.leftNode);
            System.out.println(current.data);
            middleOrder(current.rightNode);
        }
    }

    //后序
    @Override
    public void postOrder(Node current) {
        //后序：左节点-右节点-根节点
        postOrder(current.leftNode);
        postOrder(current.rightNode);
        System.out.println(current.data);
    }

    //查找最小值
    @Override
    public Node findMin() {
        //从根节点开始查找
        Node currentNode = root;
        while(currentNode != null){
            if(currentNode.leftNode == null){
                return currentNode;
            }
            currentNode = currentNode.leftNode;
        }
        return currentNode;
    }

    @Override
    public Node findMax() {
        //一直寻找右节点
        Node currentNode = root;
        Node maxNode = currentNode;
        while (currentNode!=null){
            maxNode = currentNode;
            currentNode = currentNode.rightNode;
        }
        return maxNode;
    }

    //删除节点(最简单的做法是给节点加一个属性isDelete)
    /**
     * 1.该节点没有子节点
     * 2.该节点只有1个子节点
     * 3.该节点有2个节点（最复杂）
     */
    @Override
    public boolean delete(int deleteKey) {
        //要删除节点首先要找到删除节点的父节点
//        Node currentNode = root;
//        Node parentNode = currentNode;
//        boolean isLeftNode = false;
//        while(currentNode != null){
//            parentNode = currentNode;
//            if(currentNode.data > deleteKey){
//                isLeftNode = true;
//                currentNode = currentNode.leftNode;
//            }else{
//                isLeftNode = false;
//                currentNode = currentNode.rightNode;
//            }
//        }

        return false;
    }

Test.java

BinarySearchTree binarySearchTree = new BinarySearchTree();
binarySearchTree.insert(30);
binarySearchTree.insert(25);
binarySearchTree.insert(20);
binarySearchTree.insert(31);
binarySearchTree.middleOrder(binarySearchTree.getRoot());