056312409数据结构(C语言版)(夏燕张兴科)--习题答案--第7章.doc

7.8 习题与上机操作1选择题：BBBCCC2填空题： 3 4 6 1 2 A F G 5 n2+1 完全 log2n +1 最大高度 n 2K-1 2K-1 2K-1 129 99 2n n-1 n+1 n+1 55 2m-13. 程序填空题: bt p p=p-lchild p=s.elem-s.top p=p-rchild top-addr=bt top!=null top-addr t&(t-lchild|t-rchild)t-lchild t-rchild4应用题： 答案 答案： 答案：先序序列和中序序列相同的二叉树为空树或任一结点均无左孩子的非空二叉树中序和后序序列相同的二叉树为空树或任一结点均无右孩子的非空二叉树先序和后序序列相同的二叉树为空树或仅有一个结点 答案： (A)(B)(C) 答案： 答案：的00于010为0110得01110在01111是10有1100地1101和1110个11115编程题： 设计一个算法，判定给定二叉树是否为二叉排序树。编程思想:用先序算法建立一棵二叉树，设置好二叉树初始标志为flag为1，在中序遍历二叉树时若后一个节点值大于前一个，则用max记录下这个大值，若后一个结点值小于前一个结点值（由max记录），则不为二叉排序树，设置flag为0，当树遍历结束后若flag值为1，则二叉树为二叉排序树。在此程序中，用0表示树为空树。C源程序：#define NULL 0int flag=1,max,k=0;typedef struct BitNodeint data;struct BitNode *lchild, *rchild;BitNode,*BinTree;void sortBitree(BinTree T) /*判断二叉树是否排序树，若否flag设为0*/if(T) sortBitree(T-lchild); k+; if(k=1) max=T-data; else if(T-datamax) max=T-data; else flag=0; sortBitree(T-rchild); void CreateBinTree(BinTree *root)int x; scanf(%d,&x); if (x=0) *root=NULL; else *root=(BinTree)malloc(sizeof(BitNode); (*root)-data=x; CreateBinTree(&(*root)-lchild); CreateBinTree(&(*root)-rchild); main() BinTree BT;CreateBinTree(&BT);sortBitree(BT);if(flag=1)printf(It is a sorted tree);if(flag=0)printf(It is not a sorted tree);试写出对一棵二叉树中所有结点的左右子树相互交换的算法。编程思想：为验证二叉树通过算法是否成功交换，本程序用CreateBinTree()建立了一棵二叉树，调用exchange()方法进行左右子树的交换，PreOrder()方法输出树的结点值，用以验证二叉树左右子树是否成功交换。exchange()方法主要思路是判当前树是否空树，若非空，再判断该树的左右子树是否同时为空，只要不同时为空，则交换左右子树。C源程序：#define NULL 0typedef struct BitNodeint data;struct BitNode *lchild, *rchild;BitNode,*BinTree;void PreOrder(BinTree r)if (r) PreOrder(r-lchild); printf( %d,r-data); PreOrder(r-rchild); void exchange(BinTree T) /* 交换左右子树*/BinTree p;if(T)if(T-lchild|T-rchild) p=T-lchild; T-lchild=T-rchild; T-rchild=p; exchange(T-lchild);exchange(T-rchild);void CreateBinTree(BinTree *root) /* 建立子树*/int x; scanf(%d,&x); if (x=0) *root=NULL; else *root=(BinTree)malloc(sizeof(BitNode); (*root)-data=x; CreateBinTree(&(*root)-lchild); CreateBinTree(&(*root)-rchild); main()BinTree BT;CreateBinTree(&BT);exchange(BT);PreOrder(BT);设计一个算法，要求该算法把二叉树的叶子结点按从左到右的顺序连成一个单链表，表头指针为head。二叉树按二叉链表方式存储，链接时用叶子结点的右指针域来存放单链表指针。编程思想：为验证二叉树叶子结点是否连成一个单链表，本程序用CreateBinTree()建立了一棵二叉树，调用leaf_link ()方法进行叶子结点的连接，printLeaf()方法输出由单链表连接的叶子结点的值，用以验证二叉树左右子树是否成功交换。leaf_link()的主要思路是判定树是否为空，若非空，则判断结点的左右子树是否同时为空，若同时为空，则该结点为叶结点，并单链表的链接方法把该结点加入到叶结点生成的单链表中。C源程序：#define NULL 0typedef struct BitNodeint data;struct BitNode *lchild, *rchild;BitNode,*BinTree;BinTree head,tail;void leaf_link(BinTree T) /*叶子结点生成单链表* /if(T)leaf_link(T-lchild);if(!T-lchild&!T-rchild) if(head=NULL)head=T;tail=T;elsetail-rchild=T;tail=T;leaf_link(T-rchild);void printLeaf( BinTree head) /*打印叶子结点*/while(head) printf( %d,head-data); head=head-rchild;void CreateBinTree(BinTree *root)int x; scanf(%d,&x); if (x=0) *root=NULL; else *root=(BinTree)malloc(sizeof(BitNode); (*root)-data=x; CreateBinTree(&(*root)-lchild); CreateBinTree(&(*root)-rchild); main()BinTree BT;CreateBinTree(&BT);leaf_link(BT);printLeaf(head);已知一棵以线索链表为存储结构的中序线索二叉树T，设计一个算法，试在该二叉树上求任意结点x的中序后继。编程思想：对于结点x,若要找其后继结点，当x-Rtag=1时，x-RChild即为x的后继结点;当x-Rtag=0时，说明x有右子树，此时x的中序后继结点即为其右子树的最左下端的结点。C源程序：#include stdio.h#define NULL 0typedef char Elemtype;typedef struct thread Elemtype data; struct thread *LChild; struct thread *RChild; short int Ltag; short int Rtag; ThreadNode,*ThreadTree; ThreadTree pre;ThreadTree insucc(ThreadTree p)/* 找出p的后继结点*/if(p-Rtag=1)return p-RChild;else p=p-RChild;while(p-Ltag=0) p=p-LChild;return p;void CreateBinTree(ThreadTree *root) /* 建立树*/char x; x=getchar(); if (x=#) *root=NULL; else *root=(ThreadTree)malloc(sizeof(ThreadNode); (*root)-data=x; CreateBinTree(&(*root)-LChild); CreateBinTree(&(*root)-RChild); void InThread(ThreadTree root) if (root!=NULL) InThread(root-LChild); if (root-LChild=NULL) root-Ltag=1; root-LChild=pre; if (pre!=NULL & pre-RChild=NULL) /* 置后继线索 */ pre-RChild=root; pre-Rtag=1; pre=root; InThread(root-RChild); /* 线索化右子树 */ main()ThreadTree T,q;CreateBinTree(&T);InThread(T);q=insucc(T);printf(%c ,q-data); 操作题已知一棵二叉树按顺序方式存储在数组A1.n中。设计算法，求出下标分别为i和j的两个结点的最近的公共祖先结点的值。编程思想：二叉树顺序存储，是按完全二叉树的格式存储，利用完全二叉树双亲结点与孩子结点编号间的关系，求下标为i和j的两结点的双亲，双亲的双亲等，直至找到最近的公共祖先。C源程序：typedef int ElemType; void Ancestor(ElemType A,int i ,int j)while(i!=j) if(ij) i=i/2; else j=j/2;printf(所查结点的最近公共祖先的下标是%d,值是%d,i,Ai);main() /* 从下标为1的单元存放树结点*/int A14=0,1,2,3,4,5,6,7,8,9,10,11,12,13,14; int i,j; scanf(%d%d,&i,&j);Ancestor(A,i,j);假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法(注：已知树中结点数)编程思想：由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树的深度。对每一结点，找其双亲，双亲的双亲，直至结点双亲为0为止。C源程序：#define MAX_SIZE 100typedef int ElemType;typedef struct PTNode ElemType data; int parent;PTNode;typedef struct PTNode nodesMAX_SIZE; int n;PTree;int Depth(PTree t) /*求树高*/int maxdepth=0; int