python数据结构之二叉树

树型结构是一类重要的非线性数据结构,其中以树和二叉树最为常用,是以分支关系定义的层次结构。树结构在客观世界中广泛存在,如人类社会的族谱和各种社会组织机构;在计算机领域中也有广泛应用,如在编译程序中,可用树来表示源程序的语法结构;在数据库系统中,树型结构也是信息的重要组织形式之一;在机器学习中,决策树,随机森林,GBDT等是常见的树模型

树的相关定义

节点:树的基本部分。它可以有一个名称,我们称之为“键”。节点也可以有附加信息。我们将这个附加信息称为“有效载荷”。虽然有效载荷信息不是许多树算法的核心,但在利用树的应用中通常是关键的。

边:树的另一个基本部分。边连接两个节点以显示它们之间存在关系。每个节点(除根之外)都恰好从另一个节点的传入连接。每个节点可以具有多个输出边。

根:树的根是树中唯一没有传入边的节点。

路径:路径是由边连接节点的有序列表。

子节点:具有来自相同传入边的节点 c 的集合称为该节点的子节点。

父节点:具有和它相同传入边的所连接的节点称为父节点。

兄弟节点:树中作为同一父节点的子节点的节点被称为兄弟节点。

子树:由父节点和该父节点的所有后代组成的一组节点和边。

叶节点:叶节点是没有子节点的节点。

高度:树的高度等于树中任何节点的最大层数。

定义一:树由一组节点和一组连接节点的边组成。树具有以下属性:

树的一个节点被指定为根节点。

除了根节点之外,每个节点 n 通过一个其他节点 p 的边连接,其中 p 是 n 的父节点。

从根路径遍历到每个节点路径唯一。

如果树中的每个节点最多有两个子节点,我们说该树是一个二叉树。

如下:

#!/usr/bin/env python
# -*- coding: UTF-8 -*-
#                     _ooOoo_
#                   o8888888o
#                    88" . "88
#                 ( | -  _  - | )
#                     O\ = /O
#                 ____/`---'\____
#                  .' \\| |// `.
#                 / \\|||:|||// \
#               / _|||||-:- |||||- \
#                | | \\\ - /// | |
#              | \_| ''\---/'' | _/ |
#               \ .-\__ `-` ___/-. /
#            ___`. .' /--.--\ `. . __
#         ."" '< `.___\_<|>_/___.' >'"".
#       | | : `- \`.;`\  _ /`;.`/ - ` : | |
#          \ \ `-. \_ __\ /__ _/ .-` / /
#      ==`-.____`-.___\_____/___.-`____.-'==
#                     `=---='
'''
@Project :pythonalgorithms 
@File :BinaryTree.py
@Author :不胜人生一场醉
@Date :2021/7/15 23:35 
'''

from graphviz import Digraph
import uuid
from random import sample


