0.前言
一直以来都在做Android开发，感觉算法这些都不是很好，所以准备从基本的数据结构开始学习，也相当于自己的学习笔记吧。
1.什么是二叉树
二叉树是树的一种，每个节点最多可具有两个子树，即结点的度最大为2（结点度：结点拥有的子树数）。
例：
2.二叉树的种类
2.1 斜树
所有结点都只有左子树，或者右子树。
2.2 满二叉树
所有的分支节点都具有左右节点。
2.3 完全二叉树
若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。
3.二叉树的一些性质
- 二叉树第i层上的结点数目最多为 2^(i-1) (i≥1)
- 深度为h的二叉树至多有2^h-1个结点(h≥1)
- 包含n个结点的二叉树的高度至少为log2 (n+1)
- 在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1
4.二叉树的遍历方式
二叉树的遍历方式，一般分为前序遍历，中序遍历，后续遍历，层次遍历。
前、中、后序遍历是针对中间（父亲）节点来说的，如前序遍历，即先遍历中间（父亲）节点；中序遍历，就是第二个遍历中间（父亲）节点。这么说也许还是有点抽象，下面就举个栗子吧。
- 前序遍历(中-左-右):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的值为'#'，则代表一个左节点（右节点）的结束。如果不是'#'，那么就创建一个新的节点，利用递归思想继续创建。
还是老规矩，举个栗子，如果我们要创建以下这个二叉树，如果键入呢?
答案是: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入队，然后然后读取队首，判断其是否有左孩子，有则入队，然后判断右孩子，有则入队，最后将队首弹出，注意，队列的弹出顺序就是层次遍历的顺序。
5.写在后面
二叉树的一些基本内容差不多就介绍这么多，之后准备写一点二叉树的应用。比如，二叉堆（堆排序），二叉搜索树等。
持续更新中...
二叉树（二）-二叉堆
