学习c语言的第二十八天

 二叉树的建立以及前中后序遍历：

输入：二叉树的结构体变量为BiTree T，其成员是int data（data用来存储二叉树的结点的值），以及 struct Tree *lchild（指针指向二叉树的左孩子）, struct Tree *rchild;（指针指向二叉树的右孩子）。

输出：按照前中后序遍历树T，输出遍历结果。

优化目标：可能没有优化目标。

#include
#include
typedef struct Tree{
	int data;
	struct Tree *lchild;
	struct Tree *rchild;
}Tree,*BiTree; 

BiTree CreateTree(){
	int n;
	BiTree t;
	printf("根结点为：");
	scanf("%d",&n);
	if(n==-1){
		return NULL;
	} {
		t=(BiTree)malloc(sizeof(Tree));
		t->data=n;
		printf("输入%d左子树",n);
		t->lchild= CreateTree();
		printf("输入%d右子树",n);
		t->rchild= CreateTree();
		return t;
	}
}

void Preorder(BiTree T){
	if(T==NULL){
		return NULL;
	} 
	printf("%d",T->data);
	Preorder(T->lchild);
	Preorder(T->rchild);
}

void Inorder(BiTree T){
	if(T==NULL){
		return NULL;
	} 
	Inorder(T->lchild);
	printf("%d",T->data);
	Inorder(T->rchild);
}

void Postorder(BiTree T){
	if(T==NULL){
		return NULL;
	} 
	Postorder(T->lchild);
	Postorder(T->rchild);
	printf("%d",T->data);
}

int main(){ 
    BiTree T=CreateTree();
    printf("前序为：");
	Preorder(T);
	printf("n"); 
	printf("中序为：");
    Inorder(T); 
    printf("n"); 
    printf("后序为：");
	Postorder(T);
	
} 

 二叉树的叶子结点数以及树的高度：

输入：二叉树的结构体变量为BiTree T，其成员是int data（data用来存储二叉树的结点的值），以及 struct Tree *lchild（指针指向二叉树的左孩子）, struct Tree *rchild;（指针指向二叉树的右孩子）。

输出：树的叶子结点数num以及树的高度high。

优化目标：可能没有优化目标。
 

#include
#include
typedef struct Tree{
	int data;
	struct Tree *lchild;
	struct Tree *rchild;
}Tree,*BiTree; 

BiTree CreateTree(){
	int n;
	BiTree t;
	printf("根结点为：");
	scanf("%d",&n);
	if(n==-1){
		return NULL;
	} {
		t=(BiTree)malloc(sizeof(Tree));
		t->data=n;
		printf("输入%d左子树",n);
		t->lchild= CreateTree();
		printf("输入%d右子树",n);
		t->rchild= CreateTree();
		return t;
	}
}

int Depth(BiTree T){
	if(T==NULL){
		return 0;
	}else{
		int m=Depth(T->lchild);
		int n=Depth(T->rchild); 
		if(m>=n){
			return (m+1);
		}else return (n+1);
	}
}
int Totalnum(BiTree T){
	if(T==NULL){
		return 0;
	}else{
		return (Totalnum(T->lchild)+Totalnum(T->rchild)+1);
	}
}
	
int main(){
		BiTree T=CreateTree();
		int high;
		high=Depth(T); 
		printf("树的高度为%d",high);
		int num;
		num=Totalnum(T); 
		printf("该树共有%d个结点",num);
} 

输出链表中的奇数结点。

输入：链表各个结点的值num。

输出：全为奇数的链表的值。

优化目标：昨天的练习中是把链表直接分成了全为奇数的链表和全为偶数的链表，空间复杂度过高，现在第二版直接在链表中删除偶数结点来达到效果，如果只需要输出正确，第三版也可以直接筛选奇数输出。

第一版：

#include
#include
typedef struct LNode *list;
struct LNode{
	int data;
	list next;	
}; 
 
void print(list l){//输出操作 
	if(l==NULL){
		printf("NULL");
	}
	while(l!=NULL){
		printf("%d ",l->data);
		l=l->next;
	}
}
 

int ji(list l){
	list l1;
	l1->next=NULL;
	list l2=l1;
	while(l!=NULL){
	    if(l->data%2!=0){
	    	list q=(list)malloc(sizeof(struct LNode));
	    	q->next=NULL;
		    q->data=l->data;
		    l1->next=q;
		    l1=q;
		}
		l=l->next;
	}
	return l2;
}
 
int main(){
    int num;
    list l;
    list l1=l;
    l->next=NULL;
	scanf("%d",&num);
	while(num!=-1){
		list q=(list)malloc(sizeof(struct LNode));
		q->next=NULL;
		q->data=num;
		l->next=q;
		l=q;
		scanf("%d",&num);
	}
	
	list l2=l1;
	l1=l1->next;	
	print(l1);
	printf("n");
	list l3=ji(l1);
	list la=l3->next;
	printf("奇数结点:");
	print(la);

}

第二版： 

#include
#include
typedef struct LNode *list;
struct LNode{
	int data;
	list next;	
}; 
 
void print(list l){
	if(l==NULL){
		printf("NULL");
	}
	while(l!=NULL){
		printf("%d ",l->data);
		l=l->next;
	}
}
 


int main(){
    int num;
    list l;
    list l1=l;
    l->next=NULL;
	scanf("%d",&num);
	while(num!=-1){
		list q=(list)malloc(sizeof(struct LNode));
		q->next=NULL;
		q->data=num;
		l->next=q;
		l=q;
		scanf("%d",&num);
	}
	list l2=l1;
	l1=l1->next;
	printf("结点：");	
	print(l1);
	printf("n");
    if(l2->next==NULL){
	 	return NULL;
	}
	list p=l2;
    list q=l2;
    l2=l2->next;
    while(l2!=NULL){
    	if(l2->data%2==0){
    		q->next=l2->next;
    		l2=q->next;
		}else{
			q=q->next;
    		l2=l2->next;
		}
	}
	p=p->next;
	printf("奇数结点：");
	print(p);
}

第三版：

#include
#include
typedef struct LNode *list;
struct LNode{
	int data;
	list next;	
}; 
 
void print(list l){
	if(l==NULL){
		printf("NULL");
	}
	while(l!=NULL){
		printf("%d ",l->data);
		l=l->next;
	}
}
 


int main(){
    int num;
    list l;
    list l1=l;
    l->next=NULL;
	scanf("%d",&num);
	while(num!=-1){
		list q=(list)malloc(sizeof(struct LNode));
		q->next=NULL;
		q->data=num;
		l->next=q;
		l=q;
		scanf("%d",&num);
	}
	l1=l1->next;
	printf("结点：");	
	print(l1);
	printf("n");
	printf("奇数结点：");
	while(l1!=NULL){
		if(l1->data%2!=0){
			printf("%d ",l1->data);
			l1=l1->next;
		}else{
			l1=l1->next;
		}
	}
}

今天复习了二叉树的基本操作和链表的知识，代码还是要多复习才能熟悉！