有序二叉树简介

有序二叉树

有序二叉树：左边的结点值小于当前结点，右边结点值大于当前结点。

有序二叉树结点模型

root表示指向根结点的指针。

构建有序二叉树

判断root是否为null

• root为空，root = node
• 如果 root 不为空，定义index 游标，初始值 == root 。判断index 和 node 结点值的大小

二叉树的遍历

广度优先遍历

从上到下遍历整棵树，同一层从左到右遍历每个结点。

遍历顺序：A B C D E F G H

借助底层使用链表的队列实现：

根结点入队，只要队列不是空，就从队列中一直拿取数据，并将结点的左右孩子入队。

深度优先遍历

先序遍历： 父 左 右。使用递归输出。A B D H E C F G

中序遍历：左 父 右。H D B E A F C G

后序遍历：左 右 父。H D E B F G C A

先序遍历：5 7 2 0 8 6 4 3 9 1

中序遍历：2 7 8 0 6 5 3 9 4 1

后序遍历：2 8 6 0 7 9 3 1 4 5

有序二叉树的删除

删除叶子结点

1. 找到要删除的结点 target

2. 找到要删除结点的父结点parent

   1. 如果没有父结点，而且本身就是叶子结点，则该树只有这一个结点，将root设置为空

   2. 如果有父结点，判断目标结点是父结点的右孩子还是左孩子。

      1. 如果是左孩子，则让parent的左孩子指针设为null，parent.left = null。

      2. 如果是右孩子，则让parent的右孩子指针设为null，parent.right = null。

删除只有一棵子树的结点

1. 找到要删除结点target

2. 找到要删除的结点的父结点parent

   1. 如果没有父结点

      1. 自己是根结点，且只有左子树。root直接指向左子树结点。root = root.left。绿色结点下面的结点不受波及，直接保留原状即可。

      2. 自己是根节点，且只有右子树。root直接指向右子树结点。root = root.right。绿色结点下面的结点不受波及，直接保留原状即可。

   2. 如果有父结点

      1. 如果目标结点是父结点的左孩子

         1. 如果目标有左子树：parent .left = target.left

         2. 如果目标有右子树：parent.right = target.right

      2. 如果目标结点是父结点的右孩子

         1. 如果目标有左子树：parent.right = target.left

         2. 如果目标有右子树：parent.left = target.right

删除有两棵子树的结点

找到左子树的最大值或者找右子树的最小值作为根结点，这两个找到任意一个即可，这两个都是叶子节点。

1. 找到要删除的节点

2. 找到目标节点左子树的最大值，或右子树的最小值

3. 目标节点左子树的最大值，或右子树的最小值，直接替换target的值

4. 删除替换的结点