目录

• 目录
• 二叉树的遍历方式
  • 非递归实现 三种深度优先遍历(先序,中序,后序)
  • 层序遍历
• 二叉树的种类
• 普通的二叉树
• 完全二插树
  • 大顶堆和小顶堆
  • 完全二叉树的存储方式
  • 完全二叉树的特征
• 二叉搜索树
• 平衡二叉树
  • AVL树

二叉树的遍历方式

1. 深度优先遍历
   • 先序遍历: 先根节点, 再左孩子, 之后右孩子
   • 中序遍历: 先左孩子, 在根节点, 之后右孩子
   • 后序遍历: 先左孩子, 再右孩子, 最后根节点
2. 广度优先遍历
   • 层序遍历:
     • 如果二叉树的实现的数据结构是TreeNode这种结构,则通过一个队列, 先将第一层的结点加入到队列中, 之后从队列中出队一个元素(根节点), 不断将它的孩子节点添加到队列中,然后再从队列中出队一个元素.
     • 如果实现方式是(完全二叉树)数组, 则直接顺序遍历数组即可, 自然就是层序遍历.

非递归实现 三种深度优先遍历(先序,中序,后序)

算法思想

1. 首先创建一个栈, 用于保存, 上一次保存上一次先序遍历时处理的结点.
2. 设置一个循环, 循环条件是, curr 为 null, 或者栈不为空.
3. 首先初始化 curr 为 根节点,然后进入循环, 判断current 是否为null. 如果不为null 则进行遍历 (先序遍历), 之后将该结点加入到栈.然后 将curr 修改为 当前结点 的 左孩子.如果 curr 一直不为null,则一直遍历, 直到第一次为null.则这颗二叉树的 最左边的分支的先序遍历完了, 需要进行遍历上一个遍历结点的右孩子.
4. 因为curr 为null, 但是栈不为空. 因此会进行循环, 然后进如到 curr为 null时的分支.这个分支 专门用于处理 右孩子节点.
5. 处理右孩子时 分为三种情况, 三种情况分为两类
   • 一类是: 右孩子 处理完成 - 当右孩子为 null 时, 则右孩子已经处理完毕, 此时应在 出栈父节点前, 输出 父节点. 出栈父节点后 输出子节点. - 当右孩子不为 null , 并且上次访问的就是右孩子, 此时直接出栈父节点即可,
   • 一类是: 由孩子没有处理完成, 此时设置curr为当前栈顶元素的右孩子,进入处理.

代码实现

public static <E> void  traversal3(TreeNode<E> root){
        Stack<TreeNode<E>> stack = new Stack<>();
        TreeNode<E> curr = root;
        TreeNode<E> pop = null;
        while(curr != null || !stack.isEmpty()){
            if(curr != null){
                //先序遍历输出
                System.out.println("先序: "+curr.value);
                stack.push(curr);
                curr = curr.left;
            }else {
                TreeNode<E> peek = stack.peek();
                //右结点为空 (处理过)
                if(peek.right == null){
                    System.out.println("中序: "+ peek.value);
                    pop = stack.pop();
                    System.out.println("后序: "+ pop.value);
                }
                //右结点 处理过
                else if(peek.right == pop){
                    pop = stack.pop();
                    System.out.println("后序: "+ pop.value);
                }
                //右结点, 没有处理过, 进行处理,
                else{
                    //这里的中序, 输出的是, 存在右孩子的节点
                    // 因为马上要处理右孩子了, 因为中序遍历 要在 右孩子之前先打印 父节点.
                    // 否则当右孩子处理时, 它的中序遍历会先输出
                    System.out.println("中序: "+ peek.value);
                    curr = peek.right;
                }
            }
        }
    }

层序遍历

层序遍历就是 依次遍历每一层的结点. 属于广度优先遍历. 针对这颗树的层序遍历的顺序就是: 1,2,3,4,5,6,,7,8,9

算法思想

代码的遍历逻辑就是借助一个队列来实现, 首先将根节点加入到队列中, 然后从队列头中依次取出结点, 之后将每一个结点的左右孩子添加到队列中, 之后取出下一个队列头元素, 按照这个顺序,就是层序遍历的顺序.

代码实现

/
  层序遍历, 需要借助队列实现.
  将每个结点的左右孩子, 添加到队列里面, 然后从队列中取元素
 /
