共计 2688 个字符，预计需要花费 7 分钟才能阅读完成。
一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组 A[1..n]中，则二叉树中第 i 个结点（i 从 1 开始用上述方法编号）的右孩子在数组 A 中的位置是（条件不足，无法确定）
必须是完全二叉树才能确定，如下图：
当为完全二叉树时，为 2i+1
下面几个符号串编码集合中，不是前缀编码的是（B）。
- A. {0,10,110,1111}
- B. {11,10,001,101,0001}
- C. {00,010,0110,1000}
- D. {b,c,aa,ac,aba,abb,abc}
前缀编码：前缀编码，就是哈夫曼编码，即二叉树的一种应用，用来压缩文件体积。假设一篇文章里各种单词出现次数不同，那么用不同的编码表示不同单词，可以对文件体积进行压缩。
哈夫曼编码也就是前缀编码，要求是尽量减缩某些出现频率高的文字符号的编码，但必须保证任一字符编码不是另一个字符的前缀—，否则会出错。比如 abcd，如果用最后一个编写 a =0，b=1，c=00，d=11，那么 0011 就不知道是 aabb 还是 cd 了。
总之，前缀编码，在一个字符集中，任何一个字符的编码都不是另一个字符编码的前缀
设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为 M1，M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是（M2+M3）。
根据森林转换为二叉树的法则, 二叉树的根结点通常是第一棵树的结点, 二叉树的左子树是由第一棵树删去根后所得所有子树构成的, 二叉树的右子树是由其它树 (第二，第三棵树) 构成的, 故左子树结点个数是 M1-1, 右子树上的结点个数是 M2+M3。
已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac , 它的前序遍历是（cedba）。
首先看后序遍历，最后的 c 是二叉树的根节点，然后看中序遍历，最后一个又是 c，所以这个二叉树根节点没有右子树。
c 的位置得到后，再看后序遍历，e 在 c 前面，所以 e 是 c 的左孩子节点，e 的位置得到。
然后再看中序遍历，e 前面只有一个 d，所以 d 是 e 的左孩子节点，d 的位置得到；剩下的 b 和 a 就在 e 的右子树。
然后再看后序遍历，d 是一个叶子节点，那么就还有一个叶子节点，那么这个节点就一定是 a，那么 b 就是 e 的右孩子节点，最后再结合中序遍历就可得出所表示得二叉树。
总之，先根据后序遍历确定根节点（最后一个位置），再到中序遍历中分开左右子树；然后从后序遍历中确定左右子树的根节点，以此类推
引入二叉线索树的目的是（A）
- A. 加快查找结点的前驱或后继的速度
- B. 为了能在二叉树中方便的进行插入与删除
- C. 为了能方便的找到双亲
- D. 使二叉树的遍历结果唯一
首先明确，对于 n 个结点的二叉树，在二叉链存储结构中有 n + 1 个空链域。我们就是利用这些空链域，来存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树
在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（完全相同）
遍历方法中的先序、中序、后序指的是对根的访问顺序，而对于叶子结点都采用先遍历左子树，后遍历右子树。
一棵二叉树高度为 h(根的高度为 1), 所有结点的度或为 0 或为 2, 则这棵二叉树最少有 (2h-1) 个结点
首先明确，n0 表示度为 0 的根节点，即叶子节点；如果我们想撑起来一个高度为 h 的就只能靠 n2，由于高度为 h，那么我们只要 h - 1 层每层都有一个 n2 就可以撑起来 h 的高度；
又因为 n0=n2+1，所以总结点个数为 h -1+h
一棵左右子树均不空的二叉树在前序线索化后, 其中空的链域的个数是(1)
首先明确，对于 n 个结点的二叉树，在二叉链存储结构中有 n + 1 个空链域。这是因为 n 个节点有 2n 个指针，而 n 个节点中有 n - 1 条边（除了头结点没有边，其余节点都有一个父节点，相当于都有 1 条边，共 n - 1 条），所以剩下的空链域就是 2n-(n-1)=n+1，即 n + 1 个空指针。
前序遍历最后一个结点的右指针为空；后序遍历第一个节点的左指针为空；中序遍历的第一个和最后一个节点为空。即前序和后序线索化之后，空链域为 1；中序线索化后，空链域为 2
利用二叉链表存储树, 则根结点的右指针是(空)
二叉链表又称为左孩子右兄弟存储法。根节点没有兄弟，所以为空
一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（501）
跟这个同一深度的满二叉树的结点数为 1023, 其中最后一行 512 个；
而这个 1001 个少了 22 个, 少在了最后一行, 所以这缺失的 22 个的父结点都是叶子, 共 22/2=11 个；
而这一行剩下 512-22 = 490 个叶子, 所以总共 490+11=501 个叶子结点
给定一棵树, 可以找到一棵二叉树与之对应
二叉树的做成是按照左子女右兄弟的规则来的, 这样的方式是为了保证一棵树做成二叉树之后可以还原成那棵树。
二叉树只是作为树的更高效率的存储方式, 所以为了保证树结构不会被弄乱, 按照上面的逻辑, 一棵树只能对应一棵二叉树
一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。(错)
树的前根遍历和对应二叉树的前序遍历相同，树的后根遍历与对应二叉树的中序遍历相同。
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列
一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
这样的树称为二叉排序树。
按中序遍历二叉排序树，所得到的中序遍历序列是一个递增有序序列。
用一维数组存储二叉树时, 总是以前序遍历顺序存储结点(错)
一维数组存储二叉树，总是以层次遍历的顺序存储。
二叉树的存储结构分为顺序存储和链式存储。
顺序存储：即用一维数组存储二叉树中的结点。采用层次遍历，从上至下从左到右依次存储，根节点存储在下标为 1 的位置，对于任意位置 i 的结点，其左子树位于 2i，右子树位于 2i+1，所以树结点的序号可以唯一反映出结点的逻辑关系。完全二叉树和满二叉树采用顺序存储比较合适。非完全二叉树需要添加空结点使之变成完全二叉树进行顺序存储，但是这样可能造成空间的浪费。
链式存储结构：用链表表示二叉树。每个结点存储自身的数据以及两个分别指向左孩子和右孩子结点的指针。（lchild, data, rchild）
对于有 n 个结点的二叉树, 其高度为 log2 n（错）
我们先想一个极端的例子，每层只有一个结点，则深度为 n。
完全二叉树的高度为【logn】+1，（【】为向上取整），或者为 log(2*n)，两者表示等价。
