二叉树 是一种特殊的“树”结构，它每个节点最多有两个子树。

树

树 是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树跟图的区别就在于，树是有 层次结构 的。

树与图.png

树中只有子节点，没有父节点的节点是 根节点；既有父节点，又有子节点的节点是普通的节点；只有父节点，没有子节点的节点，是 叶子节点。

二叉树

二叉树 就是每个节点最多有两个子树(子节点)的树：

二叉树、满二叉树、完全二叉树.png

满二叉树： 叶子节点全部都在最底层，除了叶子节点，每个节点都有左右两个子节点的二叉树。
完全二叉树：叶子节点只有最下面两层，最下层叶子节点全都靠左排列，除了最后一层的叶子节点意外其他任何一层的节点都是满的，这样的二叉树。

二叉树存储方式

二叉树可以使用链表来实现，也可以使用数组来实现，这两种存储方式各有各的优缺点。

链式存储

链式存储的二叉树.png

二叉树使用链式存储，每一个节点都需要包含三部分的内容：本节点的值、左子节点指针、右子节点指针。这种方式只要知道父节点，就能依次找到该节点的子节点。这种链式存储的方式每个节点需要包含这三部分，所以会浪费一定的存储空间，但是实现起来很容易，对于内存空间的使用比较灵活。

顺序存储

使用数组进行顺序存储.png

二叉树使用顺序存储，需要使用一个数组。由于数组是一个连续的存储空间，所以，数组的下标是连续的，且可以计算出来的。这样就免去了链式存储中每个节点都需要记录子节点指针的空间，每个节点只需要记录自己的值就可以了。

从图中的值可以看出来，假设父节点的存储位置设为i，那么，左子节点位置 = 2 × i；右子节点位置 = 2 × i + 1。这样我们就可以通过下标计算来计算出来各个节点的位置了。

另外，如图，如果二叉树不是完全二叉树的话，那么图中的G点(怪怪的感觉😂)就不存在，那么右边的存储数组的第6个位置就会不存储任何东西，这样的话，造成了数组存储的离散，导致空间浪费。如果这样的情况多了，空间就会浪费的多的多。所以如果最后一排叶子节点都靠左排列，即二叉树为完全二叉树的时候，空间才会是最省的，所以完全二叉树的概念并不是没有用的。

二叉树遍历

要想从头到尾将二叉树遍历完全，可以有很多种方式。先、中、后序遍历(深度优先)；层次遍历(广度优先)……层次遍历的话可以采用一个队列来实现，这个在广度优先算法一篇写过了。深度优先的话，可以有三种遍历的方式：先序遍历、中序遍历、后序遍历。

二叉树三种遍历方式.png

这三种遍历方式就是跟节点的区别在于对于每个节点的访问逻辑顺序不同，都是利用递归(非递归先不考虑)来进行访问：

先序遍历：①打印父节点 => ②访问父节点的左子节点 => ③访问父节点的右子节点
中序遍历：①访问父节点的左子节点 => ②打印父节点 => ③访问父节点的右子节点
后序遍历：①访问父节点的左子节点 => ②访问父节点的右子节点 => ③打印父节点

所谓的前中后，指的是打印父节点值的时机。先序遍历是先打印父节点，然后递归访问父节点的左子节点，然后再递归访问父节点的右子节点……

算法实现

# -*- coding: utf-8 -*-
# @Time    : 2019-03-25 16:41
# @Author  : Jaedong
# @Version : 3.6
# @File    : TraversingBinaryTree.py
# @Software: PyCharm


class Node:
    value = ''
    leftNode = None
    rightNode = None

    def __init__(self, value, leftNode, rightNode):
        self.value = value
        self.leftNode = leftNode
        self.rightNode = rightNode

# 先序遍历就是：根节点->左子树->右子树
def preorder_traversal(root):
    if root == None:
        return

    print(root.value)
    preorder_traversal(root.leftNode)
    preorder_traversal(root.rightNode)

# 中序遍历就是：左子树->根节点->右子树
def inorder_traversal(root):
    if root == None:
        return

    inorder_traversal(root.leftNode)
    print(root.value)
    inorder_traversal(root.rightNode)

# 后序遍历就是：左子树->右子树->根节点
def postorder_traversal(root):
    if root == None:
        return

    postorder_traversal(root.leftNode)
    postorder_traversal(root.rightNode)
    print(root.value)


# 简单粗暴，先来一棵二叉树
node_d = Node('D', None, None)
node_e = Node('E', None, None)
node_b = Node('B', node_d, node_e)
node_f = Node('F', None, None)
node_c = Node('C', None, node_f)
root = Node('A', node_b, node_c)

print('先序遍历：')
preorder_traversal(root)
print('中序遍历：')
inorder_traversal(root)
print('后序遍历：')
postorder_traversal(root)

结果是：

三种遍历结果.png

上一篇：写给媳妇儿的算法（十四）——动态规划
下一篇：写给媳妇儿的算法（十六）——二叉查找树