二叉树（一）-基础知识

0.前言

一直以来都在做Android开发，感觉算法这些都不是很好，所以准备从基本的数据结构开始学习，也相当于自己的学习笔记吧。

1.什么是二叉树

二叉树是树的一种，每个节点最多可具有两个子树，即结点的度最大为2（结点度：结点拥有的子树数）。

例：

二叉树.png

2.二叉树的种类

2.1 斜树

所有结点都只有左子树，或者右子树。

左斜树.png

2.2 满二叉树

所有的分支节点都具有左右节点。

满二叉树.png

2.3 完全二叉树

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

完全二叉树与非完全二叉树.png

3.二叉树的一些性质

1. 二叉树第i层上的结点数目最多为 2^(i-1) (i≥1)
2. 深度为h的二叉树至多有2^h-1个结点(h≥1)
3. 包含n个结点的二叉树的高度至少为log2 (n+1)
4. 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1

4.二叉树的遍历方式

二叉树的遍历方式，一般分为前序遍历，中序遍历，后续遍历，层次遍历。

前、中、后序遍历是针对中间（父亲）节点来说的，如前序遍历，即先遍历中间（父亲）节点；中序遍历，就是第二个遍历中间（父亲）节点。这么说也许还是有点抽象，下面就举个栗子吧。

image.png

• 前序遍历(中-左-右):1-2-4-8-9-5-10-3-6-7
• 中序遍历:(左-中-右):8-4-9-2-10-5-1-6-3-7
• 后序遍历(左-右-中):8-9-4-10-5-2-6-7-3-1

层次遍历就更简单了，也就是逐层遍历，接着上面例图，它的层次遍历结果为:1-2-3-4-5-6-7-8-9-10。值得一提的是，二叉树的层次遍历其实是利用了队列这个数据结构来实现的。

光谈理论总觉得差点什么，让人提不起兴趣。接下来就看看各个遍历方法如何用代码实现吧。正好最近在python，所以以下代码均为python实现。
不过在此之前，我们还是看看如何来创建一棵二叉树吧.

4.1 二叉树的创建

class node:
    def __init__(self, k=None, l=None, r=None) -> None:
        super().__init__()
        self.key = k
        self.left = l
        self.right = r


# 生成二叉树
def createBinaryTree():
    key = input("enter a value(# is the end of a leaf):")
    if key is "#":
        root = None
    else:
        root = node(key, createBinaryTree(), createBinaryTree())
    return root

首先定义了一个node类，只有三个属性，key表示键值，left表示左孩子，right表示右孩子，当然也可以加上父亲节点,不过这里还用不到父亲节点，所以就不用加上了。
接着写了一个createBinaryTree的方法，键入key的值，如果key的值为'#'，则代表一个左节点（右节点）的结束。如果不是'#'，那么就创建一个新的节点，利用递归思想继续创建。
还是老规矩，举个栗子，如果我们要创建以下这个二叉树，如果键入呢?

image.png

答案是:A-B-D-#-#-#-C-#-#。怎么样，是不是很简单呢。

好了知道如何创建一个二叉树，就该正式讲解如何遍历二叉树了。

4.2前序遍历

# 前序遍历
def pre_order(node):
    if node is None:
        return None
    else:
        print(node.key)
        pre_order(node.left)
        pre_order(node.right)

代码依然很简单，主要还是利用了递归的思想，拿上图来分析，A节点被传入，首先判断A是不是None，显然不是，所以我们打印A节点的键值，接着将A的左孩子传入，同样的B不是None，所以我们打印B，又将B的左孩子传入...，当D遍历然后，返回到B，B的右孩子为空，所以返回到A，传入A的右孩子C...。所以最后的遍历结果是:A-B-D-C

4.3 中序遍历

# 中序遍历
def in_order(node):
    if node is None:
        return None
    else:
        in_order(node.left)
        print(node.key)
        in_order(node.right)

分析同上，这里就不赘述了。遍历结果:D-B-A-C

4.4 后续遍历

# 后序遍历
def post_order(node):
    if node is None:
        return None
    else:
        post_order(node.left)
        post_order(node.right)
        print(node.key)

分析还是同上,遍历结果：D-B-C-A
其实，很容易发现，采用何种遍历方式，就是讲print(node.key)这句代码放在哪个位置。

4.5 层次遍历

# 层次遍历
def levelOrderTravel(node):
    if node is None:
        return
    q = [node]
    while len(q):
        print(q[0].key)
        node = q.pop(0)
        if node.left is not None:
            q.append(node.left)
        if node.right is not None:
            q.append(node.right)

上文中曾提到，二叉树的层次遍历其实是运用到了队列，我们还是用上面那个简单的二叉树来作分析，它的遍历结果为:A-B-C-D。代码是如何实现的呢？其实是首先将A入队，然后然后读取队首，判断其是否有左孩子，有则入队，然后判断右孩子，有则入队，最后将队首弹出，注意，队列的弹出顺序就是层次遍历的顺序。

image.png

5.写在后面

二叉树的一些基本内容差不多就介绍这么多，之后准备写一点二叉树的应用。比如，二叉堆（堆排序），二叉搜索树等。

持续更新中...
二叉树（二）-二叉堆