寻求二叉树建立的最优方法
寻求二叉树建立的最优方法?
最进学二叉树,看了看书上建立二叉树的方法,觉的不怎么好用,于是就自己写了一个,看了半天,感觉也不是很好,顾此寻求二叉树建立的最优方法.
请各位高手帮帮忙,谢了!
下面是我写的代码:
主要思路:从根结点开始,自顶向下建立二叉树,不拘泥于固定的顺序.
//BiTree.h
#ifndef BiTree_h
#define BiTree_h
#include <istream.h>
#include <stdlib.h>
template <class Type> class BiTree;
template <class Type> class BiTreeNode{// 二叉树结点类
friend class BiTree <Type> ;
private:
Type data;
BiTreeNode <Type> * leftChild;
BiTreeNode <Type> * rightChild;
public:
BiTreeNode():leftChild(NULL),rightChild(NULL){}//构造函数
BiTreeNode(Type item,BiTreeNode <Type> * left=NULL,
BiTreeNode <Type> * right=NULL)
{
data=item;
leftChild=left;
rightChild=right;
}
};
template <class Type> class BiTree{
private:
BiTreeNode <Type> * root;
char CreatBiTree(istream& in,BiTreeNode <Type> *& subTree);
Type RefValue;//用户自定义输入二叉树数据结束标志
public:
BiTree():root(NULL){}//构造函数
BiTree(Type value):RefValue(value),root(NULL){}
//重载操作：输入
friend istream&operator> > (istream& in,BiTree <Type> & Tree);
};
template <class Type>
istream& operator> >
(istream & in,BiTree <Type> & Tree)
{
Tree.CreatBiTree(in,Tree.root);
return in;
}
//建立二叉树
template <class Type>
char
BiTree <Type> ::CreatBiTree(istream& in,BiTreeNode <Type> *& subTree)
{
Type item;char symbol;//输入下一个结点的标志,
//若symbol== 'l '则下一个结点是当前结点的LeftChild
//若symbol== 'b '则返回上一个结点
// '# '为输入结束标志
in> > item> > symbol;
if(item!=RefValue)
{
if(subTree==NULL)
subTree=new BiTreeNode <Type> (item);
else
subTree-> data=item;
if(symbol== 'L '||symbol== 'l ')
{
cout < < "leftChild= ";
symbol=CreatBiTree(in,subTree-> leftChild);
}
if(symbol== 'R '||symbol== 'r ')
{
cout < < "rightChild= ";
symbol=CreatBiTree(in,subTree-> rightChild);
}
if(symbol== 'B '||symbol== 'b ')
{
cout < < "返回到: " < <item < < "的双亲结点\n ";
cout < < "选择L or R or Back: ";
in> > symbol;
return symbol;
}
if(symbol== '# ')
return '# ';
}
else
return '# ';
}
#endif
//Main.cpp
#include <iostream.h>
#include "BiTree.h "
void main()
{
BiTree <char> Tree( '# ');
cin> > Tree;
Tree.PreOrder(Tree.GetRoot());//先序遍历函数(自己写吧)
}
输出结果:
a l
leftChild=b l
leftChild=c b
返回到:c的双亲结点
选择L or R or Back:r
rightChild=d b
返回到:d的双亲结点
选择L or R or Back:b
返回到:b的双亲结点
选择L or R or Back:r
rightChild=e r
rightChild=f l
leftChild=g #
先序遍历:
a b c d e f g Press any key to continue
[解决办法]
看看这个...没有注释...试着看看..
#ifndef BINARY_SEARCH_TREE_H
#define BINARY_SEARCH_TREE_H
#include <iostream>
using namespace std;
template <typename T>
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree(const BinarySearchTree &rhs);
~BinarySearchTree();
const T &FindMax() const;
const T &FindMin() const;
bool Contains(const T &x) const;
bool IsEmpty() const;
void PrintTree() const;
void MakeEmpty();
void Insert(const T &x);
void Remove(const T &x);
const BinarySearchTree &operator=(const BinarySearchTree &rhs);
private:
struct BinaryNode
{
T element;
BinaryNode *left;
BinaryNode *right;
BinaryNode(const T &the_element,BinaryNode *lt,BinaryNode *rt)
: element(the_element), left(lt), right(rt){ }
};
BinaryNode *root;
void Insert(const T &x,BinaryNode *&t) const;
void Remove(const T &x,BinaryNode *&t) const;
BinaryNode *FindMax(BinaryNode *t) const;
BinaryNode *FindMin(BinaryNode *t) const;
bool Contains(const T &x,BinaryNode *t) const;
void MakeEmpty(BinaryNode *&t);
void PrintTree(BinaryNode *t) const;
BinaryNode *Clone(BinaryNode *t) const;
};
template <typename T>
BinarySearchTree <T> ::BinarySearchTree():root(NULL){}
template <typename T>
BinarySearchTree <T> ::BinarySearchTree(const BinarySearchTree &rhs):root(NULL)
{
*this=rhs;
}
template <typename T>
BinarySearchTree <T> ::~BinarySearchTree()
{
MakeEmpty();
}
template <typename T>
const T &BinarySearchTree <T> ::FindMax() const
{
if( IsEmpty() )
{
cerr < < "Empty " < < endl;
system( "pause ");
exit(1);
}
return FindMax(root)-> element;
}
template <typename T>
const T &BinarySearchTree <T> ::FindMin() const
{
if( IsEmpty() )
{
cerr < < "Empty " < < endl;
system( "pause ");
exit(1);
}
return FindMin(root)-> element;
}
template <typename T>
bool BinarySearchTree <T> ::Contains(const T &x) const
{
return Contains(x,root);
}
template <typename T>
bool BinarySearchTree <T> ::IsEmpty() const
{
return root==NULL;
}
template <typename T>
void BinarySearchTree <T> ::PrintTree() const
{
if( isEmpty() )
{
cout < < "Empty tree " < < endl;
}
else
{
PrintTree(root);
}
}
template <typename T>
void BinarySearchTree <T> ::MakeEmpty()
{
MakeEmpty(root);
}
template <typename T>
void BinarySearchTree <T> ::Insert( const T &x)
{
Insert(x,root);
}
template <typename T>
void BinarySearchTree <T> ::Remove( const T &x)
{
Remove(x,root);
}
template <typename T>
const BinarySearchTree <T> &BinarySearchTree <T> ::operator=(const BinarySearchTree &rhs)
{
if( this!=&rhs )
{
MakeEmpty();
root=Clone(rhs.root);
}
return *this;
}
template <typename T>
void BinarySearchTree <T> ::Insert(const T &x,BinaryNode *&t) const
{
if( t==NULL )
{
t=new BinaryNode(x,NULL,NULL);
}
else if( x <t-> element )
{
Insert(x,t-> left);
}
else if( t-> element> x )
{
Insert(x,t-> right);
}
else
; //duplicate,do nothing
}
template <typename T>
void BinarySearchTree <T> ::Remove(const T &x,BinaryNode *&t) const
{
if( t==NULL )
{
return; //item not found,do noting
}
if( x <t-> element )
{
Remove(x,t-> left);
}
else if( t-> element <x )
{
Remove(x,t-> right);
}
else if( t-> left!=NULL && t-> right!=NULL ) //two children
{
t-> element=FindMin(t-> right)-> element;
Remove(t-> element,t-> right);
}
else
{
BinaryNode *old_node=t;
t=( t-> left!=NULL ) ? t-> left : t-> right;
delete old_node;
}
}
template <typename T>
typename BinarySearchTree <T> ::BinaryNode *BinarySearchTree <T> ::FindMin(typename BinarySearchTree <T> ::BinaryNode *t) const
{
if( t==NULL )
{
return NULL;
}
if( t-> left==NULL )
{
return t;
}
return FindMin(t-> left);
}
template <typename T>
typename BinarySearchTree <T> ::BinaryNode *BinarySearchTree <T> ::FindMax(typename BinarySearchTree <T> ::BinaryNode *t) const
{
if( t!=NULL )
{
while( t-> right!=NULL )
{
t=t-> right;
}
}
return t;
}
template <typename T>
bool BinarySearchTree <T> ::Contains(const T &x,BinaryNode *t) const
{
if( t==NULL )
{
return false;
}
else if( x <t-> element )
{
return Contains(x,t-> left);
}
else if( t-> element )
{
return Contains(x,t- <right);
}
else
{
return true; //match
}
}
template <typename T>
void BinarySearchTree <T> ::MakeEmpty(BinaryNode *&t)
{
if( t!=NULL )
{
MakeEmpty(t-> left);
MakeEmpty(t-> right);
delete t;
}
t=NULL;
}
template <typename T>
void BinarySearchTree <T> ::PrintTree(BinaryNode *t) const
{
if( t!=NULL )
{
PrintTree(t-> left);
cout < < t-> element < < endl;
PrintTree(t-> right);
}
}
template <typename T>
typename BinarySearchTree <T> ::BinaryNode *BinarySearchTree <T> ::Clone(typename BinarySearchTree <T> ::BinaryNode *t) const
{
if( t==NULL )
{
return NULL;
}
return new BinaryNode(t-> element,Clone(t-> left),Clone(t-> right));
}
#endif
[解决办法]
http://community.csdn.net/Expert/TopicView3.asp?id=5489946