计算机二级公共基础专题探究_二叉树.doc资源-CSDN文库

版权申诉

173 浏览量 2022-07-08 10:34:37 上传评论收藏 765KB DOC 举报

资源推荐

资源详情

资源评论

.

.页脚.

公共基础专题探究——二叉树

1．6 树与二叉树

树是一种简单的非线性结构，所有元素之间具有明显的层次特性。

在树结构中，没有前件的结点只有一个，称为树的根结点，简称树的根。

每一个结点可以有多个后件，称为该结点的子结点。

没有后件的结点称为叶子结点。

在树结构中，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度。

树的最大层次称为树的深度。

二叉树的特点：（1）非空二叉树只有一个根结点；（2）每一个结点最多有两棵子树，且分别称

为该结点的左子树与右子树。

二叉树的基本性质：必考的题目

（1）在二叉树的第 k 层上，最多有 2

k-1

(k≥1)个结点；

（2）深度为 m 的二叉树最多有 2

m

-1 个结点；

（3）度为 0 的结点（即叶子结点）总是比度为 2 的结点多一个；

（4）二叉树中 n = n

0

+n

1

+n

2

满二叉树是指除最后一层外，每一层上的所有结点有两个子结点，则 k 层上有 2k-1 个结点深度

为 m 的满二叉树有 2m-1 个结点。

完全二叉树是指除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若

干结点。

二叉树存储结构采用链式存储结构，对于满二叉树与完全二叉树可以按层序进行顺序存储。

二叉树的遍历：（一般画个图要你把顺序写出来）

（1）前序遍历（DLR），首先访问根结点，然后遍历左子树，最后遍历右子树；

（2）中序遍历（LDR），首先遍历左子树，然后访问根结点，最后遍历右子树；

（3）后序遍历（LRD）首先遍历左子树，然后访问遍历右子树，最后访问根结点。

序号

高频考点

1

树是简单的非线性结构，二叉树作为树的一种也是一种非线性结构。

剩余14页未读，继续阅读

内容反馈

版权申诉

智慧安全方案

粉丝: 3694
资源: 59万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip