游客 注册 | 登录
中文 | En
  • 首页
  • 题库
  • 2585 - 数据结构/二叉树/创建与遍历（软件1、2）

2585 - 数据结构/二叉树/创建与遍历（软件1、2）

  

<span style="font-size:9pt;">实验原理：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　二叉树是最重要的一类树型结构，而二叉链表是二叉树的一种比较直观和灵活的存储结构。在二叉链表中的每个结点由三部分组成：左孩子指针、右孩子指针和结点数据。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　其中左右孩子指针分别指向本结点的左右孩子结点，如果一个结点的左右孩子不存在，则对应的指针记录为空值，</span><span style="font-family:Tahoma;font-size:9pt;">C</span><span style="font-size:9pt;">语言用</span><span style="font-family:Tahoma;font-size:9pt;">NULL</span><span style="font-size:9pt;">表示，画图时用</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">表示。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　结点数据的数据类型应该根据实际应用进行选择，在本次实验中，选用字符类型。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span> 


<span style="font-size:9pt;">　　输入创建原理：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　创建二叉树可以用递归方式进行，下面用伪代码来描述创建流程：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　１、结点</span><span style="font-family:Tahoma;font-size:9pt;">* </span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">(){</span> 


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span><span style="font-size:9pt;">定义结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 


<span style="font-size:9pt;">　　　　　　输入结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 


<span style="font-size:9pt;">　　　　　　如果　结点数据为空　则返回</span><span style="font-family:Tahoma;font-size:9pt;">NULL;//</span><span style="font-size:9pt;">规定输入字符</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">表示本结点不创建</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　　　　　创建结点</span><span style="font-family:Tahoma;font-size:9pt;">* node;</span> 


<span style="font-size:9pt;">　　　　　　赋值</span><span style="font-family:Tahoma;font-size:9pt;">node</span><span style="font-size:9pt;">的数据为刚刚输入的结点数据</span><span style="font-family:Tahoma;font-size:9pt;">;</span> 


<span style="font-size:9pt;">　　　　　　</span><span style="font-family:Tahoma;font-size:9pt;">node.</span><span style="font-size:9pt;">左孩子</span><span style="font-family:Tahoma;font-size:9pt;">=</span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">();</span> 


<span style="font-size:9pt;">　　　　　　</span><span style="font-family:Tahoma;font-size:9pt;">node.</span><span style="font-size:9pt;">右孩子</span><span style="font-family:Tahoma;font-size:9pt;">=</span><span style="font-size:9pt;">创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">();</span> 


<span style="font-size:9pt;">　　　　　　返回</span><span style="font-family:Tahoma;font-size:9pt;"> node;</span> 


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; }</span> 


<span style="font-size:9pt;">　　２、在需要创建整棵二叉树的地方写上：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　　　　　　二叉树根结点　＝　创建结点函数</span><span style="font-family:Tahoma;font-size:9pt;">()</span><span style="font-size:9pt;">；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-family:Tahoma;font-size:9pt;">&nbsp; </span><span style="font-size:9pt;">　</span><span style="font-family:Tahoma;font-size:9pt;"> </span><span style="font-size:9pt;">遍历原理：要自己描述先序遍历、中序遍历原理。</span> 


<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span> 


<span style="font-size:9pt;">实验步骤：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　１、定义二叉链表结点类型；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　２、实现二叉链表创建方法；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　３、实现二叉链表的先序、中序遍历方法；</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">　　４、实现主函数</span><span style="font-family:Tahoma;font-size:9pt;"></span>

题目输入

  

<span style="font-size:9pt;"><span style="font-family:Tahoma;font-size:9pt;">&nbsp;


<span style="font-size:9pt;">每行一棵非空的二叉树，每棵二叉树按先序遍历形式，空指针用字符</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">占位，如图的一棵二叉树。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">如果读到一行的第一个字符就是</span><span style="font-family:Tahoma;font-size:9pt;">^</span><span style="font-size:9pt;">，表示没有更多输入了，程序退出。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-size:9pt;">测试时，每棵树不会超过</span><span style="font-family:Tahoma;font-size:9pt;">20</span><span style="font-size:9pt;">个结点。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-family:Tahoma;font-size:9pt;"></span>


<span style="font-size:9pt;">输入是：</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span style="font-family:Tahoma;font-size:9pt;">AB^DE^^^C^^</span> 


<span style="font-family:Tahoma;font-size:9pt;">^</span> 


&nbsp;


&nbsp;<span style="font-family:Tahoma;font-size:9pt;"><span style="font-family:Tahoma;font-size:9pt;">&nbsp;<span style="font-family:Tahoma;font-size:9pt;">&nbsp;</span></span></span></span></span><span style="font-family:Tahoma;font-size:9pt;"></span>

题目输出

  

<span style="font-size:9pt;">对于每个二叉树，分别进行先序遍历、中序遍历，每种遍历结果输出一行。</span><span style="font-family:Tahoma;font-size:9pt;"></span> 


