第6章+树和二叉树(习题)(3)

2008信息与计算科学专业数据结构习题

例如，对于如右图所示的二叉树，其广义表表示为A（B（D，E（G）），C（，F））。 此算法的基本思路是：依次从保存广义表的字符串ls中输入每个字符。若遇到的是字母（假设以字母作为结点的值），则表示是结点的值，应为它建立一个新的结点，并把该结点作为左子女（当k=1）或右子女（当k=2）链接到其双亲结点上。若遇到的是左括号―（‖，则表明子表的开始，将k置为1；若遇到的是右括号―）‖，则表明子表结束。若遇到的是逗号―，‖，则表示以左子女为根的子树处理完毕，接着处理以右子女为根的子树，将K置为2。在算法中使用了一个栈s，在进入子表之前，将根结点指针进栈，以便括号内的子女链接之用。在子表处理结束时退栈。相关的栈操作如下：

MakeEmpty(s) 置空栈 Push(s,p) 元素p入栈 Pop(s) 退栈 Top(s) 存取栈顶元素的函数 下面给出了建立二叉树的算法，其中有5个语句缺失，请阅读此算法并把缺失的语句补上。

void CreatBinTree(BinTreeNode *&BT,char ls){

Stacks; MakeEmpty(s); BT=NULL; //置空二叉树 BinTreeNode *p;

int k; istream ins(ls)； //把串ls定义为输入字符串流对象ins ; char ch; ins>>ch; //从ins顺序读入一个字符 while (ch != ?#‘){ //逐个字符处理，直到遇到?#‘为止 switch(ch){

case ?(‘: __(1) _；k=1; break; case ?)‘: pop(s); break; case‘,‘ : _(2)__； break;

default :p=new BinTreeNode; _(3)_;p->leftChild=NULL;p->rightChild=NULL; if(BT==NULL) __(4) _；else if (k==1) top(s)->leftChild=p; else top(s)->rightChild=p;

}

__(5)__; } }

39．下列是先序遍历二叉树的非递归子程序，请阅读子程序填充空格，使其成为完整的算法。

void example(b) btree *b;

66

2008信息与计算科学专业数据结构习题

{ btree *stack[20], *p； int top; if (b!=null)

{ top=1; stack[top]=b; while (top>0) { p=stack[top]; top--; printf(―%d‖,p->data); if (p->rchild!=null) {__(1)_; (2)___; }

if (p->lchild!=null) __(3)_; _(4)_; }}}}

40．以下程序是二叉链表树中序遍历的非递归算法，请填空使之完善。二叉树链表的结点类型的定义如下：

typedef struct node /*C语言/

{char data; struct node *lchild,*rchild;}*bitree;

void vst(bitree bt) /*bt为根结点的指针*/ { bitree p; p=bt; initstack(s); /*初始化栈s为空栈*/

while(p || !empty(s)) /*栈s不为空*/ if(p) { push (s,p); __(1)_; } /*P入栈*/

else { p=pop(s); printf(―%c‖,p->data); __(2)__; } /*栈顶元素出栈*/ }

41．二叉树存储结构同上题，以下程序为求二叉树深度的递归算法，请填空完善之。 int depth(bitree bt) /*bt为根结点的指针*/ {int hl,hr;

if (bt==NULL) return(__(1) _); hl=depth(bt->lchild); hr=depth(bt->rchild); if(_(2)__) ___(3)__； return(hr+1);

67

2008信息与计算科学专业数据结构习题

}

42．由二叉树的前序遍历和中序遍历序列能确定唯一的一棵二叉树，下面程序的作用是实现由已知某二叉树的前序遍历和中序遍历序列，生成一棵用二叉链表表示的二叉树并打印出后序遍历序列，请写出程序所缺的语句。

#define MAX 100 typedef struct Node

{char info; struct Node *llink, *rlink; }TNODE; char pred[MAX],inod[MAX]; main(int argc,int **argv)

{ TNODE *root; if(argc<3) exit 0;

strcpy(pred,argv[1]); strcpy(inod,argv[2]); root=restore(pred,inod,strlen(pred)); postorder(root); }

