二叉树的概念及其遍历方法 - python实现
二叉树
二叉树的基本概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
二叉树的性质(特性)
- 性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）
- 性质2: 深度为k的二叉树至多有2^k - 1个结点（k>0）
- 性质3: 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;
- 性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)
- 性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
二叉树的遍历
树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。
二叉树的创建及广度优先遍历
class Node:
"""结点"""
def __init__(self, item):
self.item = item
self.lchild = None # 左子节点
self.rchild = None # 右子节点
class Tree:
"""二叉树类"""
def __init__(self, root=None):
self.root = root # 根节点
def add(self, item):
"""添加结点"""
node = Node(item)
if self.root == None: # 如果根节点为空,直接赋值根节点
self.root = node
else:
queue = [] # 创建一个对列
queue.append(self.root) # 将根节点加入队列中
while queue: # 遍历结点
# 弹出第一个结点
cur = queue.pop(0)
if cur.lchild == None: # 判断此节点是否为空
cur.lchild = node # 如果为空,就把node放到此位置
return # 已经找到结点位置直接返回
elif cur.rchild == None:
cur.rchild = node
return
else:
# 如果左右子树都不为空,没有位置添加node,
# 就把左右子树的结点加入队列继续判断此子节点的左右子节点是否为空
queue.append(cur.lchild)
queue.append(cur.rchild)
def travle(self):
"""
遍历二叉树
广度优先遍历
"""
if self.root == None: # 如果此树为空,直接返回
return
queue = [] # 创建一个队列
queue.append(self.root) # 将待遍历的结点加入
while queue: # 如果队列不为空,就一直循环
node = queue.pop(0) # 弹出队列第一个元素并打印出来
print(node.item)
# 接着判断该结点的左右子节点是否存在,如果存在就加入队列等待弹出打印
if node.lchild != None:
queue.append(node.lchild)
if node.rchild != None:
queue.append(node.rchild)
if __name__ == '__main__':
t1 = Tree()
t1.add(1)
t1.add(2)
t1.add(3)
t1.add(4)
t1.add(5)
t1.add(6)
t1.add(7)
t1.add(8)
t1.add(9)
t1.travle() # 1 2 3 4 5 6 7 8 9
深度优先遍历及其前序,中序,后序会在下一篇讲解