本文首发于我的个人博客Suixin’s Blog
原文: https://suixinblog.cn/2019/02/binary-tree.html 作者: Suixin
基础知识
树
树（Tree）是一种非线性结构，用来模拟具有树状结构性质的数据集合。它是由个有限结点组成一个具有层次关系的集合。树是递归结构，在树的定义中又用到了树的概念。
基本术语
- 树结点：包含一个数据元素及若干指向子树的分支；
- 孩子结点（子结点）：结点的子树的根称为该结点的孩子；
- 双亲结点（父结点）：B结点是A结点的孩子，则A结点是B结点的双亲；
- 兄弟结点：同一双亲的孩子结点；
- 堂兄结点：同一层上结点；
- 结点层次：根结点的层定义为1；根的孩子为第二层结点，依此类推；
- 树的高（深）度：树中最大的结点层；
- 结点的度：结点子树的个数；
- 树的度：树中最大的结点度；
- 叶子结点：也叫终端结点，是度为0的结点；
- 分枝结点：度不为0的结点（非终端结点）；
- 森林：互不相交的树集合；
- 有序树：子树有序的树，如：家族树；
- 无序树：不考虑子树的顺序。
性质
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
- 树里面没有环路(cycle)。
二叉树
二叉树（Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。二叉树的分支具有左右次序，不能随意颠倒。二叉树可以为空。
性质
- 在二叉树的第
层上至多有
个结点；
- 深度为
的二叉树上至多含
个结点[1]；
- 对任何一棵二叉树，若它含有
个叶子结点、
个度为2的结点，则必存在关系式：
[2]；
- 具有
个结点的完全二叉树的深度为
或
[3]；
-
- 如果对一棵有
，有：
- 如果
，则结点
，则其双亲的编号是
。
- 如果
，无左孩子；否则，其左孩子是结点
。
- 如果
，则结点
。
- 如果
完全二叉树
若设二叉树的深度为，除第
层外，其它各层
的结点数都达到最大个数，第
层所有的结点都连续集中在最左边，这就是完全二叉树。
- 完全二叉树的
或
；
- 完全二叉树的
[4]。
二叉树的遍历
- 深度优先遍历（Depth First Search，DFS）：沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
- 前序遍历：NLR，根结点->左子树->右子树；
- 中序遍历：LNR，左子树->根结点->右子树；
- 后续遍历：LRN，左子树->右子树->根结点。
- 广度优先遍历（Breadth First Search，BFS；也叫层次遍历，level order）：是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
Python建立二叉树及实现各种遍历方法
二叉树结点类
class BinaryNode(object):
"""二叉树节点类"""
def __init__(self, item, left=None, right=None):
self.item = item
self.left = left
self.right = right
二叉树类
其中包含二叉树的常用操作和七种遍历方法。不做要求的情况下，使用递归的方式实现遍历最简单。
class BinaryTree(object):
"""二叉树及几种遍历方法"""
def __init__(self):
self.root = None
self.bi_list = [] # 使用队列存放二叉树的层次节点信息
def is_empty(self):
return self.root is None
def add(self, item):
"""依次为二叉树添加节点（从上至下，从左至右）"""
node = BinaryNode(item)
if self.is_empty():
self.root = node
self.bi_list.append(node)
else:
tmp_node = self.bi_list[0]
if tmp_node.left is None:
tmp_node.left = node
self.bi_list.append(node)
else:
tmp_node.right = node
self.bi_list.append(node)
self.bi_list.pop(0)
def pre_order(self, root):
if root is None:
return
print(root.item)
self.pre_order(root.left)
self.pre_order(root.right)
def in_order(self, root):
if root is None:
return
self.in_order(root.left)
print(root.item)
self.in_order(root.right)
def post_order(self, root):
if root is None:
return
self.post_order(root.left)
self.post_order(root.right)
print(root.item)
def level_order(self, root):
"""层次遍历，也叫广度优先搜索（Breadth-first search）。
采用队列实现。"""
if root is None:
return
queue = []
queue.append(root)
while queue:
node = queue.pop(0)
print(node.item)
# 如果孩子节点不为空，那么从左至右添加进来
if node.left is not None:
queue.append(node.left)
if node.right is not None:
queue.append(node.right)
def pre_order_stack(self, root):
"""先序遍历的非递归实现。
使用栈"""
if root is None:
return
stack = []
node = root
while node or stack:
while node:
print(node.item)
stack.append(node)
node = node.left
node = stack.pop()
node = node.right
def in_order_stack(self, root):
"""中序遍历的非递归实现。
使用栈"""
if root is None:
return
stack = []
node = root
while node or stack:
while node:
stack.append(node)
node = node.left
node = stack.pop()
print(node.item)
node = node.right
def post_order_stack(self, root):
"""后序遍历的非递归实现。
使用栈"""
if root is None:
return
stack1, stack2 = [], []
stack1.append(root)
while stack1:
# 此循环为了找出后续遍历的逆序，存入stack2中
# 先讲当前节点拿出来存入stack2中
node = stack1.pop()
stack2.append(node)
if node.left is not None:
# 若左孩子非空，先入栈stack1（先入后出，所以是逆序）
stack1.append(node.left)
if node.right is not None:
# 若右孩子非空，入栈stack1
stack1.append(node.right)
for i in stack2[::-1]:
print(i.item)
def height(self, root):
"""递归的求二叉树的最大高度。从叶子结点为‘0层’依次往上数"""
if root is None:
return 0
lheight = self.height(root.left)
rheight = self.height(root.right)
return max(lheight + 1, rheight + 1)
测试函数
def test():
BT = BinaryTree()
print('二叉树是否为空：', BT.is_empty())
print('依次为二叉树添加10个节点...')
for i in range(10):
BT.add(i + 1)
print('前序遍历')
BT.pre_order(BT.root)
print('中序遍历')
BT.in_order(BT.root)
print('后序遍历')
BT.post_order(BT.root)
print('前序遍历，非递归方式')
BT.pre_order_stack(BT.root)
print('中序遍历，非递归方式')
BT.in_order_stack(BT.root)
print('后序遍历，非递归方式')
BT.post_order_stack(BT.root)
print('层次遍历')
BT.level_order(BT.root)
print('二叉树的最大高度：', BT.height(BT.root))
参考
数据结构：树和二叉树
完全二叉树
https://blog.csdn.net/Bone_ACE/article/details/46718683
https://blog.csdn.net/Marksinoberg/article/details/69482397
网友评论