[数据结构和算法]树和二叉树（Python）

树是非线性数据结构的一种重要类型，它是由分支关系定义的分层结构

定义:

树（树）是n（n> 0）个节点T的有限集合，其中: 只有一个特定的节点数据结构 二叉树，称为树（根）的根

当n> 1时，其余节点可分为m（m> 0）个不相交的有限集T1，T2，... Tm，其中每个集合本身就是一棵树，称为根'S子树（subtree）

特征: 树中至少有一个节点-根树中的子树是不相交的集合

基本术语

节点（节点）-表示树中的元素，包括数据项和许多指向其子树的分支

节点的度数-节点具有叶的子树的数量-节点的度数为0

child（子）-节点子树的根称为节点的子

父母（父母）-子节点的上层节点称为节点〜

兄弟姐妹-父母相同的孩子

树的度数-树中最大的节点度数

节点的级别-从根节点开始，根是第一级，其子级是第二级...

depth（depth）-树中节点的最大层数

森林-m（m0）棵不相交的树木的集合

二叉树二叉树是一组有限元素. 该集合为空，或具有一个称为根节点（root）的元素和两个不相交的元素数据结构 二叉树，分别称为左和右子树. 二叉树组成.

二叉树的每个节点最多具有两个子树（没有节点的度数大于2），并且二叉树的子树分为左右两半，顺序不能颠倒.

二叉树的i层最多有2个^ {i-1}个节点

深度为k的二叉树最多具有2 ^ k-1个节点;

对于任何二叉树T，如果终端节点的数量为N0，度数为2的节点的数量为N2，则N0 = N2 + 1

遍历二叉树

遍历预购

如果树为空，则返回null操作. 否则，首先访问根节点，然后按照预顺序遍历左侧子树，然后按照预顺序遍历右侧子树. （W）类型（左中右）

中间顺序遍历

如果树为空，则返回null操作. 否则，从根节点开始（请注意，首先不访问根节点），中间顺序遍历根节点的左侧子树，然后访问根节点，最后中间顺序遍历根节点的右侧子树. （M）类型，（左中右）

后续遍历

如果树为空，则返回null操作. 否则，叶子和节点从左到右遍历以访问左右子树，最后到达根节点. （左右中央）逆时针（左右中央）

序列遍历

如果树为空，则返回null操作. 否则，访问将从树的第一层（即根节点）开始，并且从上到下逐层遍历. 在同一层中，从左到右依次访问节点.

交流研究QUN483787113;秘密数字樱桃

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-222720-1.html