基础概念
定义：
树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件：有且仅有一个特定的称为根（Root）的节点；其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，其中每一个集合又是一棵树，并称为其根的子树（Subtree）。
树的一些基本概念：
- 一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。
- 度数为零的节点称为树叶或终端节点，度数不为零的节点称为分支节点，除根节点外的分支节点称为内部节点。
- 一个节点的子树之根节点称为该节点的子节点，该节点称为它们的父节点，同一节点的各个子节点之间称为兄弟节点。一棵树的根节点没有父节点，叶节点没有子节点。
- 一个节点系列k1,k2, ……,ki,ki+1, ……,kj,并满足ki是ki+1的父节点，就称为一条从k1到kj的路径，路径的长度为j-1,即路径中的边数。路径中前面的节点是后面节点的祖先，后面节点是前面节点的子孙。
- 节点的层数等于父节点的层数加一，根节点的层数定义为一。树中节点层数的最大值称为该树的高度或深度。
- m（m≥0）棵互不相交的树的集合称为森林。树去掉根节点就成为森林，森林加上一个新的根节点就成为树。
二叉树
定义与特征
- 定义
- 二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。
- 二叉树特征
- 二叉树第i（i≥1）层上的节点最多为2i−12^{i-1}2i−1个。 深度为k（k≥1）的二叉树最多有2k－12^k－12k－1个节点。 在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。 满二叉树 ：深度为k（k≥1）时有2k－1个节点的二叉树。 完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。
二叉树遍历
遍历 ：沿某条搜索路径周游二叉树，对树中的每一个节点访问一次且仅访问一次。
先序遍历： 先访问树根，再访问左子树，最后访问右子树；
中序遍历： 先访问左子树，再访问树根，最后访问右子树；
后序遍历： 先访问左子树，再访问右子树，最后访问树根；
层次遍历: 从根节点开始，逐层从左向右进行遍历。
二叉树节点类创建
# 二叉树的节点类
class TreeNode:
def __init__(self, data=None, left=None, right=None):
self.data = data
self.left = left
self.right = right
class Bitree:
def __init__(self, root=None):
self.root = root
def is_empty(self):
if self.root is None:
return True
else:
return False
# 先序遍历
def preOrder(self, node):
if node is None:
return
print(node.data, end=' ')
self.preOrder(node.left)
self.preOrder(node.right)
# 中序遍历
def inOrder(self, node):
if node is None:
return
self.inOrder(node.left)
print(node.data, end=' ')
self.inOrder(node.right)
# 后序遍历
def postOrder(self, node):
if node is None:
return
self.postOrder(node.left)
self.postOrder(node.right)
print(node.data, end=' ')
# 层次遍历
def levelOrder(self, node):
qu = LQueue()
qu.enqueue(node) # 先将根结点入队
while not qu.is_empty():
node = qu.dequeue() # 出队时打印
print(node.data, end=' ')
if node.left:
qu.enqueue(node.left)
if node.right:
qu.enqueue(node.right)
递归思想和实践
- 什么是递归？
所谓递归函数是指一个函数的函数体中直接调用或间接调用了该函数自身的函数。这里的直接调用是指一个函数的函数体中含有调用自身的语句，间接调用是指一个函数在函数体里有调用了其它函数，而其它函数又反过来调用了该函数的情况。
- 递归函数调用的执行过程分为两个阶段
递推阶段：从原问题出发，按递归公式递推从未知到已知，最终达到递归终止条件。
回归阶段：按递归终止条件求出结果，逆向逐步代入递归公式，回归到原问题求解。
- 优点与缺点
优点：递归可以把问题简单化，让思路更为清晰,代码更简洁
缺点：递归因系统环境影响大，当递归深度太大时，可能会得到不可预知的结果