根节点：左叶子节点
• 根节点：右叶子节点
• 根节点：特点：每一个节点都可以作为某一棵子树的根节点

class Node:def __init__(self, item):self.item = itemself.left = None  # 指向该节点的左叶子节点self.right = None  # 指向该节点的右叶子节点class Tree:def __init__(self):  # 构建一棵空树self.root = None  # 永远指向二叉树中的根节点def insert(self, item):  # 添加节点node = Node(item)# 如果是个空树if self.root is None:self.root = nodereturn# 如果树不是空树cur = self.rootq = [cur]  # 将根节点放入列表中while True:n = q.pop(0)  # 取出列表中的节点判断它的左右两个子节点是否为空if n.left is not None:q.append(n.left)  # 如果左子节点不为空就把它当做下一个主节点放入列表中else:n.left = node  # 如果左子节点为空就把加入的新节点插入breakif n.right is not None:q.append(n.right)  # 同上判断右节点else:n.right = nodebreakdef travel(self):  # 查看所有节点cur = self.rootq = [cur]while q:n = q.pop(0)print(n.item)if n.left is not None:q.append(n.left)if n.right is not None:q.append(n.right)tree = Tree()tree.insert(1)tree.insert(2)tree.insert(3)tree.insert(4)tree.insert(5)tree.insert(6)tree.travel()# 输出123456

二、二叉树的遍历

**广度遍历：**横向遍历

• 上述代码中的遍历就是广度遍历。自上到下逐行遍历叫做广度遍历。

**深度遍历：**纵向遍历。前中后序遍历形式需要作用到子树中，前中后序的前中后指的是子树中根节点的位置。

• 前序：根左右——>先遍历子树的根节点，在遍历子树的左节点然后是右节点
• 中序：左根右
• 后续：左右根

深度遍历的实现思路：

• 深度遍历是需要作用到每一棵子树中
• 子树和子树之间的区别体现在跟节点中
• 如果写一个函数，该函数可以将一个子树中的节点进行遍历，则将改函数作用到其他子树中就可以将整棵树进行深度遍历

class Node:def __init__(self, item):self.item = itemself.left = None  # 指向该节点的左叶子节点self.right = None  # 指向该节点的右叶子节点class Tree:def __init__(self):  # 构建一棵空树self.root = None  # 永远指向二叉树中的根节点def insert(self, item):  # 添加节点node = Node(item)# 如果是个空树if self.root is None:self.root = nodereturn# 如果树不是空树cur = self.rootq = [cur]  # 将根节点放入列表中while True:n = q.pop(0)  # 取出列表中的节点判断它的左右两个子节点是否为空if n.left is not None:q.append(n.left)  # 如果左子节点不为空就把它当做下一个主节点放入列表中else:n.left = node  # 如果左子节点为空就把加入的新节点插入breakif n.right is not None:q.append(n.right)  # 同上判断右节点else:n.right = nodebreak# 查看所有节点def travel(self):cur = self.rootq = [cur]while q:n = q.pop(0)print(n.item)if n.left is not None:q.append(n.left)if n.right is not None:q.append(n.right)# 前序遍历# 参数root表示的是子树的根节点，需要给递归调用的forward传入不同子树的根节点def forward(self, root):if root is None:  # 直到传入的节点为空才停止递归returnprint(root.item)self.forward(root.left)self.forward(root.right)# 中序遍历def middle(self, root):  # 左跟右if root is None:returnself.middle(root.left)print(root.item)self.middle(root.right)# 后续遍历def back(self, root):  # 左右根if root is None:returnself.back(root.left)self.back(root.right)print(root.item)tree = Tree()tree.insert(1)tree.insert(2)tree.insert(3)tree.insert(4)tree.insert(5)tree.insert(6)tree.insert(7)tree.forward(tree.root)# 输出1245367

三、排序二叉树

排序二叉树就是在二叉树插入数据的时候，和根节点做对比，大于根节点就插入右侧，小于就插入左侧，右侧或左侧有就和对应节点做对比，再次判断插入数据。

class Node:def __init__(self, item):self.item = itemself.left = None  # 指向该节点的左叶子节点self.right = None  # 指向该节点的右叶子节点class SortTree:def __init__(self):  # 构建一棵空树self.root = None  # 永远指向二叉树中的根节点def insert(self, item):  # 添加节点node = Node(item)if self.root is None:  # 树为空的情况self.root = nodereturncur = self.rootwhile True:  # 循环开始从根节点开始if cur.item > item:  # 插入的值小于根节点，该节点需要插入到根节点的左侧if cur.left is None:cur.left = nodebreak  # 插入即退出else:  # 左节点不为空，那么就再次循环从左节点开始cur = cur.leftelse:if cur.right is None:  # 插入的值大于根节点，就插入该节点右侧cur.right = nodebreakelse:cur = cur.right  # 同上，不为空再次从此节点循环# 中序遍历def middle(self, root):  # 左跟右if root is None:returnself.middle(root.left)print(root.item)self.middle(root.right)alist = [3, 8, 5, 4, 7, 6, 2, 1]tree = SortTree()for item in alist:tree.insert(item)tree.middle(tree.root)# 输出12345678