树型结构是一类重要的非线性数据结构，其中以树和二叉树最为常用，是以分支关系定义的层次结构。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构；在计算机领域中也有广泛应用，如在编译程序中，可用树来表示源程序的语法结构；在数据库系统中，树型结构也是信息的重要组织形式之一；在机器学习中，决策树，随机森林，GBDT等是常见的树模型
树的相关定义
节点：树的基本部分。它可以有一个名称，我们称之为“键”。节点也可以有附加信息。我们将这个附加信息称为“有效载荷”。虽然有效载荷信息不是许多树算法的核心，但在利用树的应用中通常是关键的。
边：树的另一个基本部分。边连接两个节点以显示它们之间存在关系。每个节点（除根之外）都恰好从另一个节点的传入连接。每个节点可以具有多个输出边。
根：树的根是树中唯一没有传入边的节点。
路径：路径是由边连接节点的有序列表。
子节点：具有来自相同传入边的节点 c 的集合称为该节点的子节点。
父节点：具有和它相同传入边的所连接的节点称为父节点。
兄弟节点：树中作为同一父节点的子节点的节点被称为兄弟节点。
子树：由父节点和该父节点的所有后代组成的一组节点和边。
叶节点：叶节点是没有子节点的节点。
高度：树的高度等于树中任何节点的最大层数。
定义一：树由一组节点和一组连接节点的边组成。树具有以下属性：
树的一个节点被指定为根节点。
除了根节点之外，每个节点 n 通过一个其他节点 p 的边连接，其中 p 是 n 的父节点。
从根路径遍历到每个节点路径唯一。
如果树中的每个节点最多有两个子节点，我们说该树是一个二叉树。
如下：
代码语言：javascript复制#!/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()
运行结果如下：
代码语言：javascript复制先序遍历为:
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
