【数据结构实践】手把手带你快速实现自定义二叉树

作者：迷彩

2022 年 8 月 30 日
广东
本文字数：2421 字
阅读完需：约 8 分钟

前言

什么是树

在学习二叉树之前.我们先来了解什么是树,跟我们现实生活中的树有什么联系,又有什么区别,树是一种很简单的结构,他是非线性的结构.在这种结构中,所有的元素之间的关系具有明显的层次特性,节点（Node）是树的基本构成部分,每个节点只有一个前件,成为父节点,没前件的父节点只有一个,那就是树的根节点（Root）.每个节点可以有多个后件,这就是树的子节点（Children）.没有后件(没有子节点)的节点称为叶子节点（Leaf Node）,在树结构中,一个节点拥有的后件(子节点)个数称为节点的度,最大的度称为树的度,最大的层次(Level)称为树的深度（Height）.

关于树的相关的还有其他的相关的概念:

边（Edge）：也是树的基本构成部分。边连接两个节点，并表示它们之间存在联系。每个节点（除了根节点）都有且只有一条与其他节点相连的入边（指向该节点的边），每个节点可能有许多条出边（从该节点指向其他节点的边）。

路径（Path）：是由边连接起来的节点的有序排列。例如：动物界 → 脊索动物门 → 哺乳动物纲 → 食肉动物目 → 犬科 → 猎犬.... 就是一条路径。

子节点集（Children）：当一个节点的入边来自另一个节点时，称前者是后者的子节点。同一个节点的所有子节点构成子节点集。

兄弟节点（Sibling）：同一个节点的所有子节点互为兄弟节点。

子树（Subtree）：是一个父节点的某个子节点的所有边和后代节点所构成的集合

可以想象成我们现实生活中所看到的树,只不过计算机数据结构中所说的树是倒过来的,现实生活中的树根部在下:

而计算机数据结构中的树根部在上面,下图:

什么是二叉树

我们认识了树,接着我们介绍我们今天的主角--二叉树的相关概念.

二叉树是一种特殊的树,具有以下特点:

每个节点最多只能拥有两颗子树,即每个节点的度最多为 2
二叉树的子树有左右之分,即左子树和右子树
单子树也要区分左右子树

二叉树有五种基本形态：二叉树可以是空集；根可以有空的左子树或右子树；或者左、右子树皆为空:如下图:

二叉树的基本性质

在二叉树的第 k 层上,最多 2^k-1 个节点,其中 k>=1
深度为 m 的二叉树最多有 2^m-1 个节点,其中 m>=1
在任意一颗二叉树中,度数为 0 的节点比度数为 2 的节点多一个
有 n 个节点的二叉树,其深度至少为 log2(n+1)

满二叉树

除了最后一层,每层上的所有节点都有两个子节点,如果一颗树深度为 d，最大层数为 k,它的叶子数是: 2^d,第 k 层的节点数是: 2^(k-1),总节点数是: 2^k-1 (2 的 k 次方减一),总节点数一定是奇数。如下图:

完全二叉树

除最后一层外,每一层上的节点数均达到最大值,叶子节点只能出现在最下层和次下层，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树,如下图:

二叉树的遍历

前序遍历<DLR>:先访问根节点,再遍历左子树,最后遍历右子树
中序遍历<LDR>:先遍历左子树,再访问根节点,最后遍历右子树
后续遍历<LRD>:先遍历左子树,再遍历右子树,最后访问根节点

实现流程

具体实现步骤:

定义节点类,使用 None 类型数据表示空节点
定义二叉树类,初始化根节点
实现添加节点的方法
实现二叉树的遍历方法:实现前序遍历,中序遍历,后续遍历

二叉树的代码实现

自定义创建节点的类,并初始化类的属性:

class Node:    def __init__(self, item):        self.item = item        self.child1 = None        self.child2 = None

复制代码

定义创建二叉树的类,并实现添加节点和二叉树的前中后序遍历

class Node:    def __init__(self, item):        self.item = item        self.child1 = None        self.child2 = None
class BinaryTree:    def __init__(self):        self.root = None
    #添加节点    def add(self, item):        node = Node(item)        if self.root is None:            self.root = node        else:            q = [self.root]
            while True:                pop_node = q.pop(0)                if pop_node.child1 is None:                    pop_node.child1 = node                    return                elif pop_node.child2 is None:                    pop_node.child2 = node                    return                else:                    q.append(pop_node.child1)                    q.append(pop_node.child2)
    #使用递归实现遍历    def preorder(self, root):  # 先序遍历        if root is None:            return []        result = [root.item]        left_item = self.preorder(root.child1)        right_item = self.preorder(root.child2)        return result + left_item + right_item
    def inorder(self, root):  # 中序遍历        if root is None:            return []        result = [root.item]        left_item = self.inorder(root.child1)        right_item = self.inorder(root.child2)        return left_item + result + right_item
    def postorder(self, root):  # 后序遍历        if root is None:            return []        result = [root.item]        left_item = self.postorder(root.child1)        right_item = self.postorder(root.child2)        return left_item + right_item + result

复制代码

验证二叉树类:

tree=BinaryTree()#0-9数字组成的树的遍历for i in range(10):    tree.add(i) #添加节点print('前序遍历:', tree.preorder(tree.root))print('中序遍历:', tree.inorder(tree.root))print('后序遍历:', tree.postorder(tree.root))

复制代码

执行结果:

总结

对于二叉树的遍历还有一种层序遍历，顾名思义，就是逐层遍历,对于树型结构，层序遍历就是按层从上到下，每层按一定顺序对树的节点进行遍历，比如每层从左到右逐个遍历。与前中后序遍历最根本的区别是双亲节点的访问时机不同.前序遍历是先访问双亲节点,然后左子节点,最后右子节点。而中序遍历是先访问左子节点，接着是双亲节点，最后右子节点。后序遍历是先访问左子节点，然后右子节点，最后双亲节点

发布于: 2022 年 08 月 30 日阅读数: 41

原文链接:【http://xie.infoq.cn/article/b2ae51e4b5dedf3b375f0b6e3】。文章转载请联系作者。

迷彩

关注

我的工作是常年写bug|公众号:编程架构之美 2020.06.18 加入

修bug的菜鸟~公众号:“互联网有啥事”已改名为“编程架构之美”

发布

暂无评论

创作场景

【数据结构实践】手把手带你快速实现自定义二叉树

前言

什么是树

什么是二叉树

二叉树的基本性质

满二叉树

完全二叉树

二叉树的遍历

实现流程

二叉树的代码实现

总结

迷彩

评论