以下程序是先序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。
以下程序是先序遍历二叉树的递归算法的程序,完成程序中空格部分(树结构中左、右指针域分别为left和right,数据域data为字符型,BT指向根结点)。
参考解析
略
相关考题:
阅读下列程序说明和C程序,把应填入其中(n)处的字句,写在对应栏内。【程序说明】已知某二叉树的前序遍历和中序遍历序列,可以得到该二叉树的结构。本程序实现了根据这两个遍历序列生成一棵链接表示的二叉树。构造二叉树的算法要点是:由前序遍历序列,该序列的第一个元素是根结点元素。该元素将中序遍历序列分成左、右两部分,那些位于该元素之前的元素是它的左子树上的元素,位于该元素之后的元素是它的右子树上的元素。对于左、右子树,由它们的前序遍历序列的第一个元素可确定左、右子树的根结点,参照中序遍历序列又可进一步确定子树的左、右子树元素。如此递归地参照两个遍历序列,最终构造出二叉树。两个遍历序列作为主函数main()的参数。为简单起见,程序假定两个遍历序列是相容的。主函数调用函数restore()建立二叉树。函数restore()以树(子树)的前序遍历和中序遍历两序列及序列长为参数,采用递归方法建立树(子树)。函数postorder()实现二叉树的后序遍历序列输出,用来验证函数restore()建立的二叉树。【程序】include(stdio.h>include<stdlib.h>define MAX 100typedef struct node{char data;struet node * llink,*rlink;}TNODE;charpred[MAX],inod[MAX];TNODE * restore (Char*,char*,int);main(int argc,Char* *argv){TNODE * root;if(argc<3)exit(0);strcpy(pred,argv[1]);strcpy(inod,argv[2]);root=restore(pred,inod,strlen(pred))postorder(root);printf("\n\n");}TNODE * restore(Char * ppos,char * ipos,int n){ /*参数包括前序遍历序列数组和中序遍历数组*/TNODE * ptr;Char * rpos;int k;if(n <=0)return NULL;ptr= (TNODE *)malloc(sizeof(TNODE));ptr→data=(1);for (2) rpos=ipos;rpos <ipos+n;rpos++ )if(*rpos== * ppos)break;k =(3);ptr→llink = 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);prinft("%c",ptr→data);}
已知二叉排序树采用二叉链表存储结构,根结点的指针为T,链结点的结构为(lchild,data,rchild),其中lchild,rchild分别指向该结点左、右孩子的指针,data域存放结点的数据信息。请写出递归算法,从小到大输出二叉排序树中所有数据值>=x的结点的数据。要求先找到第一个满足条件的结点后,再依次输出其他满足条件的结点。
阅读下列说明和c函数代码,将应填入 (n) 处的字句写在答题纸的对应栏内。【说明】对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二叉树的每个结点,且每个结点仅访问一次的过程。函数InOrder。()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储,结点类型定义如下:typedef struct BtNode{ElemTypedata; /*结点的数据域,ElemType的具体定义省略*/struct BtNode*ichiid,*rchild; /*结点的左、右弦子指针域*/)BtNode,*BTree;在函数InOrder()中,用栈暂存二叉树中各个结点的指针,并将栈表示为不含头结点的单向链表(简称链栈),其结点类型定义如下:typedef struct StNode{ /*链栈的结点类型*/BTree elem; /*栈中的元素是指向二叉链表结点的指针*/struct StNode*link;}S%Node;假设从栈顶到栈底的元素为en、en-1、…、e1,则不含头结点的链栈示意图如图5—5所示。【C函数】int InOrder(BTree root) /*实现二叉树的非递归中序遍历*/{BTree ptr; /*ptr用于指向二又树中的结点*/StNode*q; /*q暂存链栈中新创建或待删除的结点指针+/StNode*stacktop=NULL; /*初始化空栈的栈顶指针stacktop*/ptr=root; /*ptr指向二叉树的根结点*/while( (1 ) I I stacktop!=NULL){while(ptr!=NULL){q=(StNode*)malloc(sizeof(StNode));if(q==NULL)return-1;q-elem=ptr;(2) ;stacktop=q; /*stacktop指向新的栈顶*/ptr=(3 ) ; /*进入左子树*/}q=stacktop; (4) ; /*栈顶元素出栈*/visit(q); /*visit是访问结点的函数,其具体定义省略*/ptr= (5) ; /*进入右子树*/free(q); /*释放原栈顶元素的结点空间*/}return 0;}/*InOrder*/
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。【说明】本程序利用非递归算法实现二叉树后序遍历。【函数】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;elseif(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(top>0);}void PrintSortTree(BTREE *tree){if(tree !=NULL){printSortTree(tree->left);putchar(tree->data);pdntSortTree(tree->right);}}main(){BTREE *root=NULL, *node;char ch;ch=getchar();while(ch !=''){node=(BTREE*)malloc(sizeof(BTREE));node->data=ch;node->left=node->right=NULL;SortTreelnsert(root, node);ch=getchar();}PrintSortTree(root);putchar('\n');TraversalTree(root);}
下列关于数据结构的叙述中,正确的是______。A.实际应用中,队列的顺序存储结构一般采用循环队列的形式B.递推算法结构程序一般比递归算法结构程序更精练C.树是一种线性结构D.用一维数组存储二叉树,总是以先序遍历的顺序存储各结点
阅读以下说明和C++程序,将应填入(n)处的字句写在对应栏内。【说明】以下程序实现了二叉树的结点删除算法,若树中存在要删除的结点,则删除它,否则返回。 FindNode ()函数能够在二叉树中找到给定值的结点,并返回其地址和父结点。【C++程序】template < class T >void BinSTree < T >: :Delete( const T item){TreeNode < T > * DelNodePtr, * ParNodePtr, * RepNodePtr;if(( DelNodePtr = FindNode (item,ParNodePtr)) = = NULL)(1)if(DelNodePtr→right = = NULL) //被删除结点只有一个子结点的情况RepNodePtr = DelNodePtr→left;else if( DelNodePtr→left = = NULL)(2);else // 被删除结点有两个子结点的情况{TreeNode < T >* PofRNodePtr = DelNodePtr;RepNodePtr = DelNodePtr→left;while(RepNodePtr→right ! = NULL){ //定位左子树的最右结点PofRNodePtr =RepNodePtr;RepNodePtr = RepNodePtr→right;}if(PofRNodePtr = = DelNodePtr) //左子树没有右子结点(3);else //用左子顷的最右结点替换删除的结点{(4)RepNodePtr→left = DelNodePtr→left;RepNodePtr→right = DelNodePtr→right;}}if (5)//要删除结点是要结点的情况root = RepNodePtr;else if ( DelNodePtr→data < ParNodePtr→Data)ParNodePtr→left = RepNodePtr;elseParNodePtr→right =RepNodePtr;FirstTreeNode ( DelNodePtr ) ;//释放内存资源size→;}
一个具有m个结点的二叉树,其二叉链表结点(左、右孩子指针分别用left和right表示)中的空指针总数必定为(57)个。为形成中序(先序、后序)线索二叉树,现对该二叉链表所有结点进行如下操作:若结点p的左孩子指针为空,则将该左指针改为指向p在中序(先序、后序)遍历序列的前驱结点;若p的右孩子指针为空,则将该右指针改为指向p在中序(先序、后序)遍历序列的后继结点。假设指针s指向中序(先序、后序)线索二叉树中的某结点,则(58)。A.m+2B.m+1C.mD.m-1
阅读下列说明和流程图,将应填入(n)的语句写在对应栏内。【流程图说明】下面的流程(如图1所示)用N-S盒图形式描述了在一棵二叉树排序中查找元素的过程,节点有3个成员:data, left和right。其查找的方法是:首先与树的根节点的元素值进行比较:若相等则找到,返回此结点的地址;若要查找的元素小于根节点的元素值,则指针指向此结点的左子树,继续查找;若要查找的元素大于根节点的元素值,则指针指向此结点的右子树,继续查找。直到指针为空,表示此树中不存在所要查找的元素。【算法说明】【流程图】将上题的排序二叉树中查找元素的过程用递归的方法实现。其中NODE是自定义类型:typedef struct node {int data;struct node * left;struct node * right;}NODE;【算法】NODE * SearchSortTree(NODE * tree, int e){if(tree!=NULL){if(tree->data<e)(4); //小于查找左子树else if(tree->data<e)(5); //大于查找左子树else return tree;}return tree;}
某二叉树的先序遍历(根、左、右)序列为 EFHIGJK 、中序遍历(左、根、右)序列为HFIEJKG, 则该二叉树根结点的左孩子结点和右孩子结点分别是( )。A.A,I.KB.F,IC.F,GD.I,G
某二叉树的先序遍历(根、左、右)序列为 EFHIGJK 、中序遍历(左、根、右)序列为 HFIEJKG, 则该二叉树根结点的左孩子结点和右孩子结点分别是(37)A.A,I.K B. F,I C. F,G D.I,G
设有一个不带头结点的单向链表,头指针为head,结点类型为NODE,每个结点包含一个数据域data和一个指针域next,该链表有两个结点,p指向第二个结点(尾结点),按以下要求写出相应语句。新开辟一个结点,使指针s指向该结点,结点的数据成员data赋值为1。
问答题设有一个不带头结点的单向链表,头指针为head,结点类型为NODE,每个结点包含一个数据域data和一个指针域next,该链表有两个结点,p指向第二个结点(尾结点),按以下要求写出相应语句。新开辟一个结点,使指针s指向该结点,结点的数据成员data赋值为1。
判断题在一棵具有n个结点的线索二叉树中,每个结点的指针域可能指向子女结点,也可能作为线索,使之指向某一种遍历次序的前驱或后继结点,所有结点中作为线索使用的指针域共有n个。A对B错