TNODE *restore(char *ppos,char *ipos,int n) { TNODE *ptr； char *rpos; int k; if(n<=0) return NULL; ptr->info=___(1)____; for(____(2)___ ; rposllink=restore(ppos+1, ___(4)____,k ); ptr->rlink=restore (___(5)____+k,rpos+1,n-1-k); return ptr; }

postorder(TNODE*ptr) { if(ptr=NULL) return;

postorder(ptr->llink); postorder(ptr->rlink); printf(―%c‖,ptr->info); }

43．下面是中序线索树的遍历算法，树有头结点且由指针thr指向。树的结点有五个域，

68

2008信息与计算科学专业数据结构习题

分别为数据域 data，左、右孩子域 lchild、rchild和左、右标志域 ltag,rtag。规定，标志域为1是线索，O是指向孩子的指针。 inordethread(thr) {p=thr->lchild; while (___(1)___) { while(__(2)___) p= _(3)__;

printf(p->data);

while(_____(4)____) { p=__(5) _；printf(p->data);} p= _(6) ;}

}

44．线索二叉树有数据域data，左右孩子域lchild和rchild，左右标志ltag及rtag，规定标志为1对应的孩子域是线索，0则为指向孩子的指针。规定在储存线索二叉树时，完成下面中序线索化过程。（存储线索二叉树，不增加头结点，只在原有的由tree指向的二叉树中增加线索，此处也不考虑c语言的具体语法与约定，线索化前所有的标志tag都是0）。

/* pre是同tree类型相同的指针，初值是null */ thread_inorder (tree) { if(tree!=null)

{ thread_inorder(__(1)__); if(tree->lchild==___(2)___) { tree->ltag=1; tree->lchild=pre; } if((3)___ == null){ ___(4)____; __(5)_____;} pre=p; thread-inorder(___(6)____); } }

45．如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法空格处填上正确的语句。设线索二叉树的结点数据结构为(lflag,left,data,right,rflag)，其中： lflag= 0，left 指向其左孩子，lflag= 1，left 指向其前驱；rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。

prior(node,x) { if (node !=null)

if (__(1)___ ) *x=node->right; else *x=node->left;

69

2008信息与计算科学专业数据结构习题

}

next(bt, node, x) /*bt是二叉树的树根*/ {___(2)__; if (node!=bt && node!=null) if (node->rflag) ___(3)____ ；

else {do t=*x; ___(4)___;while (*x==node); *x=t; } }

四、应用题

1．从概念上讲，树，森林和二叉树是三种不同的数据结构，将树，森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。

2．树和二叉树之间有什么样的区别与联系？

3．请分析线性表、树、广义表的主要结构特点，以及相互的差异与关联。 4．将算术表达式（（a+b）+c*(d+e)+f）*(g+h)转化为二叉树。

5. 一棵有n(n>0)个结点的d度树, 若用多重链表表示, 树中每个结点都有d个链域, 则在表示该树的多重链表中有多少个空链域? 为什么?

6. 一棵二叉树中的结点的度或为0或为2，则二叉树的枝数为2(n0-1)，其中n0是度为0的结点的个数。

7．一个深度为L的满K叉树有以下性质：第L层上的结点都是叶子结点，其余各层上每个结点都有K棵非空子树，如果按层次顺序从1开始对全部结点进行编号，求：

1）各层的结点的数目是多少？

2）编号为n的结点的双亲结点（若存在）的编号是多少？ 3）编号为n的结点的第i 个孩子结点（若存在）的编号是多少？

4）编号为n的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？ 请给出计算和推导过程。

8．证明任一结点个数为n 的二叉树的高度至少为O(logn). 9．有n个结点并且其高度为n的二叉树的数目是多少?

10．已知完全二叉树的第七层有10个叶子结点，则整个二叉树的结点数最多是多少？ 11．高度为10的二叉树，其结点最多可能为多少？

12．任意一个有n个结点的二叉树，已知它有m个叶子结点，试证明非叶子结点有（m-1）

70

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库第6章+树和二叉树(习题)(3)在线全文阅读。