数据结构与算法-二叉树

线性结构与非线性结构

数据的结构根据其节点关系，可以分为线性结构与非线性结构。

线性结构，也叫顺序结构，是指数据存储和访问的顺序关系。在线性结构中一个节点最多只能有一个前驱节点和一个后继结点。

在非线性结构中，一个节点可以有多个前驱节点和一个后继节点，没有后继节点的节点。

线性结构与非线性结构的区别：

树

概念：树是一种典型的非线性结构，是由n(n>=0)个节点组成的有限集合，当n=0时称为空树。对于非空树，有且仅有一个根节点(root)，其没有父节点，其余节点均可以分为m(m>=0)个同级无任何关系的子集和，每一个集合又可以是一个树，被称为根的子树。

特点：

树的基本术语：

二叉树

概念：二叉树的树的一种特殊结构，二叉树中的每个节点做多只能有两个子节点，分别称为左子树和右子树。

常见类型：

性质：

二叉树的遍历

由于二叉树是非线性结构，不能用常规的顺序方法遍历，这里我们介绍两种复杂算法来遍历二叉树。

树的添加、遍历方法

class TreeNode:
def __init__(self, item):
self.item = item
self.left = None
self.right = None
class BinaryTree:
def __init__(self, root):
self.root = root
def add(self, item):
"""
添加一个新节点
:param item:要添加的节点
:return:None
"""
# 若根节点为空，则将新节点作为根节点
if self.root is None:
self.root = TreeNode(item)
else:
# 创建一个数组存储待添加节点
queue = [self.root]
# 当队列不为空时，循环
while len(queue) > 0:
# 从节点队列中取出一个节点
node = queue.pop(0)
# 判断该节点的左子树是否为空
if node.left is None:
# 为空则该节点的左子树
node.left = TreeNode(item)
break
else:
# 当前节点左子树不为空，则将左子树添加到队列中
queue.append(node.left)
# 判断该节点的右子树是否为空
if node.right is None:
# 为空则该节点的右子树
node.right = TreeNode(item)
break
else:
# 当前节点右子树不为空，则将右子树添加到队列中
queue.append(node.right)
def breadth_travel(self):
"""
广度优先遍历
:return: None
"""
if self.root is None:
return
# 创建一个队列，将根节点添加到队列中
queue = [self.root]
while len(queue):
# 从队列中取出第一个节点
node = queue.pop(0)
# 打印该节点数据
print(node.item, end=' ')
# 左子结点不为空，则将左子节点加入队列中
if node.left is not None:
queue.append(node.left)
# 右子结点不为空，则将右子节点加入队列中
if node.right is not None:
queue.append(node.right)

def preorder_travel(self, root):
"""
深度优先遍历-前序遍历(输出顺序依次是：根 -> 左节点 -> 右节点)
:param root: 根节点
:return:
"""
if root is None:
return
print(root.item, end=' ')
self.preorder_travel(root.left)
self.preorder_travel(root.right)

def inorder_travel(self, root):
"""
深度优先遍历-中序遍历(输出顺序依次是：左节点 -> 根 -> 右节点)
:param root:根节点
:return:
"""
if root is None:
return
self.inorder_travel(root.left)
print(root.item, end=' ')
self.inorder_travel(root.right)

def postorder_travel(self, root):
"""
深度优先遍历-中序遍历(输出顺序依次是：左节点 -> 右节点 -> 根)
:param root:根节点
:return:
"""
if root is None:
return
self.postorder_travel(root.left)
self.postorder_travel(root.right)
print(root.item, end=' ')

广度优先(BFS)和深度优先(DFS)的区别：