n0=n2+2n3+??+(m-1)nm+1 6.4
(1) ki-1 (i为层数) (2) (n-2)/k+1 (3) (n-1)*k+i+1
(4) (n-1)%k !=0; 其右兄弟的编号 n+1 6.5（1）顺序存储结构
1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B C D # E F # G # # # # H
注：#为空结点 6.6
(1) 前序 ABDGCEFH (2) 中序 DGBAECHF (3) 后序 GDBEHFCA 6.7
(1) 空二叉树或任何结点均无左子树的非空二叉树 (2) 空二叉树或任何结点均无右子树的非空二叉树 (3) 空二叉树或只有根结点的二叉树 6.8
int height(bitree bt)
// bt是以二叉链表为存储结构的二叉树，本算法求二叉树bt的高度 { int bl,br; // 局部变量，分别表示二叉树左、右子树的高度 if (bt==null) return(0); else { bl=height(bt->lchild);
br=height(bt->rchild);
return(bl>br? bl+1: br+1); // 左右子树高度的大者加1（根） }
}// 算法结束
6.9
void preorder(cbt[],int n,int i);
// cbt是以完全二叉树形式存储的n个结点的二叉树，i是数
A B ^ C ^ D ^ E ^ F ^ ^ G ^ ^ H ^
// 组下标，初始调用时为1。本算法以非递归形式前序遍历该二叉树 { int i=1,s[],top=0; // s是栈，栈中元素是二叉树结点在cbt中的序号 // top是栈顶指针，栈空时top=0 if (n<=0) { printf(“输入错误”);exit（0）；} while (i<=n ||top>0)
{ while(i<=n)
{visit(cbt[i]); // 访问根结点
if (2*i+1<=n) s[++top]=2*i+1; //若右子树非空，其编号进栈 i=2*i;// 先序访问左子树 }
if (top>0) i=s[top--]; // 退栈，先序访问右子树 } // END OF while (i<=n ||top>0) }// 算法结束
//以下是非完全二叉树顺序存储时的递归遍历算法，“虚结点”用‘*’表示 void preorder(bt[],int n,int i);
// bt是以完全二叉树形式存储的一维数组，n是数组元素个数。i是数 // 组下标，初始调用时为1。 { if (i<=n && bt[i]!=’*’) { visit(bt[i]);
preorder(bt,n,2*i); preorder(bt,n,2*i+1); }// 算法结束
6.10
int equal(bitree T1,bitree T2);
// T1和T2是两棵二叉树，本算法判断T1和T2是否等价 // T1和T2都是空二叉树则等价
// T1和T2只有一棵为空，另一棵非空，则不等价
// T1和T2均非空，且根结点值相等，则比较其左、右子树
{if (T1==null && T2==null) return(1); // 同为空二叉树
else if (T1==null || T2==null) return(0); // 只有一棵为空
else if (T1->data!=T2->data) return(0);// 根结点值不等 else return(equal(T1->lchild,T2->lchild)&&equal(T1->rchild,T2->rchild)) //判左右子树等价 }// 算法结束
6．11
void levelorder (bitree ht); {本算法按层次遍历二叉树ht} {if (ht!=null)
{initqueue(q); {处始化队列，队列元素为二叉树结点的指针} enqueue(q,ht); {根结点指针入队列}
while (!empty(q))
{ p=delqueue(q);
visit(p); // 访问结点
if (p->lchild!=null) enqueue (q,p->lchild); //若左子女非空，则左子女入队列
if (p->rchild!=null) enqueue (q,p->rchild)； //若右子女非空，则右子女入队列 }
}
} // 算法结束 6．12
void preorder (bitree *t); (前序非递归遍历)
{ bitree *s[n+1]; // s是指针数组，数组中元素为二叉树节点的指针 top=0;
while (t!=null || top!=0)
{ while (t!=null) { visit(*t); s[++top]=t; t=t->lchild } if (top!=0) { t=s[top--]; t=t->rchild;} }
} // 算法结束
void inorder (bitree *t); (中序非递归遍历) {bitree *s[n+1];
top=0;
while ((t!=null || top!=0)
{ while (t!=null) { s[++top]=t; t=t->lchild }
if (top!=0) { t=s[top--]; visit(*t); t=t->rchild; } } // 算法结束
void postorder (bitree *t); (后序非递归遍历) {typedef struct node
{ bitree *t; tag:0..1 } stack; stack s[n+1] ; top=0;
while (t || top)
{ while (t) { s[++top].t=t; s[top].tag=0; t=t->lchild; } while (top && s[top].tag==1) { printf(s[top--].t->data:3);} if (top) { s[top].tag=1; t=s[top].t->rchild ;} }
} // 算法结束
6.13
bitree *dissect(bitree **t,ElemType x)
// 二叉树t至多有一个结点的数据域为x，本算法拆去以x为根的子树 // 拆开后的第一棵树用t表示，成功拆开后返回第二棵二叉树
{bitree *p,*find;
if (*t!=null)
{ if ((*t)->data==x) // 根结点数据域为x {p=*t; *t=null; return(p);
}
else {find=(dissect(&(*t)->lchild),x); // 在左子树中查找并拆开 // 若在左子树中未找到，就到右子树中查找并拆开 if (!find) find=(dissect(&(*t)->rchild),x); return(find); } }
else return(null); // 空二叉树 } // 算法结束
6.14
int search(bitree t,ElemType x)
// 设二叉树t中，值为x的结点至多一个，本算法打印x的所有祖先 // 算法思想是，借助后序非递归遍历，用栈装遍历过程的结点，当查到 // 值为x的结点时，栈中元素都是x的祖先 { typedef struct { bitree p; int tag; }snode; snode s[]; int top=0;
while (t && t->data !=x || top)
{ while (t && t->data !=x) // 沿左分支向下
{ s[++top].p=t; s[top].tag=0; t=t->lchild; } if (t->data==x) //
{for (i=1;i<=top;++i) printf(“%c\\n”,s[i].p->data);// 输出，设元素为字符
return(1); } else
while (top>0 && s[top].tag==1) top--;//退出右子树已访问的结点
if (top>0) // 置访问标志1，访问右子树 {s[top].tag=1;t=s[top].p; t=t->rchild; } }
return(0); // 没有值为x的结点 } // 算法结束
6.15 中序序列BDCEAFHG
后序序列DECBHGFA
A B F
前序序列 ABCDEFGH 6.16 后序线索树：
E null
只有空指针处才能加线索。 线索链表：
6.17
bitree *search(bitree *p)
// 查找前序线索二叉树上给定结点p的前序后继
^ 1 G 1 1 H 1 1 0 0 1 E 1 0 F 1 0 B 1 0 A 0 H B C A D E H C G D E F 0 C 0