更多"【说明】
本程序利用非递归算法实现二叉树后序遍历。
【函数】
"的相关试题:
[简答题]【说明】
本程序利用非递归算法实现二叉树后序遍历。
【函数】
#include＜stdio.h＞
#include＜stdlib.h＞
typedef struct node/*二叉树的结点数据结构类型*/
char data;
struct node *left;
struct node *right;
BTREE;
void SortTreelnsert(BTREE **tree, BTREE *s)
if(*tree==NULL)*tree=s;
else
if(s-＞data＜(*tree)-＞data)
SortTreelnsert( (1) ,s);
else if(s-＞data＞=(*tree)-＞data)
SortTreelnsert( (2) ,s);
void TraversalTree(BTREE *tree)
BTREE *stack[1 000],*p;
int tag[1000],top=0;
p=tree;
do
while(p !=NULL)
stack[++top]=p;
(3) ;
tag[top]=0; /*标记栈顶结点的左子树已进行过后序遍历*/
while(top＞0&& (4) )/*栈顶结点的右子树是否被后序遍历过*/
p=stack[top--];
putchar(p-＞data);
if(top＞0)/*对栈顶结点的右子树进行后序遍历*/
(5) ;
tag[top]=1;
while(
[单项选择]实现任意二叉树的后序遍历的非递归算法用栈结构，最佳方案是二叉树采用（）存储结构。
A. 二叉链表
B. 顺序存储结构
C. 三又链表
D. 广义表存储结构
[单项选择]将一个递归算法改为对应的非递归算法时，通常需要使用 (44) 。
A. 优先队列
B. 队列
C. 循环队列
D. 栈
[单项选择]将一个递归算法改为对应的非递归算法时，通常需要使用______。
A. 栈
B. 队列
C. 循环队列
D. 优先队列
[简答题]试编写一个非递归算法．实现求以二叉链表存储的二叉树中q结点的祖先。
[简答题]已知深度为h的二叉树采用顺序存储结构已存放于数组BT[1:2h一1]中，请写一非递归算法，产生该二叉树的二叉链表结构。设二叉链表中链结点的构造为(lchild，data，rchild)，根结点所在链结点的指针由T给出。
[填空题][说明] 假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。
Void postorder (btree * B)
btree * stack [m0] , *p;
int tag [m0], top =0;
p=b;
do
while (p! =NULL)
top+ +;
(1)
tag [top] =0;
p =p- ＞left;
if (top ＞0)
(2)
if (tag[top3 = =1)
(3)
print ("%d", p- ＞data);
if(top＞0)
(4)
tag [top] = 1;
while (p! = NULL && top ! =0)
[填空题][说明] 假设二叉树采用链式存储方式存储，编写一个后序遍历二叉树的非递归方式。
Void postorder (btree * B)
{
btree * stack [m0] , *p;
int tag [m0], top =0;
p=b;
do
{
while (p! =NULL)
{
top+ +;
(1)
tag [top] =0;
p =p- ＞left;
}
if (top ＞0)
{
(2)
if (tag[top3 = =1)
{
(3)
print ("%d", p- ＞data);
}
if(top＞0)
{
(4)
tag [top] = 1;
}
}
} while (p! = NULL && top ! =0)
}
[简答题][说明]
下面的程序利用递归算法计算x和y的最大公约数。
[函数2.1]
main ( )
{ int x,y,k,t;
scanf(" % d% d" , &x, &y);
if(x＞y) { t=x;x=y; y=t;}
(1) ;
while(k! =0){
y=x;
(2) ;
k=y%x;
}
prinff( "% d" ,x); }
[函数2.2说明]
函数fun(char *str,char *substr的功能是计算子串sugbstr在串str中出现的次数。
[函数2.2]
fun(ehar * str, char * substr)
{ int x,y,z;
(3) ;
for(x=0;str[ x] ! = ’/O’;x + + )
for(y=x,z=0;sabstr[z] = =str[y]; (4) ,y+ +)
if( (5) = =’/0’) {
num + +;
break;
}
return(num);
}
[简答题]【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
{ int i=s,j=t+1,temp;
int x=A[s];
do{
do i ++ ;while (1) ;
do j -- ;while(A[j]＞x);
if(i＜j){temp=A[i]; (2) ; (3) ;}
}while(i＜j);
A[a] =A[j];A[j] =x;
if(s＜i-1) (4) ;
if(j+1＜t) (5) ;
}
[简答题]【说明】
函数QuickSort是在一维数组A[n]上进行快速排序的递归算法。
【函数】
void QuickSort( int A[ ],int s,int t)
int i=s,j=t+1,temp;
int x=A[s];
do
do i ++ ;while (1) ;
do j -- ;while(A[j]＞x);
if(i＜j)temp=A[i]; (2) ; (3) ;
while(i＜j);
A[a] =A[j];A[j] =x;
if(s＜i-1) (4) ;
if(j+1＜t) (5) ;
[简答题]二叉链表为存储结构，写出二叉树宽度的算法。所谓宽度，是指二叉树的各层上，具有结点数最多的那一层上的结点总数。
[填空题]下列程序的运行结果为 【7】 。
#include＜math．h＞
#include＜stdio．h＞
main（ ）
int s=1；
float n=1，pi=0；
double t=1；
while(fabs(t)＞=2e-6)
pi+=t；
n+=2；
s=-s；
t=s/n；
pi*=4；
printf("pi=%．6f/n"，pi)；
[简答题]下面是快速排序的递归算法。试在算法后的空白中填上正确的内容，将该算法补充完整使其完成预定功能。#define M 500typedef struct{int key；char info；}NODENODE r[M]；quiksort(NODE r[]，int low，int hig) { int i, j； NODE x； if(low>=hig) return； i=low; j=hig;x=r[i]; do { while((r[j].key>=x.key)＆＆(j>i)) (1) ; if(ii)) (2) ； if(i (3) ； }(1)_____________(2)_____________(3)_____________
[单项选择]
计算N!的递归算法如下，求解该算法的时间复杂度时，只考虑相乘操作，则算法的计算时间T(n)的递推关系式为 (55) ；对应时间复杂度为 (56) 。
int Factorial (int n)
//计算n!
if(n＜=1)return 1;
else return n * Factorial(n-1);
（55）处填（）。
A. T(n)=T(n-1)+1
B. T(n)=T(n-1)
C. T(n)=2T(n-1)+1
D. T(n)=2T(n-1)-1
