数据结构-树

1.二叉树

public class TreeDemo {
    //二叉树节点类
    private static class TreeNode{
        private int data;
        private TreeNode leftNode;
        private TreeNode rightNode;

         TreeNode(int data) {
            this.data = data;
        }
    }

    /**
     * @param inputList 构建树的序列
     * @return
     */
    private TreeNode createTree(LinkedList<Integer> inputList){
        if (inputList==null||inputList.isEmpty()){
            return null;
        }
        TreeNode node=null;
        Integer data = inputList.removeFirst();

        while (data!=null){
            node = new TreeNode(data);
            node.leftNode = createTree(inputList);
            node.rightNode=createTree(inputList);
            if (inputList.isEmpty()){
                break;
            }
        }
        return node;
    }

    /**前序遍历
     * @param node
     * @return
     */
    private void preTraveral(TreeNode node){
        if (node==null){
            return;
        }
        System.out.print(node.data+"\t");
        preTraveral(node.leftNode);
        preTraveral(node.rightNode);
    }

    /**中序遍历
     * @param node
     */
    private void inTraveral(TreeNode node){
        if (node==null){
            return;
        }
        inTraveral(node.leftNode);
        System.out.print(node.data+"\t");
        inTraveral(node.rightNode);
    }

    private void postTraveral(TreeNode node){
        if (node==null){
            return;
        }
        postTraveral(node.leftNode);
        postTraveral(node.rightNode);
        System.out.print(node.data+"\t");
    }

    public static void main(String[] args) {
        TreeDemo treeDemo = new TreeDemo();
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10, null, null, 8, null, 4}));
        TreeNode tree = treeDemo.createTree(inputList);
        System.out.println("前序");
        treeDemo.preTraveral(tree);
        System.out.println("\n"+"中序");
        treeDemo.inTraveral(tree);
        System.out.println("\n"+"后序");
        treeDemo.postTraveral(tree);

    }
}

2.二叉查找树（binary search tree）bs Tree

特点：

• 如果左子树不为空，则左子树上所有节点的值均小于根节点的值
• 如果右子树不为空，则右子树上所有节点的值均大于根节点的值
• 左右子树都是二叉查找树

缺点：
可能出现极端情况

解决方案：
使用其他自平衡的树

3.AVL树

4.红黑树

5.BTree

6.B+Tree

6.树堆