# 二叉树类
class BinaryTree(object):
    # 初始化
    def __init__(self, root=None):
        self.data = root  # 数据
        self.leftchild = None  # 左子树
        self.rightchild = None  # 右子树
        self.dot = Digraph(comment='Binary Tree')

    # 插入左节点
    def insertleft(self, data):
        newnode = BinaryTree(data)
        if self.leftchild == None:
            self.leftchild = newnode
        else:
            newnode.leftchild = self.leftchild
            self.leftchild = newnode
        return newnode

    # 插入右节点
    def insertright(self, data):
        newnode = BinaryTree(data)
        if self.rightchild == None:
            self.rightchild = newnode
        else:
            newnode.rightchild = self.rightchild
            self.rightchild = newnode
        return newnode

    # 二叉树的高度
    def height(self):
        # 空的树高度为0, 只有root节点的树高度为1
        if self.data is None:
            return 0
        elif self.leftchild == None and self.rightchild == None:
            return 1
        elif self.leftchild == None and self.rightchild != None:
            return 1 + self.rightchild.height()
        elif self.leftchild != None and self.rightchild == None:
            return 1 + self.leftchild.height()
        else:
            return 1 + max(self.leftchild.height(), self.rightchild.height())

    # 访问右子节点
    def getrightchild(self):
        return self.rightchild

    # 访问左子节点
    def getleftchild(self):
        return self.leftchild

    # 设置根节点的值
    def setrootvalue(self, data):
        self.data = data

    # 获取根节点的值
    def getrootvalue(self):
        return self.data

    # 前序遍历
    def preorder(self):

        if self.data != None:
            print(self.data, end=' ')
        if self.leftchild != None:
            self.leftchild.preorder()
        if self.rightchild != None:
            self.rightchild.preorder()

    # 中序遍历
    def inorder(self):

        if self.leftchild != None:
            self.leftchild.inorder()
        if self.data != None:
            print(self.data, end=' ')
        if self.rightchild != None:
            self.rightchild.inorder()

    # 后序遍历
    def postorder(self):

        if self.leftchild != None:
            self.leftchild.postorder()
        if self.rightchild != None:
            self.rightchild.postorder()
        if self.data != None:
            print(self.data, end=' ')

    # 利用Graphviz实现二叉树的可视化
    def printtree(self, save_path='./Binary_Tree.gv', label=True):

        # colors for labels of nodes
        colors = ['skyblue', 'tomato', 'orange', 'purple', 'green', 'yellow', 'pink', 'red']

        # 绘制以某个节点为根节点的二叉树
        def print_node(node, node_tag):
            # 节点颜色
            color = sample(colors, 1)[0]
            if node.leftchild is not None:
                left_tag = str(uuid.uuid1())  # 左节点的数据
                self.dot.node(left_tag, str(node.leftchild.data), style='filled', color=color)  # 左节点
                label_string = 'L' if label else ''  # 是否在连接线上写上标签,表明为左子树
                self.dot.edge(node_tag, left_tag, label=label_string)  # 左节点与其父节点的连线
                print_node(node.leftchild, left_tag)

            if node.rightchild is not None:
                right_tag = str(uuid.uuid1())
                self.dot.node(right_tag, str(node.rightchild.data), style='filled', color=color)  # 右节点
                label_string = 'R' if label else ''  # 是否在连接线上写上标签,表明为右子树
                self.dot.edge(node_tag, right_tag, label=label_string)
                print_node(node.rightchild, right_tag)

        # 如果树非空
        if self.data is not None:
            root_tag = str(uuid.uuid1())  # 根节点标签
            self.dot.node(root_tag, str(self.data), style='filled', color=sample(colors, 1)[0])  # 创建根节点
            print_node(self, root_tag)

        self.dot.render(save_path)  # 保存文件为指定文件


if __name__ == "__main__":
    r = BinaryTree('a')
    rb = r.insertleft('b')
    print(r.getleftchild().getrootvalue())
    rc = r.insertright('c')
    rbd = rb.insertleft('d')
    rbe = rb.insertright('e')
    rcf = rc.insertleft('f')

    print('先序遍历为:')
    r.preorder()
    print()

    print('中序遍历为:')
    r.inorder()
    print()

    print('后序遍历为:')
    r.postorder()
    print()

    # rcfg = rcf.insertleft('g')
    # print('先序遍历为:')
    # r.preorder()
    # print()
    rcfg = rc.insertleft('g')
    print('先序遍历为:')
    r.preorder()
    print()

    r.setrootvalue('aaa')
    print('先序遍历为:')
    r.preorder()
    print()
    print('根节点的值为')
    print(r.getrootvalue())
    print('树的高度是:')
    print(r.height())

    r.printtree()

运行结果如下:

先序遍历为:
a b d e c f 
中序遍历为:
d b e a f c 
后序遍历为:
d e b f c a 
先序遍历为:
a b d e c g f 
先序遍历为:
aaa b d e c g f 
根节点的值为
aaa
树的高度是:
4

来源:python与大数据分析,本文观点不代表自营销立场,网址:https://www.zyxiao.com/p/135911

发表评论

登录后才能评论
服务中心
服务中心
联系客服
联系客服
侵权联系 投诉举报
返回顶部
河南,挺住!郑州,挺住!一起为他们加油!!