Python数据结构与算法——第二十课树结构/二叉树/插入/中序遍历

　　树结构

　　树结构生活中的树结构几乎随处可见。比如总公司下面有多个分公司，分公司下面还有分公司；国家的行政单位是省、市、县，层层分支；一根燃气管道，分成多个分支进入各个城市，再分成多个分支进入社区等，这些都可称为树结构。设计出一棵优良的树结构，对提高效率，降低消耗具有非常现实的意义。同时在数学应用中，树结构也具有非常独特的应用价值。比如一棵平衡树，查找和插入的时间复杂度都是O(log2N)级；当数据量十分巨大时，线性结构的O(N)和树结构的O(1og2N)有天壤之别的效率差异。比如N为65536(2的16次方)时，链表平均查找次数是3万多次，而平衡树只需要16次，效率相差很大。下面介绍树、森林、二叉树这些同属树结构类型的概念。

　　树、森林、二叉树

　　我们先看树、森林、二叉树的概念。

　　(1)树：树是一种数据结构，它是由n(≥1)个有限节点组成一个具有层次关系的集合。把它称为“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。其具有以下特点：

　　①每个节点有零个或多个子节点；没有父节点的节点称为根节点。

　　②每一个非根节点有且只有一个父节点。

　　③除了根节点外，每个子节点可分为多个不相交的子树。

　　先了解常用的树基本术语，其包括：

　　①度：可分为“节点的度”与“树的度”。节点的度是指一个节点子树（节点）的个数；树的度是指树中所有节点的度中的最大值。

　　②叶子节点：是指没有子树的节点。

　　③层：树是有层次的，一般根节点为第0层。规定根节点到某节点的路径长度为该节点的层数。

　　④深度：树中节点的最大层数。

　　⑤兄弟：同一双亲的节点，互为兄弟。

　　⑥堂兄弟：双亲在同一层次的节点，互为堂兄弟。

　　⑦祖先：从根节点到该节点的路径上的所有节点都是该节点的祖先。

　　⑧子孙：以某一节点为根的子树上的所有节点都是该节点的子孙。

　　(2)森林：由若干棵互不相交的树组成的集合称为森林。任何一棵树，删除了根节点就变成了森林。

　　(3)二叉树：二叉树是每个节点最多有两个子树的树结构。通常子树被称为“左子树”(left subtree)和“右子树”(right subtree)。不过，二叉树不是树的一种特殊情形，尽管其与树有许多相似之处，但树和二叉树有两个主要差别：

　　①树中每个节点的最多子节点数量没有限制，而二又树每个节点的最大子节点数量为2。

　　②树的节点无左、右之分，面二叉树的节点有左，右之分。

　　常见的二又树类型包括：满二叉树、完全二叉树、平衡二叉树、二叉搜索树，红黑树，哈夫曼树等。由于数据结构中最常用到的结构就是二又树，所以本章只讲解二叉树结构。

　　二叉排序树

　　二叉排序树(Binary Sort Tree，又称为二叉搜索树或二叉查找树)或者是一棵空树，或者具有下列性质的二叉树：

　　(1)若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值。

　　(2)若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值。

　　(3)它的左，右子树也分别为二叉排序树。

　　二叉排序树空间结构如下图所示。

　　二叉排序树的插入与中序遍历

　　二叉排序树的类结构包然：节点和树。

　　①节点：包含数据引用、左指针、右指针、插人递归方法、遍历递归方法等。

　　②树：包括根节点指针、差入方法、遍历方法等。

　　下面介绍二叉排序树的插入方法和遍历方法，其遍历方法又分为3种，这里先介绍中序遍历。

　　(1)二叉排序树的插入算法：二叉排序树从限节点开始，比较待插入的节点数据和当前节点数都的大小，如果插入节点数据小于当前节点数据，则向左指针寻求继续比较，如果左指针为空，节点作为叶子节点添加到当前节点的左指针，如果插入节点数据大于或等于当前节点数据，则反之。若二叉排序树为空，则首先单独生成根节点，注意：新插入的节点总是二叉排序树的叶子节点。

　　(2)二叉排序树的中序遍历算法：中序遍历首先遍历左子树，然后访问根节点，最后遍历右子树。若此树3个方向都为空则结束返回；若任一分支不为空则视此分支为1棵新的二叉排序树，递归执行：

　　①遍历此分支的左子树，

　　②访问此分支的根节点，

　　③遍历此分支的右子树。

如果还有分支，继续递归…...此类二叉排序树按照中序遍历后得到的最终结果是一个从小到大的排序列表。

　　二叉排序树的插入操作的算法图解如下图所示。