python定义树,树的遍历python

　　树与二叉树

　　在我们认识二叉树之前，我们首先要知道树的一些概念，以便于我们对二叉树的理解。

　　什么是树？

　　Tree(英文：tree)是一种抽象数据类型(ADT)或实现这种抽象数据类型的数据结构，用来模拟一个具有树形结构的数据集。

　　它是由n(n=1)个有限节点组成的层次集合。它被称为“树”，因为它看起来像一棵颠倒的树，也就是说，它的根朝上，叶子朝下。它具有以下特点3360

　　每个节点有零个或多个子节点；

　　没有父节点的节点称为根节点；

　　每个非根节点只有一个父节点；

　　除了根节点，每个子节点可以被分成多个不相交的子树；

　　树的术语：

　　一个节点的度数是：一个节点所包含的子树的个数称为该节点的度；

　　一棵树的度数是：在一棵树中，节点的度称为树的度；

　　根节点：树的最顶层节点，它被进一步划分为子节点。

　　父节点：子节点之上的级别是父节点。

　　兄弟节点：具有相同父节点的节点称为兄弟节点。

　　叶节点/终端节点：不再有子节点的节点是叶节点。

　　二叉树：

　　是一种特殊的二叉树，它具有以下特征：

　　每个节点最多有两个子树，节点的度为2。

　　左子树和右子树是有顺序的，顺序不能颠倒。

　　即使一个节点只有一个子树，也应该区分左右子树。

　　二叉树的性质：

　　在非空二叉树的第I层，最多有2i-1个节点(i=1)。

　　深度为k的二叉树中最多有2k-1个节点(k.1)

　　对于任意非空二叉树，如果叶节点数为n0，度为2的节点数为n2，则n0=N2 ^ 1。

　　击倒过程：在一棵二叉树中，除了叶节点(度为0)，只剩下度为2(n2)和度为1(n1)的节点。那么树中的节点总数为t=n0n1n2二叉树中，节点总数为T，而连接总数为T-1=2*n2 n1，所以有：n0 n1 n2-1=2 *n2 n1，得到n0=n2 1。

　　特殊的二叉树

　　满二叉树

　　在一棵二叉树中，除了叶节点外，其他所有节点的度都是2，所有的叶节点都在同一层上，这样二叉树就变成了全二叉树。

　　完全二叉树的特征：

　　一片叶子只能出现在最底层。

　　非叶节点的度数必须是2。

　　在具有相同深度的二叉树中，全二叉树具有最多的节点和叶节点。

　　完全二叉树

　　如果一棵二叉树在去掉最后的叶节点后是满的，并且最后的叶节点从左到右依次分布，这样的二叉树称为完全二叉树。

　　完全二叉树的特点：

　　一般叶子节点出现在最底层，如果叶子节点出现在倒数第二层，就必须出现在右边连续的位置。

　　最低的叶节点必须集中在左侧连续位置。

　　对于同一个节点二叉树，完全二叉树的深度最小(完全二叉树也是对的)。

　　小例题：

　　一棵完整的二叉树有200个节点，二叉树有()个叶节点？

　　解法：n0 n1 n2=200，其中n0=n2 1，n1=0或1 (n1=1，最低层节点数为奇数，最低层节点数为偶数，则n1=0)。因为n0是整数，所以最后计算出n0=100。

　　完全二叉树的性质：

　　具有n个节点的完全二叉树的深度为log2n-1。Log2n结果取整数部分。

　　如果具有n个节点的完全二叉树的节点按层次顺序编号，则任何层的节点i(1=i=n)

　　1.如果i=1，节点是二叉树的根，没有父节点；如果i1，其父节点是i/2，向下舍入。

　　2.如果2*1n，那么节点I没有左子，否则它的左子是2i。

　　3.如果21n，则该节点没有右子节点，否则右子节点是211。

　　验证：

　　第一条：

　　当i=1时，它是根节点。比如i1的时候，节点是7，他的父母是7/2=3；节点9的父节点是4。

　　第二条：

　　节点6，62=1210，所以节点6没有左子节点，是叶节点。节点5，52=10，左子是10，节点4是8。

　　第三条：

　　节点5，2*5 110，无右子，节点4，有右子。

　　更多Python相关知识，请移步Python视频教程继续学习！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。