[数据结构]树形结构

这是偶今天的作业

1、请使用数组输入二叉树的结点数据,以结构体数组表示法创建二叉树,完成后将结构数组内容输出。
2、请使用数组输入二叉树的结点数据,以链表结构创建二叉树,完成后将链表内容输出。

提示:创建二叉树结点数据的策略有三个,如下:
1 将第一个要创建的元素插入成为根节点。
2 将元素值与结点值比较,如果元素值大于结点值,将此元素送往结点的右儿子结点,如果右儿子结点不是空的,需要重复比较,否则创建结点将元素值插入。
3 如果元素值小于结点值,将此元素送往结点的左儿子结点,如果左儿子结点不是空的,需要重复比较,否则创建结点将此元素值插入。
例如:二叉树结点值输入的数据顺序是5,6,4,8,2,3,7,1,9。按照上述策略创建的二叉树,如下图所示:

shu

代码。
(今天代码完全是偶自己写的)
gcc 下编译通过

1.数组法的代码


#include “stdio.h”
#include “math.h”
#include “stdlib.h”

/*
使用数组输入二叉树的结点数据,以结构体数组表示法创建二叉树,完成后将结构数组内容输出
*/

struct treesz {
int lchild,rchild,father;
int value ;

}sz[11] ;
/* sz[0]没有使用 */

/* cnode 是用于创建二叉树的过程中的全局变量,表示当前已经创建的结点个数 */
int cnode ;

void szinsert(struct treesz a[],int number,int node){
if (a[node].value

2.链表法的代码


#include “stdio.h”
#include “math.h”
#include “stdlib.h”
/* 使用数组输入二叉树的结点数据,以链表结构创建二叉树,完成后将链表内容输出 */

typedef struct otreelb {
int value;
struct otreelb *lchild,*rchild,*father ;
}treelb ;

treelb* insert(int number,treelb* current ){
treelb* newl ;

if (current==NULL)
{
newl=(treelb *)malloc(sizeof(treelb));
current=newl;
current->value=number ;
return current ;
}

else{
if(current->valuerchild==NULL) {newl=(treelb *)malloc(sizeof(treelb)); current->rchild=newl ; newl->father=current; newl->value=number; return newl;}
else {current=current->rchild ; insert(number,current) ; }
}
else{
if(current->lchild==NULL) {newl=(treelb *)malloc(sizeof(treelb)); current->lchild=newl ; newl->father=current; newl->value=number; return newl;}
else{ current=current->lchild ; insert (number,current) ;}
}
}

}

/* 从数组创建二叉树链表函数,返回二叉树头指针 */

treelb* create(int a[],int length) {
int i;
treelb* re ;
treelb* temp=NULL;

re= insert(a[1],temp) ;
temp=re ;
for(i=2;ivalue) ;
if(head->lchild==NULL && head->rchild==NULL) printf(“His left child is NULL , his right child is NULL\n”) ;
if(head->lchild==NULL && head->rchild!=NULL) printf(“His left child is NULL , his right child is %d\n”,head->rchild->value) ;
if(head->lchild!=NULL && head->rchild==NULL) printf(“His left child is %d , his right child is NULL\n”,head->lchild->value) ;
if(head->lchild!=NULL && head->rchild!=NULL) printf(“His left child is %d , his right child is %d\n”,head->lchild->value,head->rchild->value) ;
}
if (head->lchild!=NULL) print(head->lchild) ;
if (head->rchild!=NULL) print(head->rchild) ;
}

int main(){

int i=0;
int input[11]={0,5,6,4,8,2,3,7,1,9,10} ;

printf(“The input array is :\n”) ;

for(i=1;i<11;i++) printf("%d \t",input[i]); printf("\n\n") ; treelb* lb ; lb=create(input,10) ; print(lb) ; return 0; }

0 Responses to “[数据结构]树形结构”


Comments are currently closed.