#2
书生牛犊2016-12-28 17:27
|
程序代码:
//输入空格间隔,换行结束,再输入所要查找的数,输出其所在层,在访问结点不会写了。总是不对,求帮助
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node *lchild,*rchild;
} BSTNode;
typedef BSTNode *BSTree;
//二叉排序树插入
//若二叉排序树 *Tptr中没有关键字为key,则插入,否则直接返回
void InsertBST( BSTree *TPtr , KeyType key )
{
BSTNode *f , *p;
p = *TPtr; //p的初值指向根结点
while(p) //查找插入位置
{
if( p->key == key ) //树中已有key,无须插入
{
return;
}
f=p; //f保存当前查找的结点
//若key<p->key,则在左子树中查找,否则在右子树中查找
p=(key<p->key)? p->lchild:p->rchild;
}
p=(BSTNode *)malloc( sizeof(BSTNode) );
p->key=key;
p->lchild=p->rchild=NULL; //生成新结点
if(*TPtr==NULL) //原树为空
{
*TPtr=p; //新插入的结点为新的根
}
else //原树非空时将新结点p作为f的左孩子或右孩子插入
{
if(key<f->key)
{
f->lchild=p;
}
else
{
f->rchild=p;
}
}//[flczzhang]-> miss a }
}
//创建二叉排序树
//输入一个结点序列,建立一棵二叉排序树,将根结点指针返回
BSTree CreateBST( void )
{
BSTree T=NULL;
KeyType key;
scanf( "%d" , &key );
while(key) //假设key=0是输人结束标志
{
InsertBST( &T , key ); //将key插入二叉排序树T
scanf( "%d" , &key ); //读人下一关键字
}
return T;
}
//查找二叉排序树 T 中是否存在指定的 key
//指针 f 指向 T 的双亲, f 初始值为 NULL
//若查找成功返回1,指针p指向该数据元素结点,否则返回0,p指向查找过程中的最后一个结点
int SearchBST( BSTree T , int key , BSTree f , BSTree *p)
{
if( !T )
{
*p = f;
return 0;
}
else if( T->key == key )
{
*p = T;
return 1;
}
else if( T->key > key )
{
return SearchBST( T->lchild , key , T , p );
}
else
{
return SearchBST( T->rchild , key , T , p );
}
}
//访问节点数据
void visit( KeyType c , int level )
{
printf( "%d 在第 %d 层\n" ,c , level );//这里不对,不知道怎么写
}
//前序遍历树节点
void PreorderTraverse( BSTree T ,int level )
{
visit(T->key , level );
PreorderTraverse(T->lchild , level+1 );
PreorderTraverse(T->rchild , level+1 );
}
int main()
{
int level=1;
BSTree T;
T = CreateBST();//[flczzhang]-> type error for function name CreateBST(missing e)
PreorderTraverse( T , level );
return 0;
}
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node *lchild,*rchild;
} BSTNode;
typedef BSTNode *BSTree;
//二叉排序树插入
//若二叉排序树 *Tptr中没有关键字为key,则插入,否则直接返回
void InsertBST( BSTree *TPtr , KeyType key )
{
BSTNode *f , *p;
p = *TPtr; //p的初值指向根结点
while(p) //查找插入位置
{
if( p->key == key ) //树中已有key,无须插入
{
return;
}
f=p; //f保存当前查找的结点
//若key<p->key,则在左子树中查找,否则在右子树中查找
p=(key<p->key)? p->lchild:p->rchild;
}
p=(BSTNode *)malloc( sizeof(BSTNode) );
p->key=key;
p->lchild=p->rchild=NULL; //生成新结点
if(*TPtr==NULL) //原树为空
{
*TPtr=p; //新插入的结点为新的根
}
else //原树非空时将新结点p作为f的左孩子或右孩子插入
{
if(key<f->key)
{
f->lchild=p;
}
else
{
f->rchild=p;
}
}//[flczzhang]-> miss a }
}
//创建二叉排序树
//输入一个结点序列,建立一棵二叉排序树,将根结点指针返回
BSTree CreateBST( void )
{
BSTree T=NULL;
KeyType key;
scanf( "%d" , &key );
while(key) //假设key=0是输人结束标志
{
InsertBST( &T , key ); //将key插入二叉排序树T
scanf( "%d" , &key ); //读人下一关键字
}
return T;
}
//查找二叉排序树 T 中是否存在指定的 key
//指针 f 指向 T 的双亲, f 初始值为 NULL
//若查找成功返回1,指针p指向该数据元素结点,否则返回0,p指向查找过程中的最后一个结点
int SearchBST( BSTree T , int key , BSTree f , BSTree *p)
{
if( !T )
{
*p = f;
return 0;
}
else if( T->key == key )
{
*p = T;
return 1;
}
else if( T->key > key )
{
return SearchBST( T->lchild , key , T , p );
}
else
{
return SearchBST( T->rchild , key , T , p );
}
}
//访问节点数据
void visit( KeyType c , int level )
{
printf( "%d 在第 %d 层\n" ,c , level );//这里不对,不知道怎么写
}
//前序遍历树节点
void PreorderTraverse( BSTree T ,int level )
{
visit(T->key , level );
PreorderTraverse(T->lchild , level+1 );
PreorderTraverse(T->rchild , level+1 );
}
int main()
{
int level=1;
BSTree T;
T = CreateBST();//[flczzhang]-> type error for function name CreateBST(missing e)
PreorderTraverse( T , level );
return 0;
}