数据结构习题课第8、7、6章(网上的答案有些有问题的)

注：1023为深度是10的满二叉树，有512个叶子结点，1001比1023少22个节点。所以有512-22+22/2=501片叶子

（4）一棵完全二叉树有999 个结点，它的深度为（ B ）。 A．9 B．10 C．11 D．12

（5）一棵具有5 层的满二叉树所包含的结点个数为（ B ）。 A．15 B．31 C．63 D．32

7.2 用一维数组存放完全二叉树：ABCDEFGHI，则后序遍历该二叉树的结点序列为（ HIDEBFGCA ）。

7.10 已知一棵二叉树的中序遍历的结果为ABCEFGHD ， 后序遍历的结果为 ABFHGEDC，试画出此二叉树。 解：

7.11 已知一棵二叉树的前序遍历的结果为ABCDEF，中序遍历的结果为CBAEDF，试画出此二叉树 解：

7.14 试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。 解：

#include \ void change(bintree t) { bintree p; if (t) {

p=t->lchild;

t->lchild=t->rchild; t->rchild=p; change(t->lchild); change(t->rchild); } } int main() { bintree t;

creat(&t); /*建立二叉树t 的存储结构*/ preorder(t); change(t); printf(\ preorder(t); }

7.18 假设二叉树采用链式方式存储，root 为其根结点，p 指向二叉树中的任意一个结点，编写一个求从根结点到p 所指结点之间路径长度的函数。 解：在后序遍历非递归算法中，当访问的结点为p 时，其祖先点正好全部在栈中，此时栈中结点的个数就是根结点到p 所指结点之间路径长度。 #include #include typedef char datatype;

typedef struct node /*二叉树结点定义*/

{ datatype data;

struct node *lchild,*rchild; }bintnode;

typedef bintnode *bintree;

typedef struct stack {

bintree data[100]; int tag[100]; int top; }seqstack;

void creat(bintree *t) ;

/*函数Depth，功能：求根结点到x 的路径长度*/ int Depth(bintree t,datatype x) {

seqstack s; int i=0,j; s.top=0;

while(t || s.top!=0) {

while(t)

{

s.data[s.top]=t;

s.tag[s.top]=0; s.top++; t=t->lchild; }

while(s.top>0 && s.tag[s.top-1]) {

s.top--; t=s.data[s.top];

if(t->data==x) return s.top; //此时栈中的结点都是x 的祖先结点

} if(s.top>0) {

t=s.data[s.top-1]; s.tag[s.top-1]=1; t=t->rchild; }

else t=NULL; } } 第6章 树

6.1 树最适合用来表示具有（ 有序 ）性和（ 层次 ）性的数据。

6.2 在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（ 数据间关