数据结构基础练习

二叉树的层序创建

测试样例

5
aa bb cc dd ee

/*二叉树的层序创建(创建完成！) 层序创建需要注意的点：1.表面上创建时并没有对树进行遍历，实际上创建时是以队列的形式对树进行遍历2.当出队的树结点的左或者右子树不为空时，将这个结点的左或者右子树入队3.如果出队的树结点的左或者右子树为空时，则将新建的结点加入到当前树结点的左或者右子树中（谁空就加在谁上，加完就直接退出）
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define MAX 100 //定义字符串的大小  
typedef char elem;
typedef struct treenode *ptr;
struct treenode{elem data[MAX];ptr left;ptr right;
};
struct node{ptr root;
};
typedef struct node *tree;//创建树的根节点  
int flag=1;typedef struct Lnode *Lptr;
struct Lnode{//链队结点ptr tnode;Lptr next;Lptr end;
};
typedef Lptr list;list init(){//链队的初始化list L;L=(Lptr)malloc(sizeof(struct Lnode));L->next=NULL;L->end=NULL;return L;
}list in(list L,ptr tnode){//入队Lptr p;p=(Lptr)malloc(sizeof(struct Lnode));p->tnode=tnode;//将树的结点入队p->next=NULL;if(L->next==NULL){//当L是空链队时直接将数据入队L->next=p;}else{L->end->next=p;}L->end=p;return L;
}ptr out(list L){//出队（返回树结点的指针）ptr p;p=L->next->tnode;return p;
}list out2(list L){Lptr p;p=L->next;L->next=p->next;//将头节点的下一个指向被释放的下一个（易错）free(p);return L;
}int pdk(list L){//判断队空if(L->next==NULL){return 1;}return 0;
}tree create(){//树的初始化tree t;t=(struct node *)malloc(sizeof(struct treenode));t->root=NULL;return t;
}tree add(tree t,elem data[MAX]){//将字符串加入树中ptr p;ptr q;//新建树结点p=(ptr)malloc(sizeof(struct treenode));strcpy(p->data,data);p->left=p->right=NULL;if(t->root==NULL){t->root=p;}else{//创建队列list L;L=init();//创建空队//先将树的根节点加入队中L=in(L,t->root);while(1){q=out(L);//将队头出队L=out2(L);if(q->left!=NULL){//当队头的左子树不为空时，将队头的左子树入队L=in(L,q->left);}else{//若当前结点的左子树为空时将则将新建结点加入树中，并退出当前循环以防不正当插入q->left=p;break;}if(q->right!=NULL){//与上同理L=in(L,q->right);}else{q->right=p;break;}if(pdk(L)==1){break;}}}return t;
}//先序
void print(ptr p){//传递树的标识也就是根节点if(p!=NULL){printf("%s\n",p->data);print(p->left);print(p->right);}
}int main()
{int n;tree t;char s[MAX];t=create();scanf("%d",&n);for(int i=0;i<n;i++){scanf("%s",s);t=add(t,s);}print(t->root);//system("pause");return 0;
}// tree add(tree t,elem s[MAX]){//创建树
// 	ptr p;
// 	p=(ptr)malloc(sizeof(struct treenode));
// 	strcpy(p->data,s);
// 	p->left=NULL;
// 	p->right=NULL;
// 	strcmp(p->data)
// 	if(t->root==NULL){
// 		t->root=p;
// 	}else{
// 		ptr q;
// 		if(flag==1){//将树的结点按照偶数次放在根节点的左子树（偶数次是因为根节点也算一次插入）  
// 			q=t->root->left;
// 		}else{
// 			q=t->root->right;
// 		}
// 		q=t->root;
// 		while(1){
// 			if(q->left==NULL){
// 				q->left=p;
// 				break;
// 			}else if(q->right==NULL){
// 				q->right=p;
// 				break;
// 			}
// 			if(flag==1){
// 				q=q->left;
// 			}else{
// 				q=q->right;
// 			}
// 		}
// 		if(q->left!=NULL&&q->right!=NULL){
// 			flag=-flag;
// 		}
// 	}
// 	return t;
// }