本文回味一个非常基础的数据结构——二叉树,包括其基本的遍历方法,即前序、中序和后序遍历。然后回归代码,来看一看在 Python 可以如何以一个很简单的方式表达二叉树并用迭代器的方式实现这三种遍历。最后实现一个如何根据一个二叉树的前序和中序遍历来反向重建二叉树的方法。
Python版二叉查找树
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。
二叉查找树的特点则在于对于树中的每个节点X,它的左子树中所有项的值小于X中的项,而它的右子树中所有项的值大于X中的项。这意味着该树所有的元素都可以用某种一致的方式排序。如下图所示是一个二叉查找树:
为实现一个二叉查找树,我们将创建三个类:
BinaryTree:代表一个二叉树,实现初始化和操作;
EmptyNode:代表空节点;
BinaryNode:代表非空节点,具...