读书人

遍历一单向链表用其结点建立一棵排序

发布时间: 2012-02-28 13:06:35 作者: rapoo

遍历一单向链表,用其结点建立一棵排序二叉树怎么实现
如题!!!!

[解决办法]
struct node{
struct node *next, left, right;
int data;
}


struct node * root=NULL;
struct node *list_head;


void add_node(struct node *node, struct node *head)
{
if (node || head || head-> data == node-> data) return;
if(node-> data < head-> data){
if (!head-> left) add_node(node, head-> left);
else head-> left = node;

}else{
if (!head -> right) add_node(node, head-> right)
else head-> right = node;
}
}

main()
{
if(!list_head) return;
root = list_head;
struct node *iterate = list_head-> next;
root-> letf=root-> right=NULL;
while(iterate)
{
add(iterate,root);
iterate-> left=iterate-right=NULL;
iterate = iterate-> next;

}

}
[解决办法]
#include <iostream.h>
#include <malloc.h>
#define NUM 10
typedef struct Node{
int data ;
struct Node *next;
}Node,*LNode;

typedef struct Tree{
int data ;
struct Tree *left ;
struct Tree *right ;
}Tree,*LTree ;

bool CreateList( LNode &Head ) //创建单链表
{
for(int i=1 ; i <=NUM ; i++)
{
LNode temp ;
temp = (LNode) malloc( sizeof( Node ) );
if(!temp)
return false ;
temp-> next = NULL;
cin> > temp-> data;
temp-> next = Head-> next ;
Head-> next = temp ;
}
return true ;
}

bool InsertSqTree( LTree &root , LNode temp ) //建二叉排序树
{
if(!root)
{
root = (LTree)malloc(sizeof(Tree));
if(!root)
return false ;
root-> left =NULL;
root-> right=NULL;
root-> data = temp-> data ;
return true ;
}
else
{
if(root-> data==temp-> data)
return true ;
else if(root-> data> temp-> data)
return InsertSqTree( root-> left , temp ) ;
else if(root-> data <temp-> data)
return InsertSqTree( root-> right , temp );
}
return true ;
}

void BianLiTree( LTree root ) //采用中序遍历
{
if(!root)
return ;
BianLiTree(root-> left);
cout < <root-> data < < " ";
BianLiTree(root-> right);
return ;
}

int main()
{
LNode Head = NULL;
LTree root = NULL ;
Head = (LNode) malloc(sizeof(Node));
if(!Head)
return 0 ;
Head-> next = NULL ;
if(!CreateList( Head ))
return 0;
LNode temp = Head-> next ;
while( temp )
{
if(!InsertSqTree( root ,temp ))
return 0 ;
Head-> next = temp-> next ;
free(temp);
temp = Head-> next ;
}
BianLiTree(root); //采用中序遍历,观察树节点
return 1;
}

读书人网 >软件架构设计

热点推荐