数据结构

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

文章中使用的动画网站地址: http://www.donghuasuanfa.com

树的前序，中序，后序遍历，主要是指的 根 节 点 \color{red}{根节点} 根节点的访问顺序。 前序代表先访问 根 节 点 \color{red}{根节点} 根节点，再访问左子树，最后访问右子树。 中序代表先访问左子树，再访问 根 节 点 \color{red}{根节点} 根节点，最后访问右子树。 后序代表先访问左子树，再访问右子树，最后访问 根 节 点 \color{red}{根节点} 根节点。 二叉树讲解图例如图1-1所示:

  步骤一：二叉树前序遍历过程为先访问根节点，然后再访问左子树，最后访问右子树。示例图中节点(6)为根节点。所以前序遍历为先遍历根节点(6)，再遍历左子树，最后遍历右子树。遍历过程如下图所示。

  步骤二：根节点遍历后，需要遍历左子树。将左子树判定为一颗独立的树。则节点(3)为左子树的根节点，所以再次访问的节点是左子树的根节点(3)。左子树遍历过程如下图所示。

  步骤三:左子树的根节点访问后，需要遍历左子树的左子节点(2)。访问如下图所示。   步骤四:左子树的左子树访问后，再访问左子树的右子节点，访问节点为(4) 。访问如下图所示。

  步骤五:右子树重复上述步骤 。下图只描述了右子树的遍历的第一步，剩下的步骤不再赘述。

  步骤一：二叉树中序遍历过程为先访问左子树，然后再访问根节点，最后访问右子树。示例图中最先访问左子树(3,2,4)，将左子树视为独立的树，则左子树包含左子树的根节点(3)，左子树的左节点(2),左子树的右节点(4)。所以左子树的中序遍历过程，优先遍历左子树的左子树节点(2)。   步骤二：左子树的左子树节点(2)访问过后，再访问左子树的根节点(3)。访问过程如下图所示：   步骤三：左子树的根节点(3)访问过后，最后访问左子树的右子树节点(4)。访问过程如下图所示：   步骤四：左子树遍历后，访问整体树的根节点(6)。访问过程如下图所示：   步骤五:右子树重复上述步骤 。下图只描述了右子树的遍历的第一步，剩下的步骤不再赘述。

  步骤一：二叉树后序遍历过程为先访问左子树，然后再访问右子树，最后访问根节点。示例图中最先访问左子树(3,2,4)，将左子树视为独立的树，则左子树包含左子树的根节点(3)，左子树的左节点(2),左子树的右节点(4)。所以左子树的后序遍历过程，优先遍历左子树的左子树节点(2)。   步骤二：左子树的左子树节点(2)访问过后，再访问左子树的右子节点(4)。访问过程如下图所示：   步骤三：左子树的右子树节点(4)访问过后，再访问左子树的根节点(3)。访问过程如下图所示：   步骤四：整体的树当左子树(3,2,4)访问后，再访问右子树，最后访问根节点(6)。       右子树的后序遍历过程同样是先右子树的左子树，右子树的右子树，最后右子树的根节点。所以右子树的优先遍历右子树的左子树(7,6)。       遍历树(7,6)同样按照规则。先遍历左子树(6)。所以第四步骤遍历的节点为(6)。 访问过程如下图所示：

  步骤五：右子树重复遍历规则 。后序遍历右子树的左子树(7,6)，由于子树(7,6)没有右子树节点，所以访问子树(7,6)的根节点(7)。下图只描述了右子树的左子树遍历下一步，剩下的步骤不再赘述。访问过程如下图所示：

1.从根节点开始比较。如果查找的几点小于节点，则继续在左子树中查找。如果查找的节点大于节点。则在右子树中查找。 2.如果节点值与查找的值相同。则返回该节点。

  步骤一:输入查找节点，查找的节点的值为4。

  步骤二:从根节点开始遍历，查找的节点4小于根节点，则在左子树中继续查找。   步骤三:递归遍历子树节点。下一步需要比较节点3和查找节点4.查找节点4大于节点3，则继续递归上述步骤,下图只描述了下一步骤，剩下的步骤不再赘述。

1.先执行查找操作，查询到插入节点的位置。 2.比较插入节点和树中的节点大小。如果插入节点小于树中结点，则将节点插入到树中结点的左节点。如果插入节点大于树中结点，则将节点插入到树中结点的右节点。

  步骤一:输入插入节点，插入节点的值为5。   步骤二:执行查找逻辑，查询插入节点5的插入位置。   步骤三:比较插入节点5和插入节点的值(4)，因为5大于4.所以将插入节点插入到节点(4)的右节点。

二叉树删除分为三个场景。 场景A:删除节点下无子节点。 场景B:删除节点下只有一个子节点。 场景C:删除节点下有俩个子节点。

此场景比较简单，所以只描述步骤和演示动画。

1.查找到删除节点。 2.删除此节点。

此场景比较简单，所以只描述步骤和演示动画。

1.查找到删除节点。 2.删除此节点。 3.将删除节点的子节点替换到删除节点。

1.查找到删除节点。 2.查找到删除节点的后继结点。 3.删除节点。 4.将后继节点替换到删除节点位置。

  步骤一:查找到删除节点的位置，示例为删除节点8，则先查询要删除的节点位置8。   步骤二:将节点8从树中删除。   步骤三:查找到删除节点的后继节点。   后继节点，将树中的所有节点映射到一条线上。删除节点的下一个节点为后继节点。

示例中的删除节点的后继节点为 9   步骤四:将后继节点(9)替换到删除节点(8)位置,删除结束。