第五章 树：在前面几章里讨论的数据结构都属于线性结构，线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。非线性结构是指在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树形结构是一类十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。本章主要介绍树的基本概念以及最典型的树结构——二叉树的相关概念及基本操作。5.1树的基本概念:本节主要介绍树的基本概念和术语，要求理解这些基本概念，后面的讲解会用到这些概念。[单选题]引入二叉线索树的目的是（ ）。
5.2二叉树:本节主要介绍二叉树的基本概念及二叉树的性质及二叉树的遍历方法，要求掌握二叉树的结构特性，了解相应的证明方法。遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。不仅要熟练掌握各种遍历策略的递归算法，了解遍历过程中“栈”的作用和状态，而且能灵活运用遍历算法实现二叉树的其他操作。
5.3线索二叉树:遍历二叉树是以一定规则将二叉树中所有结点排列为一个线性序列，得到二叉树结点的先序序列、中序序列或后序序列。在该序列中，除第一个结点外，每个结点有且仅有一个直接前驱结点；除最后一个结点外，每个结点有且仅有一个直接后继结点。这实质上是对一个非线性结构进行线性化的操作。为了保存结点在某种遍历序列中得到的直接前驱和直接后继的位置信息，可在二叉链表存储结构中增加两个指针域来指示。这些指向直接前驱结点和指向直接后继结点的指针被称为线索，增加了线索的二叉树称为线索二叉树。本节主要介绍了线索二叉树的定义、建立线索二叉树和遍历线索二叉树的方法，要求理解线索二叉树的概念，掌握线索二叉树的相关操作算法及其实现方法。
加快查找结点的前驱或后继的速度
为了能在二叉树中方便的进行插入与删除
使二叉树的遍历结果唯一
为了能方便的找到双亲
答案：
加快查找结点的前驱或后继的速度
[单选题]n个结点的线索二叉树上含有的线索数为（ ）。
n
n＋l
n－l
2n[单选题]由3 个结点可以构造出多少种不同的二叉树（ ）。
5
2
4
3[单选题]已知一算术表达式的中缀形式为 A+B*C-D/E，后缀形式为ABC*+DE/-，其前缀形式为( )。
-A+B*CD/E
-+A*BC/DE
-A+B*C/DE
-+*ABC/DE[单选题]若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）。
不确定
15
11
9[单选题]有关二叉树下列说法正确的是（ ）。
二叉树中任何一个结点的度都为2
二叉树的度为2
二叉树中至少有一个结点的度为2
一棵二叉树的度可以小于2[单选题]一个具有1025个结点的二叉树的高h为（ ）。
10
10至1024之间
11
11至1025之间[单选题]若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。
前序
按层次
后序
中序[单选题]若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( )
X的右子树中最左的结点
X的右子树的根
X的双亲
X的左子树中最右结点[单选题]二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中序遍历: HFIEJKG 。该二叉树根的右子树的根是（ ）。
F
H
E
G
温馨提示支付 ￥1.00 元后可查看付费内容,请先翻页预览!
