元素赋给一个指定的变量。这个运算不删除栈顶 元素,只是将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为 0 时,说明栈空,读 不
到栈顶元素。
小技巧:栈是按照"先进后出"或"后进先出"的原则组织数据,但是出栈方式有多种选择, 在考题中经常考查各种不同的出栈方式。 考点 6 线性链表的基本概念 考试链接: 考点 6 在笔试考试中出现的几率为 30%,主要是以选择的形式出现,分值为 2 分,此考点 为识记内容。重点识记结点的组成。 在链式存储方式中, 要求每个结点由两部分组成: 一部分用于存放数据元素值, 称为数据域, 另一部分用于存放指针,称为指针域。其中指针用于指向该结点的前一个或后一个结点(即 前件或后件) 。 链式存储方式既可用于表示线性结构,也可用于表示非线性结构。 (1)线性链表 线性表的链式存储结构称为线性链表。 在某些应用中,对线性链表中的每个结点设置两个指针,一个称为左指针,用以指向其前件
结点;另一个称为右指针,用以指向其后件结点。这样的表称为双向链表。 (2)带链的栈 栈也是线性表, 也可以采用链式存储结构。 带链的栈可以用来收集计算机存储空间中所有空 闲的存储结点,这种带链的栈称为可利用栈。
疑难解答:在链式结构中,存储空间位置关系与逻辑关系是什么? 在链式存储结构中, 存储数据结构的存储空间可以不连续, 各数据结点的存储顺序与数据元 素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。 1.4 树与二叉树 考点 7 树与二叉树及其基本性质 考试链接: 考点 7 在笔试考试中,是一个必考的内容,在笔试考试中出现的几率为 100%,主要是以选 择的形式出现,有时也有出现在填空题中,分值为 2 分,此考点为重点掌握内容。重点识记 树及二叉树的性质。 误区警示: 满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。应该注意二者的区别。 1、树的基本概念 树(tree)是一种简单的非线性结构。在树结构中,每一个结点只有一个前件,称为父结点, 没有前件的结点只有一个,称为树的根结点。每一个结点可以有多个后件,它们称为该结点 的子结点。没有后件的结点称为叶子结点。 在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为 0。在树中,所 有结点中的最大的度称为树的度。 2、二叉树及其基本性质 (1)二叉树的定义 二叉树是一种很有用的非线性结构,具有以下两个特点: ①非空二叉树只有一个根结点; ②每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。 由以上特点可以看出,在二叉树中,每一个结点的度最大为 2,即所有子树(左子树或右子 树)也均为二叉树,而树结构中的每一个结点
的度可以是任意的。另外,二叉树中的每个结 点的子树被明显地分为左子树和右子树。 在二叉树中, 一个结点可以只有左子树而没有右子 树,也可以只有右子树而没有左子树。当一个结点既没有左子树也没有右子树时,该结点即 为叶子结点。 (2)二叉树的基本性质 二叉树具有以下几个性质: 性质 1:在二叉树的第 k 层上,最多有 2k-1(k≥1)个结点; 性质 2:深度为 m 的二叉树最多有 2m-1 个结点; 性质 3:在任意一棵二叉树中,度为 0 的结点(即叶子结点)总是比度为 2 的结点多一个。 性质 4:具有 n 个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]表示取 log2n 的整数部分。
小技巧:在二叉树的遍历中,无论是前序遍历,中序遍历还是后序遍历,二叉树的叶子结 点的先后顺序都是不变的。 3、满二叉树与完全二叉树 满二叉树是指这样的一种二叉树:除最后一层外,每一层上的所有结点都有两个子结点。在
满二叉树中,每一层上的结点数都达到最大值,即在满二叉树的第 k 层上有 2k-1 个结点, 且