人与人之间，最大的吸引力，不是您的容颜，不是您的财富，也不是您的才华。而是，您传递给对方的温暖和踏实，以及传递给对方的那份正能量！
链表、队列都是一对一的线性结构，那么一对多的情况如何处理呢？“树”有效的解决了这种一对多的数据结构关系。
非线性结构：每个元素可以有多个前驱和后继；
1.树
树是n（n>=0）个元素的集合;
1.树只有一个特殊的没有前驱的元素，成为树的根Root
2.树中除了根节点外，其余元素只能有一个前驱，可以有0、对个后继；
递归定义：
树（Tree）是n（n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：
1.有且仅有一个特定的称为根（root）的结点；
2.当n>1时，其余结点可分为m(m>0)个互补交互的有限集T1、T2...Tm，其中每一个集合本身又是一棵树，并称为根的子树（SubTree）。
1.1 树的特点
1.唯一的根；
2.子树不相交；
3.除了根以外，每个元素只有一个前驱或对个后继；
4.根结点没有双亲结点（前驱），叶子结点没有孩子结点（后继）；
5.vi 是 vj 的双亲，则L(vi) = L（vj）-1, 也就是说双亲比孩子结点的层次小1；
2.结点的分类
结点：树中的数据元素；
结点的度degree : 结点拥有的子树的数目称为结点的度，记为d(v);
叶子结点：结点的度为0， 称为叶子结点leaf、终端结点、末端结点
分支结点：结点的度不为0，称为非终端结点或分支结点
分支：结点之间的关系；
内部结点：除根节点外的分支结点吗，当然也不包括叶子结点；
树的度 是树内各结点的度的最大值。D结点度（后继数目）最大为3，树的度数就是3；
3.结点之间的关系
孩子（Child）和双亲（Parent）：结点的子树的根，相应的，该结点称为孩子的双亲。（注意是双亲，不是单亲）
兄弟（sibling）：同一个双亲的孩子之间互称兄弟。
结点的祖先：从根结点到该结点所经过分支上的所有结点。
子孙：以某结点为根的子树中的任一结点都称为该节点的子孙。
无序树和有序树：如果将树中结点的各子树看成从左至右是有次序的，不能互换的(兄弟有大小、有先后次序；)，则称该数为有序树，否则为无序树。
路径长度 = 路劲上节点数 - 1，也是分支树；
森林(fores):m(m>=0)棵互不相交的树的集合。 相交的话就是 图了；
eg:对于结点而言，其子树的集合就是森林，A结点的2棵子树的集合就是森林；
4.二叉数
什么是二叉树：每个节点最多有两个子树的树结构，通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）
在Python3中，已有实现好的二叉树的模块：binarytree模块；可通过pip安装此模块：pip install binarytree 。
二叉树是有序树
1.每个结点最多2棵子树，不存在度数大于2的结点；
2.它是有序树，左子树、右子树是顺序的，不能交换次序；
3.即使某个结点只有一颗子树，也要确定它是左子树还是右子树；
4.1二叉树的5种基本形态
空二叉树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点只有左子树和右节点（满二叉树）
满二叉树：所有叶节点都在最底层的完全二叉树；
1.K为深度（1《 k《 n），则结点综述为2^k -1 ;
完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
重点性质：
1.完全二叉树由满二叉树引出；
2.满二叉树一定是完全二叉树，但完全二叉树不是满二叉树；
3.第d层所有节点从左向右连续地紧密排列
4.1二叉树的性质
性质：
1.在二叉树的 第 i 层 上至多有 2^(i-1) 个结点(i>=1)
2.深度为K的二叉树，至多有 2^k -1个结点（k>=1）
3.对于任意一颗二叉树T,如果其终端节点数为 n0(叶子节点数),度数为2的节点数为n2,则 n0=n2 + 1 ; 叶子结点数-1 = 度数为2的结点数
总结点数：n=n0+n1+n2 ; n1为度数为1的结点总数；
2*n2+n1=n0+n1+n2-1 => n2=n0-14.具有n个结点的完全二叉树的深度为int(log2n)+1 或者 math.ceil(log2(n+1))
性质5很重要，会经常用到；
图片.png
网友评论