BinaryTree
二叉树是一种数据结构，在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
CharacteristicsOfBinaryTree

  • 每个结点最多有两颗子树。
  • 左子树和右子树次序不能任意颠倒。
  • 即使树中某结点度为1（只有一棵子树），也要区分它是左子树还是右子树。

NatrueOfBinaryTree

  • 在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
  • 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）

FullBinaryTree

  • 在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

CompleteBinaryTree

  • 对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

BinaryTreeTraverse

  • PreOlderTraverse （先根次序遍历）（前序遍历）

  • InOlderTraverse （中根次序遍历）（对称序列）

  • PostOlderTraverse （后根次序遍历）
    图片来自网络
    ProOlderTraverse
    先根次序遍历二叉树：第一次到达节点就输出节点数据，从根节点开始，并按照先左后右的原则依次进行，即首先从根节点1出发，输出1的节点数据后向左访问，到达2节点，输出2节点数据后，继续向左访问4,8,节点并输出数据，因为8为该二叉树的叶子，向下没有分支，所以返回4，因为4已经进行过输出，因此4不再进行输出，并且向右进行访问9,并进行输出数据，紧接着是5,10,11,3,6,7。

    整个二叉树遍历顺序是1，2,4,8,9,5,10,11,3,6,7。

    InOlderTraverse
    中根次序遍历二叉树：第二次达到节点就输出节点数据，依然遵循先左后右的原则，从根节点开始向左进行访问，因为1是第一次访问，因此不输出1的数据，紧接着2,4也依然不进行输出，4向左进行访问8后，8向左进行访问到NULL因此由NULL返回8，此时8为第二次访问并进行输出，然后返回4,并且输出4，接着是9,2,10,5,11,1,6,3,7。
    整个二叉树的遍历顺序是8,4,9,2,10,5,11,1,6,3,7。
    PostOlderTraverse
    后根次序遍历二叉树：第三次到达节点就输出节点数据，同样遵循先左后右的原则，从根节点开始想左进行访问，先是1,2,4进行访问但不输出数据，接着向左访问8,8继续向左进行访问，此时访问到NULL所以返回进行向右访问，同样访问到NULL后再次返回8，此时是第三次访问，因此输出8的数据，接着返回4再向右访问9，同8一样输出9后返回4，之后根据规则进行相同的操作。
    整个二叉树的遍历顺序是8,9,4,10,11,5,2,6,7,3,1。
    根据访问次序还原二叉树
    已知先跟次序遍历二叉树的序列和中根次序遍历二叉树的序列可以还原二叉树。
    已知中根次序遍历二叉树的序列和后跟次序遍历二叉树的序列可以还原二叉树。

    注：已知先根次序遍历二叉树的序列和后跟次序遍历二叉树的序列不可以还原二叉树。