A.98B.99C.50D.48 答:A 【例6.2】深度为5的二叉树至多有个结点。 16B.32C.31D.10 容:相同满度时满二叉树结点最多,h=5的满二叉树结点个数=25-1=31。本题答案应为C。 3.二叉树存储结构 1)二叉树的顺序存储结构 (2)二叉链存储结构 typedef struct /*数据元素*/ struct node *k *指向左孩子*/ struct node* rchild:/指向右孩子*/ BTNode 4二叉树的遍历 1)先序遍历 void preorder (BTNode *t) printf(“%d”,t->data) preorder(t->child) (2)中序遍历 oid inorder btnode *t) I inorder(t->lchild) printf(“%d”,t->data) inorder(t->rchild):I (3)后序遍历 void postorder(BTNode t) i postorder(t->lchild) postorder(t->rchild printf(“%d”,t->data);} 注意:重点掌握基于遍历的递归算法设计 5.二叉树的构造 任何n(n≥0)个不同结点的二又树,都可由它的中序序列和先序序列惟一地确定 任何n(n≥0)个不同结点的二又树,都可由它的中序序列和后序序列惟一地确定 掌握它们的构造方法。 6.线索二叉树 (1)线索二叉树的概念 对于具有n个结点的二叉树,采用二叉链存储结构时,每个结点有两个指针域,总共有2n个指针域,又 由于只有n-1个结点被有效指针所指向(树根结点没有被有效指针域所指向),则共有2n-(n-1)=n+1个空链域 遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样 的指向该线性序列中的“前驱”和“后继”的指针,称作线索。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。 (2)二叉树进行线索化的过程 不要求掌握算法。 6.3哈夫曼树 1.哈夫曼树的定义 在n个带权叶子结点构成的所有二叉树中,带权路径长度WPL最小的二叉树称为哈夫曼树(或最优二叉树) 2.哈夫曼树的构造过程 3.哈夫曼编码的构造过程 第7章广义表 一个广义表中所含元素的个数称为它的长度 个广义表中括号嵌套的最大次数为它的深度A.98 B.99 C.50 D.48 答：A 【例 6.2】 深度为 5 的二叉树至多有 个结点。 A.16 B.32 C.31 D.10 答：相同满度时满二叉树结点最多，h=5 的满二叉树结点个数=25-1=31。本题答案应为 C。 3.二叉树存储结构 （1）二叉树的顺序存储结构 （2）二叉链存储结构 typedef struct node { ElemType data; /*数据元素*/ struct node *lchild; /*指向左孩子*/ struct node *rchild; /*指向右孩子*/ } BTNode; 4.二叉树的遍历 （1） 先序遍历 void preorder（BTNode ＊t） { printf(“%d”,t->data); preorder(t->lchild); preorder(t->rchild); } （2） 中序遍历 void inorder（BTNode ＊t） { inorder(t->lchild); printf(“%d”,t->data); inorder(t->rchild); } （3）后序遍历 void postorder（BTNode ＊t） { postorder(t->lchild); postorder(t->rchild); printf(“%d”,t->data); } 注意：重点掌握基于遍历的递归算法设计。 5.二叉树的构造 任何 n（n≥0）个不同结点的二又树，都可由它的中序序列和先序序列惟一地确定。 任何 n（n≥0）个不同结点的二又树，都可由它的中序序列和后序序列惟一地确定。 掌握它们的构造方法。 6.线索二叉树 (1)线索二叉树的概念 对于具有 n 个结点的二叉树，采用二叉链存储结构时，每个结点有两个指针域，总共有 2n 个指针域，又 由于只有 n-1 个结点被有效指针所指向（树根结点没有被有效指针域所指向），则共有 2n-(n-1)=n+1 个空链域。 遍历二叉树的结果是一个结点的线性序列。可以利用这些空链域存放指向结点的前驱和后继结点的指针。这样 的指向该线性序列中的“前驱”和“后继”的指针，称作线索。 对二叉树以某种方式遍历使其变为线索二叉树的过程称作按该方式对二叉树进行线索化。 (2) 二叉树进行线索化的过程 不要求掌握算法。 6.3 哈夫曼树 1.哈夫曼树的定义 在 n 个带权叶子结点构成的所有二叉树中，带权路径长度 WPL 最小的二叉树称为哈夫曼树（或最优二叉树） 。 2.哈夫曼树的构造过程 3.哈夫曼编码的构造过程 第 7 章 广义表 相关概念: 一个广义表中所含元素的个数称为它的长度. 一个广义表中括号嵌套的最大次数为它的深度