数据结构(树和二叉树)

发布于 2021-09-28  730 次阅读


5.1 树和二叉树的定义

5.1.1 树的定义

file

树形结构(非线性结构)

file

file

file

file

5.1.2 树的基本术语

file

树的深度(高度):树中结点的最大层次.

file

森林:把m(m>=0)颗互不相交的书的集合。
把根节点删除就编程了森林。

file

file

5.1.3 二叉树的定义

file

file

file

file

二叉树的5种基本形态

file

5.2 案例引入

案例5.1:数据压缩问题

file

案例5.2:利用二叉树求解表达式的值

file

5.3 树和二叉树的抽象数据类型定义

file

file

5.4 二叉树的性质和存储结构

性质1:

file

file

提问:第i层上至少有1个结点。

性质2:深度为K的二叉树之多有2^k-1个结点(k>=1)

file

提问:深度为K时至少有n个结点。

性质3:对任何一颗二叉树T,如果其叶子结点数为n0,度为u2的结点数为n2,则n0 = n2 +1;

file

两种特殊形式的二叉树

研究意义:它们在顺序存储方式下可以复原!

满二叉树

file

file

完全二叉树

file

是否是完全二叉树?

file

file

file

满二叉树一定是完全二叉树
但是完全二叉树是不一定为满二叉树的

性质4:具有n个节点的完全二叉树的深度为

file

file

file

性质5:

file

file

二叉树的性质与存储结构

file

二叉树的顺序存储

file

file

file

file

file

二叉树的链式存储结构

file

file

file

file

三叉链表

file


擦肩而过的概率