本文共 2415 字，大约阅读时间需要 8 分钟。

树与二叉树技术文档

树的定义与特点

树是一种抽象数据类型（ADT），用来模拟具有树状结构的数据集合。树由n（n≥1）个节点组成，每个节点可以有零个或多个子节点，且每个非根节点有且只有一个父节点。树的层次关系从根节点开始定义，根节点为第1层，其子节点为第2层，依此类推。

树的术语解析

树的种类

常见二叉树类型

• 完全二叉树：除了最底层外，其它层节点数目均已达最大值，且第d层节点从左向右连续排列。
• 平衡二叉树（AVL树）：任意节点的两棵子树高度差不超过1。
• 排序二叉树：有序二叉树，用于二叉查找。
• 霍夫曼树：带权路径最短的二叉树。
• B树：自平衡二叉查找树，支持多级分支。

树的存储与表示

树的存储可分为两种方式：

二叉树的性质

二叉树的代码实现

节点与树的创建

class Node(object):    def __init__(self, item):        self.elem = item        self.lchild = None        self.rchild = Noneclass Tree(object):    def __init__(self):        self.root = None    def add(self, item):        node = Node(item)        if self.root is None:            self.root = node            return        queue = [self.root]        while queue:            cur_node = queue.pop(0)            if cur_node.lchild is None:                cur_node.lchild = node                return            else:                queue.append(cur_node.lchild)            if cur_node.rchild is None:                cur_node.rchild = node                return            else:                queue.append(cur_node.rchild)

广度优先遍历

def breadth_travel(self):    if self.root is None:        return    queue = [self.root]    while queue:        cur_node = queue.pop(0)        print(cur_node.elem, end=" ")        if cur_node.lchild is not None:            queue.append(cur_node.lchild)        if cur_node.rchild is not None:            queue.append(cur_node.rchild)

深度优先遍历

def preorder(self, node):    if node is None:        return    print(node.elem, end=" ")    self.preorder(node.lchild)    self.preorder(node.rchild)def inorder(self, node):    if node is None:        return    self.inorder(node.lchild)    print(node.elem, end=" ")    self.inorder(node.rchild)def postorder(self, node):    if node is None:        return    self.postorder(node.lchild)    self.postorder(node.rchild)    print(node.elem, end=" ")

树的唯一性判断

通过广度优先和深度优先遍历，可以唯一确定一棵树的结构。

转载地址：http://vviv.baihongyu.com/