什么是树，它是和链表一样都是一种抽象数据类型（ADT),包括数据结构和对数据的操作。
树是一种二维平面的数据结构结构，它也是由节点组成的，只是它的后继节点不止一个，而链表的后继节点只有一个。
树具有以下特点：
①每个节点有零个或多个子节点；
②没有父节点的节点称为根节点；
③每一个非根节点有且只有一个父节点；
④除了根节点外，每个子节点可以分为多个不相交的子树；
先来介绍一种典型的树类型：二叉树（上图不是个二叉树，因为根节点就不满足只有两个子树的条件）
定义：每个结点最多含有两个子树的树称为二叉树。
二叉树有很多种：二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树
关于树有很多专业术语：
根结点，叶子结点，深度，堂兄弟结点，兄弟结点，层等等
满足二叉树的前提条件下，又衍生出完全二叉树和满二叉树：
完全二叉树：假设树的深度的是h，那么除了h层之外，其余层节点数达到最大，且第h层所有的节点都连续集中在最左边，这就是完全二叉树。
满二叉树：除最后一层外，其余结点都含有两个子结点，达到每层均是满的结点数。
有了树的模型，那么树是怎么来存储呢，有两种方式：顺序存储和链表存储。
有了存储的方式，那么就是对树如何进行操作了，这里暂时只介绍增加结点和遍历树中的结点
下面来介绍如何遍历二叉树：
遍历二叉树有两种方式：BFS和DFS
BFS就是广度遍历，就是一层一层的遍历。从第一层根结点开始。然后第二层：左结点，右结点，依次类推，最后是到叶子结点遍历完成。
DFS就是：深度遍历，分为先序遍历，中序遍历，后序遍历。
先序遍历：从树的根节点开始，然后左结点，右节点。
中序遍历：先从树的根节点的左结点开始，遍历根结点，遍历右节点
后序遍历：先从树的根节点的左节点开始，然后遍历右节点，最后遍历根节点。
下面通过代码来实现树，并进行广度遍历。这里使用的是队列：
class Node(object):
def __init__(self,item=None):
self.val = item
self.lchild = None
self.rchild = None
#创建一个树
class Tree(object):
def __init__(self,node=None):
self.root = node
#增加结点
def add(self,item):
node = Node(item)
if self.root == None:
self.root = node
return
queue = [self.root] #使用队列来操作
while queue:
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
else:
queue.append(cur.lchild)
if cur.rchild == None:
cur.rchild = node
return
else:
queue.append(cur.rchild)
#树的广度遍历
def travel_bfs(self):
queue = [self.root]
if self.root == None:
return
while queue:
cur_node = queue.pop(0)
print(cur_node.val,end='\t')
if cur_node.lchild != None:
queue.append(cur_node.lchild)
if cur_node.rchild != None:
queue.append(cur_node.rchild)
t = Tree()
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.travel_bfs()
运行结果：
1 2 3 4 5
下面介绍树的深度遍历：先序遍历，中序遍历，后序遍历。主要使用的是递归：
例：先序遍历
#创建一个结点
class Node(object):
def __init__(self,item=None):
self.val = item
self.lchild = None
self.rchild = None
#创建一个树
class Tree(object):
def __init__(self,node=None):
self.root = node
#增加结点
def add(self,item):
node = Node(item)
if self.root == None:
self.root = node
return
queue = [self.root] #使用队列来操作
while queue:
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
else:
queue.append(cur.lchild)
if cur.rchild == None:
cur.rchild = node
return
else:
queue.append(cur.rchild)
#树的广度遍历
def travel_bfs(self):
queue = [self.root]
if self.root == None:
return
while queue:
cur_node = queue.pop(0)
print(cur_node.val,end = ' ')
if cur_node.lchild != None:
queue.append(cur_node.lchild)
if cur_node.rchild != None:
queue.append(cur_node.rchild)
def preorder(self,root_node):
if root_node == None:
return
print(root_node.val,end = ' ')
self.preorder(root_node.lchild)
self.preorder(root_node.rchild)
t = Tree()
t.add(0)
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.add(6)
t.add(7)
t.add(8)
t.add(9)
t.travel_bfs()
print()
t.preorder(t.root)
运行结果：
0 1 2 3 4 5 6 7 8 9
0 1 3 7 8 4 9 2 5 6
例：中序遍历和后序遍历
#创建一个结点
class Node(object):
def __init__(self,item=None):
self.val = item
self.lchild = None
self.rchild = None
#创建一个树
class Tree(object):
def __init__(self,node=None):
self.root = node
#增加结点
def add(self,item):
node = Node(item)
if self.root == None:
self.root = node
return
queue = [self.root] #使用队列来操作
while queue:
cur = queue.pop(0)
if cur.lchild == None:
cur.lchild = node
return
else:
queue.append(cur.lchild)
if cur.rchild == None:
cur.rchild = node
return
else:
queue.append(cur.rchild)
#树的广度遍历
def travel_bfs(self):
queue = [self.root]
if self.root == None:
return
while queue:
cur_node = queue.pop(0)
print(cur_node.val,end = ' ')
if cur_node.lchild != None:
queue.append(cur_node.lchild)
if cur_node.rchild != None:
queue.append(cur_node.rchild)
def preorder(self,root_node):
'''先序遍历'''
if root_node == None:
return
print(root_node.val,end = ' ')
self.preorder(root_node.lchild)
self.preorder(root_node.rchild)
def midorder(self,root_node):
'''中序遍历'''
if root_node == None:
return
self.midorder(root_node.lchild)
print(root_node.val,end = ' ')
self.midorder(root_node.rchild)
def postorder(self,root_node):
'''后序遍历'''
if root_node == None:
return
self.postorder(root_node.lchild)
self.postorder(root_node.rchild)
print(root_node.val,end = ' ')
t = Tree()
t.add(0)
t.add(1)
t.add(2)
t.add(3)
t.add(4)
t.add(5)
t.add(6)
t.add(7)
t.add(8)
t.add(9)
t.travel_bfs()
print()
t.preorder(t.root)
print()
t.midorder(t.root)
print()
t.postorder(t.root)
运行结果：
0 1 2 3 4 5 6 7 8 9
0 1 3 7 8 4 9 2 5 6
7 3 8 1 9 4 0 5 2 6
7 8 3 9 4 1 5 6 2 0
附上别人写的挺详细的文章：
https://blog.csdn.net/u012060033/article/details/107128291/