树的定义
非线性结构,n对n
由根和子树递归定义
树是n个节点的有限集合
树的基本术语
结点
-根结点:没有前驱结点
-结点的度:拥有子树个数
-树的度:结点度的最大值
-度为0的结点:叶子\终端结点
eles
-分支结点\内部结点:度不为0且不是根结点
二叉树的定义
类似于离散数学的范式,我们习惯将树全部转换为二叉树
二叉树和树是两个概念
案例引入
数据压缩问题:
编码
二叉树求解表达式的值:
用叶子结点存储数值,利用深度表示运算优先级
树和二叉树的ADT
无
二叉树的性质和存储结构
性质1:
要证明对任意一个i都有相同的性质
即证明i前面的数据的性质能推出第i个数据
-因为有归纳基,若证明了此性质,那么就可以推出任 意第i个元素的性质
性质2:
等比数列求和
性质3:
1,用前驱的边计算总边数
2,用后继的边计算总边数
3,总结点数等于度为0,1,2相加的总和
二叉树的性质和存储结构
满二叉树:
深度为k,达到最多的结点2的k次方-1
完全二叉树:
看图
性质4:
取任意的一个k层完全二叉树,他的节点数量在2k- 1次方到2的k次方之间,转换为底数为二的对数遍对挺k-1层到k层之间,也就是k层,故先取对数的底再加1便是该完全二叉树的深度
性质5:
双亲结点与孩子结点编号之间的关系
二叉树的存储结构
顺序存储:
按满二叉树的编号依次存放元素
链式存储结构:
-二叉链表:
用后继或者前驱存储边
-性质:
-三叉链表
如果需要找双亲,再加一个指针域