python树形结构

.树形结构:

定义:树(Tree)是n(n>=0)个结点的有限集合T,它满足两个条件:有且只有一个特别的称为根(Toot)的结点,其余的结点可以分为m(m>=0)个互不相交的集合T1,T2……、tm,其中第一个集合又是一棵树,并称为其根的子树(Subtree)

应用:比如网站的每一个连接页都属于树形模型


基本概念:

.一个节点的子树的个数称为该节点的度数。一棵树的度数指的是该结点的最大的度数。

一个结点的子树之根结点称为该结点的子结点,该结点称为它们的父结点,同一结点之间各各结点称为兄弟结点。一根树的根结点没的父结点,叶结点没有子结点。

.一个结点系列k1,k2……ki,ki+1……kj,并满足ki是ik+1的父结点就称为从ki到kj的路径,路径的长度为j-1,即路径中的边数。路径中前面的结点是后面结点的祖先,后面结点是前面结点的子孙。

.节点的层数等于父结点加一,根结点层数定义为一。树结点中的最大值称为该树的高度或深度。

.m(m>=0)根互不相交的树的集合称为森林。树去掉根结点就称为树林,森林加上一个新的根结点又称为树。


二叉树:(每个结点都是两度,即只有两个子结点)

定义:二叉树(Binary Tree)是n(n>=0)个结点有有限集合,它或者是空集,或者是由一根结点以及两个互不相交的分别称为左子树和右子树的二叉树组成。二叉树与普通有序树不同,二叉树严格区分左孩子和右孩子,即使有一个子结点的也要区分左右。


2.二叉树的特征

二叉树第1(21)层上的节点最多为2-1个。

深度为k(k21)的二叉树最多有2k一1个节点。

·在任意一棵二叉树中,树叶的数目比度数为2的节点的数目多一。

·满二叉树:深度为k(k21)时有2k一1个节点的二叉树。

.完全二叉树:只有最下面两层有度数小于2的节点,且最下面一层的

叶节点集中在最左边的若干位置上。

原文链接:,转发请注明来源!