| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1148 人关注过本帖
标题:怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~?
只看楼主 加入收藏
sainimu78
Rank: 2
等 级:论坛游民
帖 子:57
专家分:26
注 册:2010-1-27
结帖率:100%
收藏
已结贴  问题点数:8 回复次数:7 
怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~?
怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~?

搜索更多相关主题的帖子: 递归 百度 算法 
2010-03-30 23:03
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:1 
程序代码:
/*

 * Author: Devil Wang

 * Data: 01-21-2010

 * Notes: Template For Binary Tree

 */
#ifndef __BINTREE_H_
#define __BINTREE_H_
#include<iostream>
#include<cstdlib>
using std::cin;
using std::cout;
struct Exception{};
template<class KeyType,class InfoType>
     struct TNode
     {
          KeyType key;
          InfoType info;
          TNode<KeyType,InfoType> *left;
          TNode<KeyType,InfoType> *right;
          TNode<KeyType,InfoType> *parent;
          TNode<KeyType,InfoType>():left(NULL),right(NULL),parent(NULL){}
          TNode<KeyType,InfoType>(KeyType val, InfoType infoval=0):key(val),left(NULL),right(NULL),parent(NULL)
               {
                    info=infoval;
               }
          friend ostream & operator<<(ostream &out,TNode<KeyType,InfoType> &Node)
               {
                    out<<Node.key;
                    return out;
               }
     } ;
