二叉树是一种特殊的树，树是我们常用数据结构。因二叉树拥有多种优良特性，所以在实际应用中使用非常广泛。
这里我们讨论有根二叉树，有根二叉树的根节点度最多为2，每个节点只有一个父节点，最多有两个子节点。而二叉树又有很多特殊的结构，如斜二叉树、满二叉树、完全二叉树、线索二叉树（排序二叉树）、平衡二叉树等。
这里我们先不做深究，先来实现二叉树这种数据结构。
二叉树中的节点本身可以存储数据，而且有一个父节点，两个子节点。
所以我们可以很容易的模拟出这种节点的结构：
-------------------------------------------
| left_child | data | right_child |
-------------------------------------------
这是最简单的节点结构，当然我们也可以给节点一个内存空间用来指向其父节点。
------------------------------------------------------
| left_child | data | parent | right_child |
------------------------------------------------------
这两种都可以，我们今天用前一种，用来实现三种遍历方式。
class BiTNode:
"""模拟二叉树节点"""
def __init__(self,arg):
self.data = arg
self.left_child = None
self.right_child = None
先来说一下三种遍历方式：
前序遍历——根左右：
遍历每一颗二叉树时，总是先遍历其根节点，然后遍历其左孩子，在遍历其右节点。
遍历二叉树其实是一个递归的过程，因为当遍历到左节点是，左节点可能也是一个二叉树，此时遍历左节点也是依据——根左右的顺序，来遍历这颗子树。
中序遍历——左根右
遍历一颗二叉树时，总是先遍历其左节点，然后遍历其根节点，最后遍历其右节点。也是一个递归的过程。
后序遍历——左右根
遍历一颗二叉树时，总是先从其左节点开始，然后遍历其右节点，最后遍历根节点。
可以看出这三种遍历方式都是遍历根节点的顺序变了。
比如这棵树：
image.png
前序遍历：
** FCADBEHGM **
中序遍历：
** ACBDFHEMG **
后序遍历：
** ABDCHMGEF **
代码实现：
前序遍历：
#前序遍历
def print_tree_pre_order(root):
#先判断二叉树是否为空
#if root.left_child is None and root.right_child is None:
if root is None:
return root
#先根
print(root.data)
#再左
if root.left_child is not None:
print_tree_pre_order(root.left_child)
#再右
if root.right_child is not None:
print_tree_pre_order(root.right_child)
中序遍历：
#中序遍历
def print_tree_mid_order(root):
#先判断二叉树是否为空,当左右节点都为空时
if root is None:
return
#中序遍历 左根右
#遍历左子树
if root.left_child is not None:
print_tree_mid_order(root.left_child)
#遍历根节点
print(root.data)
#遍历右子树
if root.right_child is not None:
print_tree_mid_order(root.right_child)
后序遍历：
#后序遍历
def print_tree_after_order(root):
#先判断二叉树是否为空
if root is None:
return root
#再左
if root.left_child is not None:
print_tree_after_order(root.left_child)
#再右
if root.right_child is not None:
print_tree_after_order(root.right_child)
#先根
print(root.data)
我们来用程序验证下这三种方式是否正确：
if __name__ == '__main__':
root=BiTNode(1)
root.left_child=BiTNode(2)
root.right_child=BiTNode(3)
root.left_child.left_child=BiTNode(4)
root.left_child.right_child = BiTNode(4)
print("前序：\n")
print_tree_pre_order(root)
print("中序：\n")
print_tree_mid_order(root)
print("后序：\n")
print_tree_after_order(root)
运行结果：
image.png
从运行性结果来讲我们的程序是对的。
全部代码：
#二叉树有顺序存储和链式存储两种，这里用的链式存储
#遍历二叉树的三种方法：前序、中序、后序
#构造二叉树节点类型
class BiTNode:
"""模拟二叉树节点"""
def __init__(self,arg):
self.data = arg
self.left_child = None
self.right_child = None
#前序遍历
def print_tree_pre_order(root):
#先判断二叉树是否为空
#if root.left_child is None and root.right_child is None:
if root is None:
return root
#先根
print(root.data)
#再左
if root.left_child is not None:
print_tree_pre_order(root.left_child)
#再右
if root.right_child is not None:
print_tree_pre_order(root.right_child)
#中序遍历
def print_tree_mid_order(root):
#先判断二叉树是否为空,当左右节点都为空时
if root is None:
return
#中序遍历 左根右
#遍历左子树
if root.left_child is not None:
print_tree_mid_order(root.left_child)
#遍历根节点
print(root.data)
#遍历右子树
if root.right_child is not None:
print_tree_mid_order(root.right_child)
#后序遍历
def print_tree_after_order(root):
#先判断二叉树是否为空
if root is None:
return root
#再左
if root.left_child is not None:
print_tree_after_order(root.left_child)
#再右
if root.right_child is not None:
print_tree_after_order(root.right_child)
#先根
print(root.data)
if __name__ == '__main__':
root=BiTNode(1)
root.left_child=BiTNode(2)
root.right_child=BiTNode(3)
root.left_child.left_child=BiTNode(4)
root.left_child.right_child = BiTNode(4)
print("前序：\n")
print_tree_pre_order(root)
print("中序：\n")
print_tree_mid_order(root)
print("后序：\n")
print_tree_after_order(root)
前段时间接触了机器学习，安装tensorflow时遇到了不少问题，最后还是没有安装成功，很难受，说什么DLL加载失败，网上查一下，挺多人遇到的，github上看了，歪果仁写的解决方案，大概能看懂，但是好像并没有解决我的问题，所以打算先放放，而且电脑也没有支持的gpu，以后在弄吧！
至于二叉树的其他操作，我会慢慢学的！
网友评论