| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3221 人关注过本帖
标题:二叉排序树,输出所要查找的数所在层数
只看楼主 加入收藏
Ocean1
Rank: 2
等 级:论坛游民
帖 子:25
专家分:20
注 册:2016-11-10
结帖率:100%
收藏
已结贴  问题点数:20 回复次数:2 
二叉排序树,输出所要查找的数所在层数
程序代码:
//输入空格间隔,换行结束,再输入所要查找的数,输出其所在层,在访问结点不会写了。总是不对,求帮助
#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 
2016-12-27 12:48
书生牛犊
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:星夜征程
等 级:贵宾
威 望:10
帖 子:1101
专家分:5265
注 册:2015-10-27
收藏
得分:20 
要知道某结点在二叉树的层数,必须从根节点往下遍历寻找该节点的时候就做计数,找到那个元素的时候直接输出计数结果就行了。
//访问节点数据
void visit( KeyType c , int level )
{

    printf( "%d 在第 %d 层\n" ,c , level );//这里不对,不知道怎么写
}
你专门写一个visit()函数,从节点出发想要往根节点溯源 一般情况下是做不到的,除非你闲着没事给每个节点配上一个指针指向它的父节点。这对空间的消耗就要大一些了。。不划算!
程序代码:
//查找二叉排序树 T 中是否存在指定的 key
//指针 f 指向 T 的双亲, f 初始值为 NULL
//若查找成功返回所在层数,指针p指向该数据元素结点,否则返回0,p指向查找过程中的最后一个结点
int SearchBST( BSTree T , int key , BSTree f , BSTree *p)
{
static int Cen=0;/*静态变量,生存周期为该次递归开始直到释放*/
Cen++;
if( !T )
{
*p = f;
return 0;
}
else if( T->key == key )
{
*p = T;
return Cen;
}
else if( T->key > key )
{
return SearchBST( T->lchild , key , T , p );
}
else
{
return SearchBST( T->rchild , key , T , p );
}






φ(゜▽゜*)♪
2016-12-28 17:27
Ocean1
Rank: 2
等 级:论坛游民
帖 子:25
专家分:20
注 册:2016-11-10
收藏
得分:0 
回复 2楼 书生牛犊
大神,这个怎么加到整个程序里啊,研究半天,不会弄,新手,不知道怎么调用
2016-12-28 20:55
快速回复:二叉排序树,输出所要查找的数所在层数
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.032494 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved