二叉树

定义：

二叉树是一个连通的无环图，从根节点开始，每一个顶点的度不大于3（每一个节点的子节点不大于3），如下图所示。

树的结点（node）：包含一个数据元素及若干指向子树的分支；

孩子结点（child node）：结点的子树的根称为该结点的孩子；

双亲结点：B 结点是A 结点的孩子，则A结点是B 结点的双亲；

兄弟结点：同一双亲的孩子结点；堂兄结点：同一层上结点；

祖先结点: 从根到该结点的所经分支上的所有结点

子孙结点：以某结点为根的子树中任一结点都称为该结点的子孙

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

定义节点：

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

    public void show() {
        System.out.println("节点值：" + nodeData);
    }
}

定义的节点由三部分组成，一部分是节点值，一部分是左节点，一部分是右节点；这里很像链表，只不过这里是有两个指向。

二叉查找树：

二叉查找树是由节点构成的，所以我们通过上面的Node节点类来构建这颗二叉查找树。构建树采用的是从根节点开始，自上而下构建二叉树，如果插入的节点值大于父节点就放到父节点的左子树，否则放到该父节点的右子树。

构建树的过程也就是遍历树的过程，需要注意的是每次插入值首先要进行判空过程，如果父节点要是null，那么此时插入的新节点就直接放到父节点，如果父节点不是null，那么根据它的值来判断插到左节点还是右节点；还有，图的遍历必定涉及到循环，所以我们在构建树的时候采用的是while循环，只要要插入的节点不为null，那么我们就一直插入。

我们像集合一样来写树的生成，首先写一个节点的插入方法，代码如下：

public class TreeDemo {
    private Node root;

    public void insert(int iData) {
        Node newNode = new Node();
        newNode.nodeData = iData;
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (iData < current.nodeData) {
                    current = current.leftNode;
                    if (current == null) {
                        parent.leftNode = newNode;
                        return;
                    }
                } else {
                    current = current.rightNode;
                    if (current == null) {
                        parent.rightNode = newNode;
                        return;
                    }
                }
            }
        }
    }
}

构建完了树我们如果想查询树中的节点，那么我们需要写一个查询方法。查询方法也要进行树的遍历，首先从根节点开始，一个一个查找，规则就是小于父节点就找左节点，大于就找右节点。

public Node search(int key) {
    Node current = root;
    while (current.nodeData != key) {
        if (current.nodeData > key) {
            current = current.leftNode;
        } else {
            current = current.rightNode;
        }
        if (current == null)
            return null;
    }
    return current;
}

二叉树这么构建还有一个好处我们可以知道这棵树的最大值一定在最右面的节点，最小值一定在最左面的节点，我们也可以根据这个查询到树的极值情况。

完整测试代码：

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

    public void show() {
        System.out.println("节点值：" + nodeData);
    }
}
public class TreeDemo {
    private Node root;

    public void insert(int iData) {
        Node newNode = new Node();
        newNode.nodeData = iData;
        if (root == null) {
            root = newNode;
        } else {
            Node current = root;
            Node parent;
            while (true) {
                parent = current;
                if (iData < current.nodeData) {
                    current = current.leftNode;
                    if (current == null) {
                        parent.leftNode = newNode;
                        return;
                    }
                } else {
                    current = current.rightNode;
                    if (current == null) {
                        parent.rightNode = newNode;
                        return;
                    }
                }
            }
        }
    }

    public Node search(int key) {
        Node current = root;
        while (current.nodeData != key) {
            if (current.nodeData > key) {
                current = current.leftNode;
            } else {
                current = current.rightNode;
            }
            if (current == null)
                return null;
        }
        return current;
    }

    public Node maxValue() {
        Node maxNode = null;
        Node current = root;

        while (current != null) {
            maxNode = current;
            current = current.rightNode;
        }
        return maxNode;
    }

    public Node minValue() {
        Node minNode = null;
        Node current = root;
        while (current != null) {
            minNode = current;
            current = current.leftNode;
        }
        return minNode;
    }
}
public class TreeTest {
    public static void main(String[] args) {
        TreeDemo tree = new TreeDemo();
        tree.insert(10);
        tree.insert(4);
        tree.insert(15);
        tree.insert(3);
        tree.insert(7);
        tree.insert(9);
        Node node = tree.search(7);
        if (node == null) {
            System.out.println("树中没有该节点！");
        } else {
            node.show();
        }
        tree.maxValue().show();
        tree.minValue().show();
    }
}

完全二叉树：

首先说一下满二叉树，什么是满二叉树呢，如果一个二叉树，每一个非叶子节点均有两个子节点，那么我们可以叫这棵树为满二叉树，如图：

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树，如下图。

(1)所有的叶结点都出现在第k层或k-l层（层次最大的两层）

(2)对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+1。

它的遍历和上面的完全一样，这里就不在写了。

判断一棵树是否是完全二叉树的思路看以下几点：

1.如果树为空，则直接返回错

2.如果树不为空：层序遍历二叉树

（1）如果一个结点左右孩子都不为空，则pop该节点，将其左右孩子入队列；

（2）如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；

（3）如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；

平衡二叉树：

平衡二叉树（Balanced Binary Tree）是在二叉查找树的基础上来的，又叫AVL树。平衡二叉树要求对于每一个节点来说，它的左右子树的高度之差不能超过1，如果插入或者删除一个节点使得高度之差大于1，就要进行节点之间的旋转，将二叉树重新维持在一个平衡状态。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。详解点击这里

平衡查找树之2-3树