public static List<Integer> layerTraversal(TreeNode root){
    if(root == null) return null;
    List<Integer> result = new ArrayList<>();
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        for (int i = 0; i < size; i++) {
            TreeNode poll = queue.poll();
            result.add(poll.getVal());
            if (poll.getLeft() != null){
                queue.add(poll.getLeft());
            }
            if (poll.getRight() != null){
                queue.add(poll.getRight());
            }
        }
    }
    return result;
}

二叉树的种类

1. 普通的二叉树
2. 完全二叉树
3. 二叉搜索树
4. 平衡二叉树

普通的二叉树

普通的二叉树, 就是一个根节点,最多有两个左右孩子的二叉树

完全二插树

一颗完全二叉树是指, 除了最底层之外, 每一层都被完全的填满, 如果最底层不满, 则需要从左到右填满, 另外, 对于任意一个结点, 它的左子树都比右子树高(或者相等).

大顶堆和小顶堆

1. 大顶堆和小顶堆都是指在堆排序中定义的一种数据结构。它们都是一种特殊的完全二叉树.
2. 大顶堆要求每个节点的值都大于等于它的子节点的值，也就是说堆顶元素是整个堆中最大的元素.
3. 而小顶堆要求每一个节点的值都要小于等于它的子节点的值, 也就是说堆顶元素时整个对重最小的元素.

建堆算法

有两种创建堆的算法:

• 依次遍历每一个数组值,然后一个个的插入到树中. 时间复杂度O(n * logN)
• 弗洛伊德建堆算法: 找到第一个非叶子结点, 然后从这个节点开始从后往前,对每一个元素,执行down算法, 时间负责度O(logN)

弗洛伊德建堆算法

public void makeHeap(int[] array) {
    int first = (size - 1)/2;
    for(int i = first; i>=0;i--){
        down(i);
    }
}

下沉算法(down)

public void down(int parent) {
    int left = parent * 2 + 1;
    int right = left + 1;
    int max = parent;
    if(left < size && array[left] > array[max]){
        max = left;
    }
    if(right < size && array[right] > array[max]){
        max = right;
    }
    if(max != parent){
        swap(array,max,parent);
        down(max);
    }
}

上浮算法

public void up(int newValue) {
    int child = size;
    while(child > 0){
        int parent = (child - 1) / 2;
        if(array[parent] < newValue){
            swap(array,parent,child);
            child = parent;
        }else{
            break;
        }
    }
    array[child] = newValue;
}

完全二叉树的存储方式

完全二插树可以存储在一个一维的数组中, 每一层的结点从左到右顺序的排列在数组里面

完全二叉树的特征

二叉搜索树

定义: 根节点的左孩子的key小于根节点,而右孩子大于根节点的树.

平衡二叉树

定义: 在二叉搜索树的基础上,加入了自动平衡功能的树. 这种树的实现之一是 AVL树.

AVL树

1. 定义:AVL树, 被AV和L开头的两个人发明.所以叫做AVL树, 特点是:左右孩子的高度差最大不会超过1.

2. 失衡:当左右节点的高度差大于1时, 这个节点就失衡了, 对于AVL来说,我们需要调整.

3. 平衡因子:左子树与右子树的高度的差值. 当平衡因子的绝对值大于1时, 就失衡了, 平衡因子为负数时, 表明是右子树的高度大于左子树, 当平衡因子为正数时, 则表明左子树的高度大于右子树.

AVL树不平衡时的四种情况

1. LL树: 左子树高度大于右子树.且左子树的左右孩子中, 右孩子的高度不大于左子树.

2. LR树: 左子树高度大于右子树.且左子树的左右孩子中, 右孩子的高度大于左子树.

3. RR树: 左子树高度小于右子树.且右子树的左右孩子中, 左孩子的高度不大于右子树.

4. RL树: 左子树高度小于右子树.且右子树的左右孩子中, 左孩子的高度大于右子树.

对于四种情况的平衡方式.

1. LL树: 对失衡节点的左孩子进行一次右旋
2. LR树: 对失衡节点的左孩子先进行一次左旋,之后再进行一次右旋.
3. RL树: 对失衡节点的右孩子先进行一次右旋,之后再进行一次左旋.
4. RR树: 对失衡节点的右孩子进行一次左旋.