于是，(1) 当n=2k时，h??log n??1，当没有度为1的结点时；h??log n??2，当有1个度为1的结点时。(2) 其他情况下，h??log n??2。
错误！未找到引用源。
void PrintBinaryTree ( BinTree bt, int indent ) {
if ( ! bt ) return;
for ( i=0; i
PrintBinaryTree ( bt->lchild, indent+1 ); PrintBinaryTree ( bt->rchild, indent+1 ); }
错误！未找到引用源。
void PrintBinaryTree ( BinTree bt, int level ) {
if ( ! bt ) return;
PrintBinaryTree ( bt->rchild, level+1 ); // 旋转后先打印右子树 for ( i=0; i
PrintBinaryTree ( bt->lchild, level+1 ); }
错误！未找到引用源。
分析：按层遍历完全二叉树，当遇到第一个空指针之后应该全都是空指针。 bool IsComplete ( BinTree bt ) {
// 按层遍历至第一个空指针 InitQueue ( Q ); EnQueue ( Q, bt );
while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p ); if ( p ) {
EnQueue ( Q, p->lchild ); EnQueue ( Q, p->rchild ); } else
break; // 遇到第一个空指针时停止遍历 }
// 检查队列中剩余元素是否全部是空指针 while ( ! QueueEmpty(Q) ) { DeQueue ( Q, p );
if ( ! p ) return false; // 不是完全二叉树 }
return true; // 完全二叉树 }
错误！未找到引用源。
分析：进行后序遍历时，栈中保存的是当前结点的所有祖先。所以，后序遍历二叉树，遇到该结点
时，取出栈中的内容即是所有祖先。 // 求二叉树bt中结点xptr的所有祖先
vector Ancestors ( BinTree bt, BinTree xptr ) {
stack s; stack tag; p = bt;
while ( p || ! s.empty() ) { if ( p ) {
s.push ( p ); tag.push ( 1 ); p = p->lchild; } else {
p = s.pop(); f = tag.pop(); if ( f==1 ) {
s.push ( p ); tag.push ( 2 ); p = p->rchild; } else {
if ( p==xptr ) {
v = s; // 当前栈的内容就是xptr的所有祖先 return v; }
p = NULL; } }
} // while
return vector(); // return a null vector }
注：这里为描述方便借助了C++中的某些描述方式。
错误！未找到引用源。
思路：用后序遍历求出两者的所有祖先，依次比较。 // 求二叉树bt中两个结点q和r的最近的共同祖先
BinTree LastAncestor ( BinTree bt, BinTree q, BinTree r ) {
stack sq, sr;
stack s; stack tag; // 求q和r的所有祖先 p = bt;
while ( p || ! s.empty() ) { if ( p ) {
s.push ( p ); tag.push ( 1 ); p = p->lchild; } else {
p = s.pop(); f = tag.pop(); if ( f==1 ) {
s.push ( p ); tag.push ( 2 ); p = p->rchild; } else {
if ( p==q ) sq = s; // q的所有祖先 if ( p==r ) sr = s; // s的所有祖先
p = NULL; } } }
// 先跳过不同层的祖先，然后依次比较同一层的祖先
if ( sq.size()>sr.size() ) while ( sq.size()>sr.size() ) sq.pop(); else while ( sr.size()>sq.size() ) sr.pop(); // 求q和r的最近的共同祖先
while ( !sq.empty() and (sq.top()!=sr.top()) ) { //寻找共同祖先 sq.pop(); sr.pop(); }
if ( !sq.empty() ) return sq.top(); else
return NULL; }
错误！未找到引用源。
分析：当左孩子的优先级低于根时需要加括号，根的优先级大于右孩子时也需要加括号。 void PrintExpression ( BinTree bt ) {
if ( bt==NULL ) return ;
if ( bt->lchild==NULL and bt->rchild==NULL ) print ( bt->data ); // 叶子结点直接打印 else {
// 左子树
brackets = bt->lchild and is_operator(bt->lchild->data)
and comp_operator(bt->lchild->data, bt->data)<0; // 左孩子优先级低于根 if ( brackets ) print (“(“); PrintExpression ( bt->lchild ); if ( brackets ) print (“)”); // 根结点
print ( bt->data ); // 右子树
brackets = bt->rchild and is_operator(bt->lchild->data)
and comp_operator(bt->data, bt->rchild->data)>0; // 根的优先级大于右孩子 if ( brackets ) print (“(“); PrintExpression ( bt->rchild ); if ( brackets ) print (“)“); } }
注：is_operator(c)判断c是否是运算符；comp_operator(a,b)比较两个运算符的优先级。 bool is_operator(char c) { // 判断c是否是运算符 return c=='+' || c=='-' || c=='*' || c=='/'; }
int comp_operator(char opl, char opr) { // 比较两个运算符的优先级 return (opl=='*' || opl=='/' || opr=='+' || opr=='-') ? +1 : -1; }
错误！未找到引用源。
分析：树中的叶子没有孩子，即firstchild为空。 // 求树t中叶子结点的个数 int LeafCount ( CSTree t ) {
if ( t==NULL ) return 0; // 空树 if ( t->firstchild==NULL ) // 没有孩子 return 1 + LeafCount(t->nextsibling); else
return LeafCount(t->firstchild) + LeafCount(t->nextsibling); }
错误！未找到引用源。
分析：度最大的结点的度数。 int Degree ( CSTree t ) {
if ( t==NULL ) return 0; else
return max( Degree(t->firstchild), 1+Degree(t->nextsibling)); }
错误！未找到引用源。 int Depth ( CSTree t ) {
if ( t==NULL ) return 0; else {
depchild = Depth(t->firstchild); // 孩子的深度 depsibling = Depth(t->nextsibling); // 兄弟的深度 return max(depchild+1, depsibling); // 取较大者 } }
错误！未找到引用源。
分析：划分先序序列a=(D,(L),(R))和后序序列b=((L),D,(R))，然后对子序列(L)和(R)递归。 // 根据先序序列a[si..ti]和中序序列b[sj..tj]构造二叉树
BinTree CreateBinaryTree ( T a[], int si, int ti, T b[], int sj, int tj ) {
if ( n<=0 ) return 0; // 空树 // 建立根结点
p = new BinNode(a[si]); // 以a[si]为数据域建立新结点 // 根据根结点划分中序序列为b[sj..k-1]和b[k+1..tj] k = sj;
while ( b[k]!=a[si] ) k++; // 在b[]中搜索根结点a[si] // 建立左右子树
p->lchild = CreateBinaryTree ( a, si+1, si+k-sj, b, sj, k-1 ); // 建立左子树 p->rchild = CreateBinaryTree ( a, si+k-sj+1, b, k+1, tj); // 建立右子树 return p; }
错误！未找到引用源。
分析：根据先根和后根序列可以唯一确定一棵树。先根序列中的第一个是树的根，后根序列中最后一个是根，然后根据先根序列和后根序列，将其余序列划分成若干不相交的子序列，就是根的子树，对每一个子树，重复前面的步骤，最终就可以得到整个树。
先根GFKDAIEBCHJ ?根为G，第一棵子树的根为F，又后根DIAEKFCJHBG，所以第一棵子树为(DIAEKF)，同样第二棵子树为(CJHB)，依此类推，可得该树。
G F K D A I E C B H J 错误！未找到引用源。 分析：根据森林和二叉树的对应关系，可知森林的先序序列和中序序列。划分出每一棵树，正好得到每棵树的先序和后序序列，最终得到整个森林。
A B C E D F G I J H K L 错误！未找到引用源。 分析：由于每个字符出现的频率不同，使用固定长度的编码往往比哈夫曼编码使得整个通信量增多。这里先建立哈夫曼树，得出哈夫曼编码，然后计算通信所需的字节数。每字节含8位。
使用固定长度的编码所需字节数为(20+6+34+11+9+7+8+5)*3/8=37.5字节。一种可能的哈夫曼编码是：A:00, B:1100, C:10, D:010, E:011, F:1110, G:1111, H:1101，通信的总字节数是[(20+34)*2+(11+9)*3+(6+5+7+8)*4]/8=34字节。
错误！未找到引用源。
分析：哈夫曼树总是取两个最小的子树合并成一棵二叉树，共需n-1步完成算法，共增加n-1个结点，故总结点个数为n+(n-1)=2n-1。
错误！未找到引用源。
分析：如果n条弧恰好使n个顶点构成环的话，这是构成强连通图所需弧最少的情况。类似无向图的情况，n-1个顶点最多有(n-1)(n-2)条弧，再增加n-1条指向另外一点顶点的弧(或者相反方向的弧)，此时该图恰好不能构成强连通图，若再增加一条弧则必定强连通。 因此，n个顶点的有向图最少需要n条弧就可以构成强连通图；当弧的数目超过(n-1)(n-2)+(n-1) =
2
(n-1)时，必定构成强连通图。
错误！未找到引用源。 A E D B C (a) A B C E D (b)
