精品646③ 编写复制一棵二叉树的非递回算法

精品646③ 编写复制一棵二叉树的非递回算法 6.46? 编写复制一棵二叉树的非递归算法。 要求实现下列函数: void CopyBiTree(BiTree T, BiTree &TT); /* 基于层次遍历的非递归复制二叉链 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf */ 二叉链表类型定义: typedef char TElemType; // 设二叉树的元素为char类型 typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree; 可用队列类型Queue的相关定义: typedef BiTree QElemType; // 设队列元素为二叉树的指针类型 Status InitQueue(Queue &Q); Status EnQueue(Queue &Q, QElemType e); Status DeQueue(Queue &Q, QElemType &e); Status GetHead(Queue Q, QElemType &e); Status QueueEmpty(Queue Q); void CopyBiTree(BiTree T, BiTree &TT) /* 基于层次遍历的非递归复制二叉链表 */ { QElemType p;Queue t2,tt2; InitQueue(t2); InitQueue(tt2); if(!T)TT=NULL; else { EnQueue(t2,T); if(!(TT=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); p=TT; p->data=T->data; p->lchild=p->rchild=NULL; EnQueue(tt2,p); while(!QueueEmpty(t2)) { DeQueue(t2,T); DeQueue(tt2,p); if(T->lchild) { EnQueue(t2,T->lchild); if(!(p->lchild=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); p->lchild->data=T->lchild->data; p->lchild->lchild=p->lchild->rchild=NULL; EnQueue(tt2,p->lchild); } if(T->rchild) { EnQueue(t2,T->rchild); if(!(p->rchild=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); p->rchild->data=T->rchild->data; p->rchild->lchild=p->rchild->rchild=NULL; EnQueue(tt2,p->rchild); } } } } 6.65? 已知一棵二叉树的前序序列和中序序列分别 存于两个一维数组中，试编写算法建立该二叉树的二 叉链表。 要求实现以下函数: void BuildBiTree(BiTree &bt, int ps, char *pre, int is, char *ino, int n); /* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ 二叉链表类型定义: typedef char TElemType; typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree; void BuildBiTree(BiTree &bt, int ps, char *pre, int is, char *ino, int n) /* 当前要建立的子树bt的元素总数为n，*/ /* 元素在前序序列pre的起始位置为ps，*/ /* 元素在中序序列ino的起始位置为is */ { if(n==0)bt=NULL; else{ int i=is; bt=(BiTNode*)malloc(sizeof(BiTNode)); bt->data=pre[ps]; while(ino[i]!=pre[ps])i++; BuildBiTree(bt->lchild,ps+1,pre,is,ino,i-is); BuildBiTree(bt->rchild,ps+i-is+1,pre,is+i-is+1,ino,n-(i-is)-1); } } 6.70? 如果用大写字母标识二叉树结点，则一棵 二叉树可以用广义表形式的字符序列表示。试写一 个递归算法，由这种形式的字符序列，建立相应的 二叉树的二叉链表存储结构。 要求实现以下函数: void BuildBiTree(BiTree &bt, char *s, int &i); /* 单遍扫描广义表形式的字符序列s， */ /* 建立相应的二叉树bt。 */ /* i为扫描s时当前字符的序号，初值为0 */ 二叉链表类型定义: typedef char TElemType; typedef struct BiTNode { TElemType data; BiTNode *lchild, *rchild; } BiTNode, *BiTree; void BuildBiTree(BiTree &bt, char *s, int &i) /* 单遍扫描广义表形式的字符序列s， */ /* 建立相应的二叉树bt。 */ /* i为扫描s时当前字符的序号，初值为0 */ { bt=(BiTree)malloc(sizeof(BiTNode)); if(!bt)exit(OVERFLOW); if(!s[i])bt=NULL; else { bt->data=s[i];i++; if(s[i]=='(') { i++; BuildBiTree(bt->lchild,s,i); i++; while(s[i]==','||s[i]==')')i++; BuildBiTree(bt->rchild,s,i); } } } 9.31? 试写一个判别给定二叉树是否为二叉排序树 的算法，设此二叉树以二叉链表作存储结构。且树中 结点的关键字均不同。 实现下列函数: Status IsBSTree(BiTree t); /* 判别给定二叉树t是否为二叉排序树。*/ /* 若是，则返回TRUE，否则FALSE */ 二叉树的类型BiTree定义如下: typedef struct { KeyType key; ... ... // 其他数据域 } ElemType; typedef struct BiTNode { ElemType data; BiTNode *lchild,*rchild; }BiTNode, *BiTree; Status IsBSTree(BiTree t) /* 判别给定二叉树t是否为二叉排序树。*/ /* 若是，则返回TRUE，否则FALSE */ { if(!t||!t->lchild&&!t->rchild) return TRUE; if(!t->lchild&&t->rchild->data.key>t->data.key) t=t->rchild; if(t->lchild->data.keydata.key&&t->rchild->data.key>t->data.key) return TRUE; else return FALSE; } 9.40? 在平衡二叉排序树的每个结点中增设一个 lsize域，其值为它的左子树中的结点数加1。试写 一时间复杂度为O(logn)的算法，确定树中第k小的 结点的位置。 实现下列函数: BiTNode *Ranking(BiTree T, int k) /* 在含lsize域的平衡二叉排序树T中确定第k小的结点指针 */ 二叉树的类型BiTree定义如下: typedef struct { KeyType key; ... ... // 其他数据域 } ElemType; typedef struct BiTNode { ElemType data; BiTNode *lchild,*rchild; int lsize; }BiTNode, *BiTree; BiTNode *Ranking(BiTree T, int k) /* 在含lsize域的平衡二叉排序树T中确定第k小的结点指针 */ { if(!T) return NULL; if(T->lsize==k) return T; else if(T->lsize>k) return Ranking(T->lchild,k); else return Ranking(T->rchild,k-T->lsize);