template<class KeyType, class InfoType>
     class BinTree
{
private:
     TNode<KeyType,InfoType> *root;
     size_t Size;
protected:
     TNode<KeyType,InfoType> *minimum( TNode<KeyType,InfoType> *point)const
     {
          TNode<KeyType,InfoType> *p=point;
          while( NULL != p->left )
          {
               p=p->left;
          }
          try{
               if( NULL == p )
                    throw Exception();
               return p;
          }catch( Exception e )
           {
                exit;
           }
     }
     TNode<KeyType,InfoType> * maximum(TNode<KeyType,InfoType> *point)const
     {
          TNode<KeyType,InfoType> *p=point;
          while( NULL != p->right )
          {
               p=p->right;
          }
          try{
               if( NULL == p )
                    throw Exception();
               return p;
          }catch( Exception e )
           {
                exit;
           }

     }
     int leafcont(TNode<KeyType,InfoType> *pointer )
     {
          static int cont=0;
          if (NULL!=pointer)
          {
               leafcont(pointer->left);
               if(NULL== pointer->left && NULL==pointer->right)
               {
                    cont++;
               }
               leafcont(pointer->right);
               return cont;
          }
     }
     void travel(TNode<KeyType,InfoType> *T)const
     {
          if( NULL!=T )
          {
               travel(T->left);
               cout<<*T<<" ";
               travel(T->right);
          }
          return ;
     }
public:
     BinTree<KeyType,InfoType>():root(NULL),Size(0){}
     BinTree<KeyType,InfoType>(int n):root(NULL),Size(0)
     {
          KeyType m;
          for(int i=0; i<n;i++)
          {
               cin>>m;
               BTinsert(m);
          }
     }
     ~BinTree()
     {
         TNode<KeyType,InfoType> *p;
         while( NULL != root->left || NULL != root->right)
         {
              p=minimum(root);
              BTDelete(p);
         }
         if( NULL !=root )
         {
              delete root;
         }
     }
     void BTInsert(KeyType val)
     {
          if( NULL == root)
          {
               root=new TNode<KeyType,InfoType>(val);
               root->parent=root;
               Size++;
               return ;
          }
          else
          {
               TNode<KeyType,InfoType> *pr=root,*cur;
               cur=(root->key>val)?root->left:root->right;
               while( NULL != cur )
               {
                    pr=cur;
                    cur=cur->key>val?cur->left:cur->right;
               }
               try{
                    if( NULL != cur )
                         throw Exception();
                    cur=new TNode<KeyType,InfoType> (val);
                    cur->parent=pr;
                    if( pr->key > val)
                         pr->left=cur;
                    else
                         pr->right=cur;
               }catch( Exception())
                {
                     cout<<"Catch An Exception"<<endl;
                     cout<<"BTInsert"<<endl;
                     exit;
                }
               Size++;
          }
     }
     TNode<KeyType,InfoType> * BTSearch(KeyType val)const
     {
          TNode<KeyType,InfoType> * p=root;
          while( NULL != p && p->key!=val )
          {
               p=(p->key>val)?p->left:p->right;
          }
          try
          {
               if( NULL == p )
                    throw Exception();
               return p;
          }catch ( Exception e)
           {
                cout<<"Catch An Exception"<<endl;
                cout<<"BTSearch"<<endl;
                return NULL;
           }
     }
     TNode<KeyType,InfoType> *BTMaximum()const{return maximum(root);}
     TNode<KeyType,InfoType> *BTMinimum()const{return minimum(root);}
     size_t size()
     {
          return Size;
     }
     bool empty()
     {
          return Size==0;
     }
     TNode<KeyType,InfoType> *BTSuccessor( TNode<KeyType,InfoType> *pointer )const
     {
          try
          {
               TNode<KeyType,InfoType> *point=pointer;
               if( NULL == point || point== maximum(root))
               {
                    throw Exception();
               }
               if ( NULL != point->right )
                    return point->right;
               TNode<KeyType,InfoType> *pr=point->parent;
               if( NULL == pr )
                    throw Exception();
               while( NULL != pr && point==pr->right )
               {
                    point=pr;
                    pr=pr->parent;
               }
               return pr;
          }catch( Exception e)
           {
                cout<<"Catch An Exception" <<endl;
                cout<<"BTSuccessor"<<endl;
                return NULL;
           }
     }
     TNode<KeyType,InfoType> * BTPredecessor(TNode<KeyType,InfoType> *pointer )const
     {
          try
          {
               TNode<KeyType,InfoType> *point=pointer,*pr;
               if( NULL == point || point == BinTree::minimum(root))
                    throw Exception();
               if( NULL != point->left )
                    return point->left;
               pr=point->parent;
               while( pr->left == point && NULL != pr )
               {
                    point=pr;
                    pr=pr->parent;
               }
               return pr;
          }catch ( Exception e )
           {
                cout<<"Catch An Exception" <<endl;
                cout<<"BTPredecessor"<<endl;
                return NULL;
           }
     }
     void BTDelete( TNode<KeyType,InfoType> * z)
     {
          TNode<KeyType,InfoType> *x,*y;
          if ( NULL == z->left && NULL == z->right && z==z->parent )
          {
               delete z;
               z=NULL;
               root=NULL;
               Size--;
               return ;
          }
          if( NULL==z->left || NULL == z->right )
               y=z;
          else
               y=BinTree::BTSuccessor(z);
          if( NULL != y->left)
               x=y->left;
          else
               x=y->right;
          if ( NULL !=x )
               x->parent=y->parent;
          if( y->parent==y)
          {
               root=x;
               x->parent=x;
          }
          else if (y== y->parent->left)
               y->parent->left=x;
          else
               y->parent->right=x;
          if( z!=y )
          {
               z->key=y->key;
               z->info=y->info;
          }
          delete y;
          Size--;
     }
     void BTTravel()
     {
          travel(root);
          cout<<endl;
     }
     int BTLeafCont(){return leafcont(root);} 
};
#endif
2010-03-30 23:40
sainimu78
Rank: 2
等 级:论坛游民
帖 子:57
专家分:26
注 册:2010-1-27
收藏
得分:0 
编译了一下 好几个错哦
好几个关键字没见过 呵呵
说明方式也没见过.. 真的是C吗...
我整本书都翻完了啊 都没见过类似的啊
2010-03-31 00:11
Devil_W
Rank: 10Rank: 10Rank: 10
等 级:青峰侠
威 望:9
帖 子:1160
专家分:1797
注 册:2009-9-14
收藏
得分:0 
楼上的忧郁的让人心疼。。。
2010-03-31 00:25
外部三电铃
Rank: 16Rank: 16Rank: 16Rank: 16
来 自:那一年
等 级:贵宾
威 望:57
帖 子:2012
专家分:7306
注 册:2007-12-17
收藏
得分:1 
以下是引用sainimu78在2010-3-31 00:11:03的发言:

编译了一下 好几个错哦
好几个关键字没见过 呵呵
说明方式也没见过.. 真的是C吗...
我整本书都翻完了啊 都没见过类似的啊
2楼的是C++代码

那一年,苍井空还是处女
2010-03-31 00:30
lucky563591
Rank: 11Rank: 11Rank: 11Rank: 11
等 级:小飞侠
威 望:4
帖 子:765
专家分:2103
注 册:2009-11-18
收藏
得分:1 
不懂啊!
2010-03-31 07:31
a654548060
Rank: 2
等 级:论坛游民
帖 子:18
专家分:10
注 册:2010-3-30
收藏
得分:1 
,不懂
2010-03-31 19:58
sainimu78
Rank: 2
等 级:论坛游民
帖 子:57
专家分:26
注 册:2010-1-27
收藏
得分:0 
啊 ..好想看看代码啊
2010-03-31 22:02
快速回复:怎么百度都百不到用非递归算法创建树~? 是不是非递归不比递归好~?
数据加载中...
 
   



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

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