二叉树 / Binary Tree
二叉树是树结构的一种，但二叉树的每一个节点都最多只能有两个子节点。
Binary Tree:
00
|_____
| |
00 00
|__ |__
| | | |
00 00 00 00
对于二叉树的遍历，主要有以下三种基本遍历方式：
- 先序遍历：先显示节点值，再显示左子树和右子树
- 中序遍历：先显示左子树，再显示节点值和右子树
- 后序遍历：先显示左子树和右子树，再显示节点值
下面将用代码构建一个二叉树，并实现三种遍历方式，
完整代码
class TreeNode:
def __init__(self, val=None, lef=None, rgt=None):
self.value = val
self.left = lef
self.right = rgt def __str__(self):
return str(self.value) class BinaryTree:
"""
Binary Tree:
00
|_____
| |
00 00
|__ |__
| | | |
00 00 00 00
"""
def __init__(self, root=None):
self._root = root def __str__(self):
return '\n'.join(map(lambda x: x[1]*4*' '+str(x[0]), self.pre_traversal())) def pre_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
x.append((node, depth))
if node and node.left is not None:
_traversal(node.left)
if node and node.right is not None:
_traversal(node.right)
depth -= 1
return x
return _traversal(root) def in_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
if node and node.left is not None:
_traversal(node.left)
x.append((node, depth))
if node and node.right is not None:
_traversal(node.right)
depth -= 1
return x
return _traversal(root) def post_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
if node and node.left is not None:
_traversal(node.left)
if node and node.right is not None:
_traversal(node.right)
x.append((node, depth))
depth -= 1
return x
return _traversal(root) @property
def max_depth(self):
return sorted(self.pre_traversal(), key=lambda x: x[1])[-1][1] def show(self, tl=None):
if not tl:
tl = self.pre_traversal()
print('\n'.join(map(lambda x: x[1]*4*' '+str(x[0]), tl))) def make_empty(self):
self.__init__() def insert(self, item):
if self._root is None:
self._root = TreeNode(item)
return def _insert(item, node):
if not node:
return TreeNode(item)
if node.left is None:
node.left = _insert(item, node.left)
elif node.right is None:
node.right = _insert(item, node.right)
else:
if len(self.pre_traversal(node.left)) <= len(self.pre_traversal(node.right)):
node.left = _insert(item, node.left)
else:
node.right = _insert(item, node.right)
return node
self._root = _insert(item, self._root) if __name__ == '__main__':
bt = BinaryTree()
print('\nBinary Tree:')
'''
0
|_____
| |
1 2
|__ |__
| | | |
3 5 4 6
'''
for i in range(7):
bt.insert(i)
bt.show()
print('\n------Pre-traversal-------')
print(bt) print('\n------Post-traversal------')
bt.show(bt.post_traversal())
print('\n-------In-traversal-------')
bt.show(bt.in_traversal()) bt.make_empty()
print('\n-------Empty-tree-------')
print(bt)
分段解释
首先定义树节点，包含3个属性（指针引用），分别为：当前值，左子树节点，右子树节点
class TreeNode:
def __init__(self, val=None, lef=None, rgt=None):
self.value = val
self.left = lef
self.right = rgt def __str__(self):
return str(self.value)
构建一个二叉树类，构造函数中包含一个根节点属性，
class BinaryTree:
"""
Binary Tree:
00
|_____
| |
00 00
|__ |__
| | | |
00 00 00 00
"""
def __init__(self, root=None):
self._root = root
重定义__str__方法，在打印树时，依据树的深度添加tab显示，类似于文件目录（文件分级目录原本便是由树实现的）的显示方式
def __str__(self):
return '\n'.join(map(lambda x: x[1]*4*' '+str(x[0]), self.pre_traversal()))
定义先序遍历方法，通过递归的方式进行实现，优先显示当前节点
def pre_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
x.append((node, depth))
if node and node.left is not None:
_traversal(node.left)
if node and node.right is not None:
_traversal(node.right)
depth -= 1
return x
return _traversal(root)
定义中序遍历方法，与先序遍历基本相同，只是处理当前节点的顺序在左子树之后，右子树之前，
def in_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
if node and node.left is not None:
_traversal(node.left)
x.append((node, depth))
if node and node.right is not None:
_traversal(node.right)
depth -= 1
return x
return _traversal(root)
定义后序遍历方法，处理当前节点的顺序在左子树和右子树之后，
def post_traversal(self, root=None):
if not root:
root = self._root
x = []
depth = -1 def _traversal(node):
nonlocal depth
depth += 1
if node and node.left is not None:
_traversal(node.left)
if node and node.right is not None:
_traversal(node.right)
x.append((node, depth))
depth -= 1
return x
return _traversal(root)
再定义一些树的基本方法，显示树的时候，优先采用先序遍历显示，
@property
def max_depth(self):
return sorted(self.pre_traversal(), key=lambda x: x[1])[-1][1] def show(self, tl=None):
if not tl:
tl = self.pre_traversal()
print('\n'.join(map(lambda x: x[1]*4*' '+str(x[0]), tl))) def make_empty(self):
self.__init__()
最后定义二叉树的插入方法，插入方式尽量保证二叉树的平衡，插入顺序为当前节点->左->右，当左右节点都不为空时，则递归插入左子树和右子树中，深度较小的那一棵树。
def insert(self, item):
if self._root is None:
self._root = TreeNode(item)
return def _insert(item, node):
if not node:
return TreeNode(item)
if node.left is None:
node.left = _insert(item, node.left)
elif node.right is None:
node.right = _insert(item, node.right)
else:
if len(self.pre_traversal(node.left)) <= len(self.pre_traversal(node.right)):
node.left = _insert(item, node.left)
else:
node.right = _insert(item, node.right)
return node
self._root = _insert(item, self._root)
定义完二叉树类后，对二叉树进行构建，插入元素并利用三种遍历方式显示二叉树。
if __name__ == '__main__':
bt = BinaryTree()
print('\nBinary Tree:')
'''
0
|_____
| |
1 2
|__ |__
| | | |
3 5 4 6
'''
for i in range(7):
bt.insert(i)
bt.show()
print('\n------Pre-traversal-------')
print(bt) print('\n------Post-traversal------')
bt.show(bt.post_traversal())
print('\n-------In-traversal-------')
bt.show(bt.in_traversal()) bt.make_empty()
print('\n-------Empty-tree-------')
print(bt)
三种遍历方式显示结果如下
Binary Tree:
0
1
3
5
2
4
6 ------Pre-traversal-------
0
1
3
5
2
4
6 ------Post-traversal------
3
5
1
4
6
2
0 -------In-traversal-------
3
1
5
0
4
2
6 -------Empty-tree-------
None