目录
树
树的定义
树的相关概念
树的存储结构
树在实际中的运用（表示文件系统的目录树结构 ）
二叉树
二叉树的定义
现实中的二叉树
二叉树的特点
特殊的二叉树
1.斜树
2.满二叉树
3.完全二叉树
二叉树的性质
性质1：二叉树的第i层至多有个
性质2：深度为k的二叉树至多有个结点（k≥1）。
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。
性质4：具有n个结点的完全二叉树的深度为（[x]表示不大于x的最大整数）。
性质5：如果对一棵有n个结点的完全二叉树（其深度为）的结点按层序编号（从第1层到第层，每层从左到右），对任一结点i（1≤i≤n）有：
练习题
树
树的定义
树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
- 有一个特殊的结点，称为根结点，根节点没有前驱结点
- 除根节点外，其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm，其中每一个集合Ti(1，意味着
，所以
，不等式两边取对数，得到
，而k作为深度也是整数，因此
。
性质5：如果对一棵有n个结点的完全二叉树（其深度为
）的结点按层序编号（从第1层到第
- 如果i=1，则结点/是二叉树的根，无双亲；如果/>1，则其双亲是结点[i/2]。
- 如果2i>n，则结点/无左孩子（结点/为叶子结点）；否则其左孩子是结点2i。
- 如果2i+1>n，则结点/无右孩子；否则其右孩子是结点2i+1。
我们以下图为例，来理解这个性质。这是一个完全二叉树，深度为4，结点总数是10。
对于第一条来说是很显然的，i=1时就是根结点。i>1时，比如结点7，它的双亲就是[7/2]=3，结点9，它的双亲就是[9/2]=4。
第二条，比如结点6，因为2×6=12超过了结点总数10，所以结点6无左孩子，它是叶子结点。同样，而结点5，因为2×5=10正好是结点总数10，所以它的左孩子是结点10。
第三条，比如结点5，因为2×5+1=11，大于结点总数10，所以它无右孩子。而结点3，因为2×3+1=7小于10，所以它的右孩子是结点7。
练习题
我特地为大家留了几道练习题，帮大家巩固一下
4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12
5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386
1-5答案是BAABB
还没有评论，来说两句吧...