如果将打印安排在同个数字第一次被访问时,即先序遍历
第二次即中序遍历
第三次即后序遍历
现二叉树的先序、中序、后序遍历，包括递归方式和非递归
方式
二叉树结构定义

public static class Node {
        public int value;
        public Node left;
        public Node right;

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

红黑树、AVL、替罪羊树、Treap、伸展树等。

二叉搜索树，二叉排序树）
它或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

完全二叉树(Complete Binary Tree)
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

/**
 * 是否为完全二叉树
 *
 * @param head
 * @return
 */
public static boolean isCBT(Node head) {
    if (head == null) {
        return true;
    }
    Queue queue =new LinkedList();
    boolean leaf = false;
    Node left,right;
    //开始时,将头加入队列
    queue.offer(head);
    while (!queue.isEmpty()) {
        //然后在队列中出队当前节点
        head = queue.poll();
        //拿到左右孩子
        left = head.left;
        right = head.right;
        //开启了叶节点的阶段 且 左/右孩子非空
        if ((leaf && (left != null || right != null)) || (left == null && right != null)) {
            return false;
        }
        if (left != null) {
            queue.offer(left);
        }
        if (right != null) {
            queue.offer(right);
        } else {
            leaf = true;
        }
    }
    return true;
}

二叉树层序遍历

ITPub博客

二叉树的常用算法

最新文章