<span></span>

输入/输出样例

题目输入

DL^^R^^
AB^DE^^^C^^
^

题目输出

DLR
LDR
ABDEC
BEDAC

提示


	1、主函数可以采用以下流程




	　　int main(){




	　　　　定义结点指针;




	             do{




	　　　　　　结点指针=创建结点函数();




	　　　　　　if (结点指针非空){




	　　　　　　　　先序遍历;换行




	　　　　　　　　中序遍历;换行




	                   }




	　　　　}while(结点指针非空);




	　　　　return 0;




	      }




	2、




	如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：




	char ch;
do{

 scanf("%c",&ch);

}while(ch<=32);//确保读到一个非空白非换行的字符





&nbsp;

C语言解答

#include "stdio.h"
#include "string.h"


struct node
{
	 char key;
	 int left;
	 int right;
	 int father;
};


struct node tree[100000];
int head,sum;



void xianxu(int n)
{
	if (n==-1) return;
	if (n==0) return;
	if (n>0) printf("%c",tree[n].key);
	if (tree[n].left>=0) xianxu(tree[n].left);
	if (tree[n].right>=0) xianxu(tree[n].right);
}

void zhongxu(int n)
{
	if (n==-1) return;
	if (n==0) return;
	if (tree[n].left>=0) zhongxu(tree[n].left);
	if (n>0) printf("%c",tree[n].key);
	if (tree[n].right>=0) zhongxu(tree[n].right);
}


int insert(int n,char key)
{
	if (n==-1)
	{
		sum++;
	    head=sum;
		tree[head].father=0;
		tree[head].left=-1;
		tree[head].right=-1;
		tree[head].key=key;
		return(1);
	}
	if (tree[n].left==-1) 
	{
		if (key=='^') tree[n].left=0;			
		else
		{
	    	sum++;
			tree[n].left=sum;
	    	tree[sum].father=n;
	    	tree[sum].left=-1;
	    	tree[sum].right=-1;
	    	tree[sum].key=key;
		}
		return(1);
	}
	if ((tree[n].left>0) &&(insert(tree[n].left,key)==1)) return;
	if (tree[n].right==-1) 
	{
		if (key=='^') tree[n].right=0;			
		else
		{
	    	sum++;
			tree[n].right=sum;
	    	tree[sum].father=n;
	    	tree[sum].left=-1;
	    	tree[sum].right=-1;
	    	tree[sum].key=key;
		}
		return(1);
	}
	if ((tree[n].right>0) &&(insert(tree[n].right,key)==1)) return;
}


void main()
{
	int i;
	char str[100];
	gets(str);
	while (1)
	{
    	sum=0;
    	head=-1;
    	for (i=0;i<strlen(str);i++)
    	{
    		insert(head,str[i]);
    	}
    	xianxu(head);
		printf("\n");
    	zhongxu(head);
		printf("\n");
		gets(str);
		if ((str[0]=='^')&&(strlen(str)==1)) break;
	}

}

C++解答

#include <stdio.h> 
#include <malloc.h>
typedef struct BiTNode{
  char data;
  struct BiTNode *lchild,*rchild;
}BitNode, *BiTree;
BiTree CreateBiTree()
{
  char da;
  BiTree T;
  do{
  scanf("%c",&da);
  }while(da<=32);
  if(da == '^')T=NULL;
  else{
   T=(BiTree)malloc(sizeof(BiTNode));
    T->data=da;
    T->lchild=CreateBiTree();
    T->rchild=CreateBiTree();
   }
  return T;
}
void PreOrderTraverse(BiTree T){
  if(T){
       printf("%c",T->data);
       PreOrderTraverse(T->lchild);
       PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(BiTree T){
    if(T){
       InOrderTraverse(T->lchild);
       printf("%c",T->data);
       InOrderTraverse(T->rchild);
 }
}
int main(){
 BiTree btree;
  do{
    btree=CreateBiTree();
    if(btree!=NULL){
    PreOrderTraverse(btree);
 printf("\n");
 InOrderTraverse(btree);
 printf("\n");
    }
  }while(btree!=NULL);
  return 0;
}

提示

1、主函数可以采用以下流程

　　int main(){

　　　　定义结点指针;

             do{

　　　　　　结点指针=创建结点函数();

　　　　　　if (结点指针非空){

　　　　　　　　先序遍历;换行

　　　　　　　　中序遍历;换行

                   }

　　　　}while(结点指针非空);

　　　　return 0;

      }

2、

如果不采用一次输入一行字符串处理其中每个字符，而是采用每次输入一个字符处理，需要略过空白换行等字符，如下：

char ch;

do{
 scanf("%c",&ch);
}while(ch<=32);//确保读到一个非空白非换行的字符 

&nbsp;

时间限制 1 秒
内存限制 8 MB
讨论 统计
上一题 下一题