树

二叉树的建立

public class TreeNode {

    public TreeNode left;
    public TreeNode right;
    public int value;
    public TreeNode next;
}

public class 二叉树的建立 {

    private static int counter = 0;//定义一个静态计数变量

    public static void main(String[] args) {
        int[] a = {1, 2, 3, 0, 0, 4, 0, 0, 5, 0, 0};
        createBiTree(a);
    }

    public static TreeNode createBiTree(int[] a) {
        TreeNode root = new TreeNode();
        createBiTree(root, a, counter);
        return root;
    }

    /**
     * 构造二叉树
     *
     * @param root 根节点
     * @param a    数据源
     * @param i    计数器
     * @return 根节点
     */
    private static TreeNode createBiTree(TreeNode root, int[] a, int i) {
        if (i < a.length) {
            if (a[i] == 0) {
                root = null;
            } else {
                TreeNode left = new TreeNode();
                TreeNode right = new TreeNode();
                root.left = createBiTree(left, a, ++counter);
                root.right = createBiTree(right, a, ++counter);
                root.value = a[i];
            }
        }
        return root;
    }
}

建立二叉树，利用了递归的原理，也就是在打印二叉树的前中后序遍历算法中打印结点的地方，改成了生成结点，给结点赋值的操作而已。

二叉树的遍历

二叉树前中后序遍历

public class 二叉树前中后遍历 {

    static void recursionPreoderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.value + " ");
        recursionPreoderTree(root.left);
        recursionPreoderTree(root.right);
    }

    static void recursionInoderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        recursionInoderTree(root.left);
        System.out.print(root.value + " ");
        recursionInoderTree(root.right);
    }

    static void recursionPostorderTree(TreeNode root) {
        if (root == null) {
            return;
        }
        recursionPostorderTree(root.left);
        recursionPostorderTree(root.right);
        System.out.print(root.value + " ");
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
        TreeNode root = 二叉树的建立.createBiTree(a);
        recursionPreoderTree(root);
        System.out.println();
        recursionInoderTree(root);
        System.out.println();
        recursionPostorderTree(root);
    }
}

二叉树层序遍历(广度优先)

public class 二叉树层序遍历 {

    static void levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(root);

        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();

            System.out.print(current.value + " ");
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
        TreeNode root = 二叉树的建立.createBiTree(a);
        levelOrder(root);
    }
}

用队列，每次遍历当前节点的时候，把该节点从队列拿出来，并且把它的子节点全部加入到队列中

题目

设置二叉树的next节点

public class 二叉树的next结点 {

    static void nextSiblings(TreeNode treeNode) {

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.add(treeNode);

        //这个level没有实际用处，但是可以告诉大家怎么判断当前node是第几层。
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {

                TreeNode current = queue.poll();
                System.out.print(current.value + " ");

                if (current.left != null) {
                    queue.offer(current.left);
                }
                if (current.right != null) {
                    queue.offer(current.right);
                }

                if (i != size - 1) {
                    current.next = queue.peek();
                }
            }
            level++;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
        TreeNode root = 二叉树的建立.createBiTree(a);
        nextSiblings(root);
    }
}

其实这个题目就是典型的层序遍历，使用队列就可以轻松解决，每次poll出来一个节点，判断是不是当前层的最后一个，如果不是，把其next设置成queue中的下一个节点就ok了。至于怎么判断当前节点是哪一层呢？使用当前queue的size做for循环。

翻转二叉树

public class 翻转二叉树 {

    static TreeNode reverseBinaryTree(TreeNode root) {
        if (root == null) {
            return null;
        } else {
            //左子树已翻转好
            TreeNode left = reverseBinaryTree(root.left);
            //右子树已翻转好
            TreeNode right = reverseBinaryTree(root.right);
            //交换左右子树
            root.right = left;
            root.left = right;
            return root;
        }
    }

}

分而治之 和 递归 的思想

铺平二叉树

public class 铺平二叉树_链表 {

    static TreeNode inflateBinaryTree(TreeNode root) {

        if (root == null) {
            return root;
        }

        //用递归的思想，把左右先铺平
        TreeNode left = inflateBinaryTree(root.left);
        TreeNode right = inflateBinaryTree(root.right);

        //把左指针和右指针先指向空。
        root.left = null;
        root.right = null;

        //假如左子树生成的链表为空，那么忽略它，把右子树生成的链表指向根节点的右指针
        if (left == null) {
            root.right = right;
            return root;
        }

        //如果左子树生成链表不为空，那么用while循环获取最后一个节点，并且它的右指针要指向右子树生成的链表的头节点
        root.right = left;
        TreeNode lastLeft = left;
        while (lastLeft.right != null) {
            lastLeft = lastLeft.right;
        }
        lastLeft.right = right;
        return root;
    }

    public static void main(String[] args) {
        int[] a = {1, 2, 0, 4, 0, 0, 3, 0, 0};
        TreeNode root = 二叉树的建立.createBiTree(a);
        inflateBinaryTree(root);
    }

}

android的findViewById

View searchViewById(ViewGroup viewGroup, int id) {

        if (viewGroup == null) {
            return null;
        }

        int childCount = viewGroup.getChildCount();
        for (int i = 0; i < childCount; i++) {
            View view = viewGroup.getChildAt(i);
            if (view.getId() == id) {
                return view;
            }

            if (view instanceof ViewGroup) {
                View temp = searchViewById((ViewGroup) view, id);
                if (temp != null) {
                    return temp;
                }
            }
        }
        return null;
    }

线索二叉树

中序线索化二叉树

public class 中序线索化二叉树 {

    private Node preNode;   //线索化时记录前一个节点

    //节点存储结构
    static class Node {
        String data;        //数据域
        Node left;          //左指针域
        Node right;         //右指针域
        boolean isLeftThread = false;   //左指针域类型  false：指向子节点、true：前驱或后继线索
        boolean isRightThread = false;  //右指针域类型  false：指向子节点、true：前驱或后继线索

        Node(String data) {
            this.data = data;
        }
    }

    /**
     * 通过数组构造一个二叉树（完全二叉树）
     *
     * @param array
     * @param index
     * @return
     */
    static Node createBinaryTree(String[] array, int index) {
        Node node = null;

        if (index < array.length) {
            node = new Node(array[index]);
            node.left = createBinaryTree(array, index * 2 + 1);
            node.right = createBinaryTree(array, index * 2 + 2);
        }

        return node;
    }

    public static void main(String[] args) {
        String[] array = {"A", "B", "C", "D", "E", "F", "G", "H"};
        Node root = createBinaryTree(array, 0);

        中序线索化二叉树 tree = new 中序线索化二叉树();
        tree.inThreadOrder(root);
    }

    private void inThreadOrder(Node root) {

        inThreadOrder(root.left);

        //左指针为空，将指针指向刚才访问过的结点
        //若preNode为null，则当前结点时第一个结点
        if (root.left == null) {
            root.isLeftThread = true;
            root.left = preNode;
        }

        // 前一个结点的后继结点指向当前结点
        // 当前结点的后继点只能由父节点指定
        if (preNode != null && preNode.right == null) {
            preNode.isRightThread = true;
            preNode.right = root;
        }

        preNode = root;

        inThreadOrder(root.right);

    }

}

和二叉树中序遍历的递归代码几乎完全一样。只不过将本是打印的结点的功能改成了线索化的功能。