Python3学习笔记-24：数据结构：二叉树

“人生苦短，快用Python”

在Python3中，已有实现好的二叉树的模块：binarytree模块；可通过pip安装此模块：pip install binarytree 。
一、二叉树
二叉树（Binary Tree）是一种特殊的树结构，它的每个节点最多可以有两个子节点。每个二叉树都有一个根指针，指向二叉树的根节点；在空二叉树中，根指针将指向 NULL 。每个节点包含三个部分：左子节点指针、本节点数据、右子节点指针。叶子节点的左右子节点指针为 NULL 。如果所有叶子节点都位于相同的水平d，则称二元树是完全二叉树；在0级和d级之间的每个级别（n级）包含 2^n 个节点。具有深度d的完全二叉树中的节点总数是 2^(d+1) -1，其中叶子节点总数是 2^d 。

二叉树的遍历递归地应用于树的每个子树：

前序遍历：首先遍历根，然后分别遍历左子树和右子树。
中序遍历：首先遍历左子树，然后分别遍历根和右子树。
后序遍历：遍历左子树，然后分别遍历右子树和根。
层序遍历：从上到下、从左到右，遍历每一层的每一个节点。

二叉树包含的数据操作有：、创建二叉树（createBinaryTree）、前序遍历（preorder）、中序遍历（inorder）、后序遍历（postorder）、层序遍历（levelorder）
二、二叉树的实现

class Node(object):

复制代码

def __init__(self, data=None ):

复制代码

self.left = None

复制代码

self.right = None

复制代码

self.data = data

复制代码

def set_left(self, node):

复制代码

self.left = node

复制代码

def set_right(self, node):

复制代码

self.right = node

复制代码

def get_left(self):

复制代码

return self.left

复制代码

def get_right(self):

复制代码

return self.right

复制代码

def set_data(self, data):

复制代码

self.data = data

复制代码

def get_data(self):

复制代码

return self.data

复制代码

# 二叉树

复制代码

class BinaryTree(object):

复制代码

def __init__(self):

复制代码

self._in_order = []

复制代码

self._pre_order = []

复制代码

self._post_order = []

复制代码

# 中序遍历

复制代码

def inorder(self, root):

复制代码

if root:

复制代码

# 遍历左子树

复制代码

self.inorder(root.get_left())

复制代码

# 遍历根节点

复制代码

self._in_order.append(root.get_data())

复制代码

# 遍历右子树

复制代码

self.inorder(root.get_right())

复制代码

return self._in_order

复制代码

# 前序遍历

复制代码

def preorder(self, root):

复制代码

if root:

复制代码

# 遍历根节点

复制代码

self._pre_order.append(root.get_data())

复制代码

# 遍历左子树

复制代码

self.preorder(root.get_left())

复制代码

# 遍历右子树

复制代码

self.preorder(root.get_right())

复制代码

return self._pre_order

复制代码

# 后序遍历

复制代码

def postorder(self, root):

复制代码

if root:

复制代码

# 遍历左子树

复制代码

self.postorder(root.get_left())

复制代码

# 遍历右子树

复制代码

self.postorder(root.get_right())

复制代码

# 遍历根节点

复制代码

self._post_order.append(root.get_data())

复制代码

return self._post_order

复制代码

Talk is cheap.

Show me the code.