可用分押宝游戏火热进行中...	专题改版：Java Web 专题

求表达式建二叉树代码!!!!!在线给分~~~

楼主hereisme（）2005-06-03 11:55:27 在 C/C++ / C++ 语言提问

RT~~
求表达式建二叉树代码!!!!!在线给分~~~ 问题点数：100、回复次数：20Top

1 楼sunman1982（冥王星）回复于 2005-06-03 12:00:45 得分 0

什么意思？是要binarytree代码？

//binarytree
#ifndef binarytree
#define binarytree

#include<iostream>

using std::cout;
using std::endl;

template <class Type>
struct nodeType
{
Type info;
nodeType<Type>*llink;
nodeType<Type>*rlink;
};//binarytree

template <class Type>
class binarytree
{
private:
void _destroytree(nodeType<Type>*p);//destroytree
void inorder(nodeType<Type>*p);//inorder
void preorder(nodeType<Type>*p);//preorder
void postorder(nodeType<Type>*p);//postorder
int _length(nodeType<Type>*p);//the lengrh of tree
void copytree(nodeType<Type>*tree1,nodeType<Type>*tree2);//copy the tree
int max(int x,int y);//the max of x and y
int _nodenum(nodeType<Type>*p);//num of node
int _leavenum(nodeType<Type>*p);//nim of leaves
protected:
nodeType<Type>*root;
public:
const binarytree<Type>& operator =(const binarytree<Type>&);//overload operator =
void inordertree();//inorder tree
void preordertree();// perrordertree
void postordertree();//postorder tree
binarytree();//constructor
~binarytree();//destructor
int length();//length of the tree
int nodenum();//num of tree node
int leavenum();//numof tree leavas
bool isempty();// isempty>??
void destroytree(); //destroy tree
binarytree(nodeType<Type>&);//copy constructor
};
//define the fuc of class
//************************************************************
//*******************_destroytree*****************************
template<class Type>
void binarytree<Type>::_destroytree(nodeType<Type>*p)
{
if(p!=NULL)
{
_destroytree(p->llink);
_destroytree(p->rlink);
delete p;
p=NULL;
}//end if
}//end des
//************************************************************
//******************inorder***********************************
template<class Type>
void binarytree<Type>::inorder(nodeType<Type>*p)
{
if(p!=NULL)
{
inorder(p->llink);
cout<<*p<<" ";
inorder(p->rlink);
}//end if
}//end inorder
//************************************************************
//*****************preorder***********************************
template<class Type>
void binarytree<Type>::preorder(nodeType<Type>*p)
{
if(p!=NULL)
{
cout<<*p<<" ";
preorder(p->llink);
preorder(p->rlink);
}//end if
}//enf preorder
//************************************************************
//*****************postorder**********************************
template<class Type>
void binarytree<Type>::postorder(nodeType<Type>*p)
{
if(p!=NULL)
{
postorder(p->llink);
postorder(p->rlink);
cout<<*p<<" ";
}//end if
}//end posterorder
//*************************************************************
//*****************length**************************************
template<class Type>
int binarytree<Type>::_length(nodeType<Type>*p)
{
if(p==NUll)
return 0;
else
return 1+max(_height(p->llink),_height(p->rlink));
} //end -length
//*************************************************************
//*****************copytree************************************
template<class Type>
void binarytree<Type>::copytree(nodeType<Type>*tree1,nodeType<Type>*tree2)
{
if(tree2==NULL)
{
tree1=NULL;
}//end if
else
{
tree1=new nodeType<Type>;
tree1->info=tree2->info;
copytree(tree1->llink,tree2->llink);
copytree(tree1->rlink,tree2->rlink);
}
}//end copytree
//**************************************************************
//*****************max******************************************
template<class Type>
int binarytree<Type>::max(int x,int y)
{
return(x>y?x:y);
}//enf max
//**************************************************************
//*****************nodenum**************************************
template<class Type>
int binarytree<Type>::_nodenum(nodeType<Type>*p)
{
int x=0;
if(p==NULL)
return x;
else
if(p->llink!=NUll||p->rlink!=NUll)x++;
_nodenum(p->llink);
_nodenum(p->rlink);
return x;
}//end nodenum
//**************************************************************
//***************** _leavenum***********************************
template<class Type>
int binarytree<Type>::_leavenum(nodeType<Type>*p)
{
int i=0;
if(p==NUll)return i;
else
if(p->llink==NUll&&p->rlink==NULL)i++;
_leavenum(p->llink);
_leavenum(p->rlink);
return i;
}//end _leavenum
//**************************************************************
//***************** operator =*********************************
template<class Type>
const binarytree<Type>&binarytree<Type>::operator =(const binarytree<Type>&tree1)
{
if(this!=&tree1)
{
if(root!=NULL)
_destroytree(root);
else
copytree(root,tree1.root);
}//end if
return this;
}//end operator =
//**************************************************************
//***************** inordertree()*******************************
template<class Type>
void binarytree<Type>::inordertree()
{
inorder(root);
}//end inorder
//**************************************************************
//*****************preordertree*********************************
template<class Type>
void binarytree<Type>::preordertree()
{
preorder(root);
}//end preordertree
//**************************************************************
//****************postordertree*********************************
template<class Type>
void binarytree<Type>::postordertree()
{
postorder(root);
}//end postordertree
//**************************************************************
//****************length ***************************************
template<class Type>
int binarytree<Type>::length()
{
_length(root);
}
//**************************************************************
//****************nodenum***************************************
template<class Type>
int binarytree<Type>::nodenum()
{
_nodenum(root);
}
//**************************************************************
//****************leavenum**************************************
template<class Type>
int binarytree<Type>::leavenum()
{
_leavenum(root);
}
//**************************************************************
//*************** isempty***************************************
template<class Type>
bool binarytree<Type>::isempty()
{
return(root==NULL);
}
//**************************************************************
//*************** binarytree(nodeType<Type>&)*******************
template<class Type>
binarytree<Type>::binarytree(nodeType<Type>&tree)
{
copytree(root,tree.root);
}
//**************************************************************
//***************destroytree************************************
template<class Type>
void binarytree<Type>::destroytree()
{
_destroytree(root);
}
//**************************************************************
//*************** binarytree()*********************************
template<class Type>
binarytree<Type>::binarytree()
{
root=NULL;
}
//**************************************************************
//***************~binarytree()**********************************
template<class Type>
binarytree<Type>::~binarytree()
{
_destroytree(root);
}
//**************************************************************
#endifTop

2 楼qhfu（改个名字）回复于 2005-06-03 12:12:17 得分 0

楼主的意思大概是输入中缀表达式，用中序遍历建立二叉树，就可以用前序便利产生前缀表达式，也可以用后序变量产生后缀表达式，呵呵Top

3 楼guyaguya（我只愿面朝大海，春暖花开）回复于 2005-06-03 12:42:34 得分 0

/**************************************************
* Essential C++ -- Stanley Lippman
* Addison-Wesley
* ISBN 0-201-48518-4
* homepage: www.objectwrite.com
* email: slippman@objectwrite.com
*************************************************/

#include <iostream>
#include <vector>
using namespace std;

template <typename elemType>
class BinaryTree;

template <typename elemType>
class BTnode;

/*
template <typename valType>
ostream&
foo( ostream &os, const BTnode<valType> &bt );*/

template <typename valType>
class BTnode {
friend class BinaryTree<valType>;
/*
friend ostream&
// foo<valType>( ostream&, const BTnode<valType>& );
foo( ostream&, const BTnode<valType>& );*/

public:
BTnode( const valType &val );

const valType& value() const { return _val; }
int occurs() const{ return _cnt; }

void remove_value( const valType&, BTnode*& );

void insert_value( const valType& );
bool find_value( const valType& ) const;

void preorder ( BTnode*, ostream& ) const;
void inorder ( BTnode*, ostream& ) const;
void postorder( BTnode*, ostream& ) const;

static void lchild_leaf( BTnode *leaf, BTnode *subtree );
private:
int _cnt; // occurrence count
valType _val;
BTnode *_lchild;
BTnode *_rchild;

void display_val( BTnode *pt, ostream &os ) const;
BTnode( const BTnode& );
BTnode& operator=( const BTnode& );
};

Top

4 楼guyaguya（我只愿面朝大海，春暖花开）回复于 2005-06-03 12:43:10 得分 0

template <typename valType>
inline
BTnode<valType>::
BTnode( const valType &val )
: _val( val )
{
_cnt = 1;
_lchild = _rchild = 0;
}

template <typename valType>
void
BTnode<valType>::
insert_value( const valType &val )
{
if ( val == _val )
{
_cnt++;

(*BinaryTree<valType>::os()) << "BTnode::insert_value: increment count( "
<< val << " : " << _cnt << " )\n";

return;
}

if ( val < _val ){
if ( ! _lchild ){
_lchild = new BTnode( val );
(*BinaryTree<valType>::os()) << "ok: BTnode::insert_value at left child( " << val << " )\n";
}
else _lchild->insert_value( val );
}
else {
if ( ! _rchild ){
_rchild = new BTnode( val );
(*BinaryTree<valType>::os()) << "ok: BTnode::insert_value at right child( " << val << " )\n";
}
else _rchild->insert_value( val );
}
}

template <typename valType>
bool
BTnode<valType>::
find_value( const valType &val ) const
{
if ( val == _val )
return true;

if ( val < _val ){
if ( ! _lchild )
return false;
else return _lchild->find_value( val );
}
else {
if ( ! _rchild )
return false;
else return _rchild->find_value( val );
}
}

template <typename valType>
void
BTnode<valType>::
lchild_leaf( BTnode *leaf, BTnode *subtree )
{
while ( subtree->_lchild )
subtree = subtree->_lchild;
subtree->_lchild = leaf;
}

template <typename valType>
void
BTnode<valType>::
remove_value( const valType &val, BTnode *&prev )
{
if ( val < _val )
{
if ( ! _lchild )
return; // not present
else _lchild->remove_value( val, _lchild );
}
else
if ( val > _val )
{
if ( ! _rchild )
return; // not present
else _rchild->remove_value( val, _rchild );
}
else
{ // ok: found it
// reset the tree then delete this node
if ( _rchild )
{
prev = _rchild;
if ( _lchild )
if ( ! prev->_lchild )
prev->_lchild = _lchild;
else BTnode<valType>::lchild_leaf( _lchild, prev->_lchild );
}
else prev = _lchild;
delete this;
}
}

template <typename valType>
inline void BTnode<valType>::
display_val( BTnode *pt, ostream &os ) const
{
os << pt->_val;
if ( pt->_cnt > 1 )
os << "( " << pt->_cnt << " ) ";
else os << ' ';
}

template <typename valType>
void BTnode<valType>::
preorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
display_val( pt, os );
if ( pt->_lchild ) preorder( pt->_lchild, os );
if ( pt->_rchild ) preorder( pt->_rchild, os );
}
}

template <typename valType>
void BTnode<valType>::
inorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
if ( pt->_lchild ) inorder( pt->_lchild, os );
display_val( pt, os );
if ( pt->_rchild ) inorder( pt->_rchild, os );
}
}

template <typename valType>
void BTnode<valType>::
postorder( BTnode *pt, ostream &os ) const
{
if ( pt )
{
if ( pt->_lchild ) postorder( pt->_lchild, os );
if ( pt->_rchild ) postorder( pt->_rchild, os );
display_val( pt, os );
}
}

template <typename elemType>
class BinaryTree {
public:
BinaryTree();
BinaryTree( const vector< elemType >& );
BinaryTree( const BinaryTree& );
~BinaryTree();
BinaryTree& operator=( const BinaryTree& );

void remove_root() ;
void insert( const vector< elemType >& );
void insert( const elemType& );
void remove( const elemType& );
void clear(){ clear( _root ); _root = 0; } // remove entire tree ...

bool empty() { return _root == 0; }

void inorder( ostream &os = *_current_os ) const { _root->inorder( _root, os ); }
void postorder( ostream &os = *_current_os ) const { _root->postorder( _root, os ); }
void preorder( ostream &os = *_current_os ) const { _root->preorder( _root, os ); }

bool find( const elemType& ) const;
ostream& print( ostream &os = *_current_os,
void (BinaryTree<elemType>::*traversal)( ostream& ) const =
&BinaryTree<elemType>::inorder ) const;

static void current_os( ostream *os ){ if ( os ) _current_os = os; }
static ostream* os() { return _current_os; }

private:
BTnode<elemType> *_root;
static ostream *_current_os;

// copy a subtree addressed by src to tar
void copy( BTnode<elemType>*&tar, BTnode<elemType>*src );
void clear( BTnode<elemType>* );
void removef_root();
};

template <typename elemType>
ostream *BinaryTree<elemType>::_current_os = &cout;

template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree()
: _root( 0 ){}

template <typename elemType>
inline
BinaryTree<elemType>::
BinaryTree( const BinaryTree &rhs )
{ copy( _root, rhs._root ); }

template <typename elemType>
inline
BinaryTree<elemType>::
~BinaryTree(){ clear(); }

template <typename elemType>
inline BinaryTree<elemType>&
BinaryTree<elemType>::
operator=( const BinaryTree &rhs )
{
if ( this != &rhs )
{
clear();
copy( _root, rhs._root );
}
}

template <typename elemType>
inline void
BinaryTree<elemType>::
insert( const elemType &elem )
{
if ( ! _root ){
(*BinaryTree<elemType>::os()) << "BinaryTree::insert: root( " << elem << " )\n";
_root = new BTnode<elemType>( elem );
}
else _root->insert_value( elem );
}

template <typename elemType>
BinaryTree<elemType>::
BinaryTree( const vector< elemType > &vec )
{
_root = 0;
for ( int ix = 0; ix < vec.size(); ++ix )
insert( vec[ ix ] );
}

template <typename elemType>
void
BinaryTree<elemType>::
insert( const vector< elemType > &vec )
{
for ( int ix = 0; ix < vec.size(); ++ix )
insert( vec[ ix ] );
}

template <typename elemType>
inline void
BinaryTree<elemType>::
remove( const elemType &elem )
{
if ( _root )
{
if ( _root->_val == elem )
remove_root();
else _root->remove_value( elem, _root );
}
}

Top

5 楼guyaguya（我只愿面朝大海，春暖花开）回复于 2005-06-03 12:43:23 得分 0

template <typename elemType>
void
BinaryTree<elemType>::
remove_root()
{
if ( ! _root ) return;
BTnode<elemType> *tmp = _root;

if ( _root->_rchild )
{
_root = _root->_rchild;
BTnode<elemType> *lc = tmp->_lchild;
BTnode<elemType> *newlc = _root->_lchild;

// if left child of root is non-null
// attach it as leaf to left subtree
if ( lc )
if ( ! newlc )
_root->_lchild = lc;
else BTnode<elemType>::lchild_leaf( lc, newlc );
}
else _root = _root->_lchild;

delete tmp;
}

template <typename elemType>
void
BinaryTree<elemType>::
clear( BTnode<elemType> *pt )
{
if ( pt ){
clear( pt->_lchild );
clear( pt->_rchild );
delete pt;
}
}

template <typename elemType>
ostream&
BinaryTree<elemType>::
print( ostream &os,
void (BinaryTree::*traversal)( ostream& ) const ) const
{
(this->*traversal)( os );
return os;
}

template <typename elemType>
inline ostream&
operator<<( ostream &os, const BinaryTree<elemType> &bt )
{
os << "Tree: " << endl;
bt.print( os, &BinaryTree<elemType>::inorder );
return os;
}

template <typename elemType>
inline bool
BinaryTree<elemType>::
find( const elemType &elem ) const
{
return ! _root
? false
: _root->find_value( elem );
}
template <typename elemType>
void
BinaryTree<elemType>::
copy( BTnode<elemType> *&tar, BTnode<elemType> *src )
{
if ( src ) {
tar = new BTnode<elemType>( src->_val );
if ( src->_lchild ) copy( tar->_lchild, src->_lchild );
if ( src->_rchild ) copy( tar->_rchild, src->_rchild );
}
}

#include <string>
#include <algorithm>
#include <fstream>
using namespace std;

main()
{
/*
BinaryTree< int > bt;

bt.insert( 7 );
bt.insert( 5 );
bt.insert( 9 );
bt.insert( 6 );
bt.insert( 3 );
*/

/*
BinaryTree< string > bt;
bt.insert( "Piglet" );
bt.insert( "Pooh" );
bt.insert( "Eeyore" );
bt.insert( "Kanga" );
bt.insert( "Tigger" );
*/

ofstream log( "logfile.txt" );
if ( ! log ){
cerr << "error: unable to open file!\n";
return -1;
}
else BinaryTree<string>::current_os( &log );

/*
int ia[] = { 24, 18, 36, 12, 14, 8, 24, 1, 42, 24, 8, 8, 16, 55 };
vector< int > ivec( ia, ia + 14 );
BinaryTree<int> bt( ivec );

log << "preorder traversal: \n";
// cout << should see\n\t ";
bt.preorder( log );

bt.clear();
log << "\nbt is now " << ( bt.empty() ? " empty! " : " oops -- not empty!" ) << endl;

sort( ivec.begin(), ivec.end() );
bt.insert( ivec );

log << "\n\ninorder traversal:\n";
bt.inorder( log );

bt.insert( ivec );

log << "\n\npostorder traversal:\n";
bt.postorder( log );

log << endl << endl;
*/

BinaryTree<string> bt;
bt.insert( "Piglet" );
bt.insert( "Eeyore" );
bt.insert( "Roo" );

bt.insert( "Tigger" );
bt.insert( "Chris" );
bt.insert( "Pooh" );
bt.insert( "Kanga" );

log << "preorder traversal: \n";
bt.preorder( log );

log << "\n\nabout to remove root: Piglet\n";
bt.remove( "Piglet" );

log << "\n\npreorder traversal after Piglet removal: \n";
bt.preorder( log );

log << "\n\nabout to remove Eeyore\n";
bt.remove( "Eeyore" );

log << "\n\npreorder traversal after Piglet removal: \n";
bt.preorder( log );

// log << "\n\ninorder traversal:\n";
// bt.inorder( log );

// log << "\n\npostorder traversal:\n";
// bt.postorder( log );
//
return 0;
}

呵呵，给个Stanley Lippman的代码看看

Top

6 楼6spring（6Spring）回复于 2005-06-03 13:25:26 得分 0

楼主都说了是要表达式建二叉树了说~~~

最简单的思路，扫描表达式字串，根据运算符优先级，栈式生成。（用2个栈，数据栈，运算符栈）
Top

7 楼hereisme（）回复于 2005-06-03 13:35:15 得分 0

用两个栈如何实现这就是我不会的~~Top

8 楼mostideal（三甲）回复于 2005-06-03 13:44:00 得分 0

mark!!Top

9 楼du51（郁郁思扬）回复于 2005-06-03 13:47:57 得分 0

///////////////////////////////Tree.h///////////////////////////////////////////////
#ifndef _TREE_H_
#define _TREE_H_ //防止反复包含

#include<iostream>
#include<string>
#include<math.h>
#include<sstream>
using namespace std;
////////////////////////////////////////////////////////////////////////

bool IsOperator(string mystring) //验证操作符
{
if(mystring=="-"||mystring=="+"||mystring=="/"||mystring=="*"||mystring=="^")
return(true);
else
return(false);
}
bool IsOperator(char ops)//重载
{
if(ops=='+'||ops=='-'||ops=='*'||ops=='/'||ops=='^'||ops=='('||ops==')')
return(true);
else
return(false);
}
/////////////////////////////////////////////////////////////
class node_type//结点类
{
public:
string data;
node_type *left_child;
node_type *right_child;
node_type(string k)
{
data=k;
left_child=NULL;
right_child=NULL;
}
};
///////////////////////////////////////////////////////////////////
class binary_tree //二叉树类开始
{
public:
node_type *root;
void print(node_type *r);
binary_tree(void){root=NULL;}
void inprint(node_type *p)
{
if(p!=NULL)
{

inprint(p->left_child);
cout<<p->data<<" ";
inprint(p->right_child);
}
}
void deprint(node_type *p)
{
if(p!=NULL)
{

deprint(p->right_child);
cout<<p->data<<" ";
deprint(p->left_child);
}
}
void print(void){print(root);}
void inprint(void){print(root);}
void evaluate()
{
evaluate(root);
}
void evaluate(node_type *prt)
{
if(IsOperator(prt->data)&&!IsOperator(prt->left_child->data)&&!IsOperator(prt->right_child->data))
{
int num=0;
int num1=atoi(prt->left_child->data.c_str()); //C类型的字符串常量不可改变
int num2=atoi(prt->right_child->data.c_str()); //同上
if(prt->data=="+")
num=num1+num2;
else if(prt->data=="-")
num=num1-num2;
else if(prt->data=="*")
num=num1*num2;
else if(prt->data=="/")
num=num1/num2;
else if(prt->data=="^")
num=pow(num1,num2);
cout<<num<<'\t'; //打印中间结果
stringstream bob;
bob<<num;
string suzzy(bob.str());
prt->data=suzzy;
prt->left_child=NULL;
prt->right_child=NULL;

}
else if(prt->left_child==NULL&&prt->right_child==NULL);
else
{
evaluate(prt->left_child);
evaluate(prt->right_child);
evaluate(prt);
}
}
void clear_help(node_type *rt) //删除者
{
if(rt!=NULL)
{
clear_help(rt->left_child);
clear_help(rt->right_child);
delete rt;
}
}
void clear() //删除整个二叉树。
{
clear_help(root);
}
/////////////////////////////////////////////
void count_help(node_type *rt,int &a) //计数者//引用可以带回改变值。
{
a=0;
int f1,f2;
if(rt!=NULL)
{
count_help(rt->left_child,f1);
count_help(rt->right_child,f2);
a=f1+f2+1;
}
}
int counter() //返回结点的个数
{
int a;
count_help(root,a);
return a;
}
bool compare(string str1,string str2) //比较两结点的大小。若str1大于str2返回TRUE。否则为FALSE。
{
int i=0;
while(str1[i]&&str2[i])
{
if((int)str1[i]>(int)str2[i])
return true;
else if((int)str1[i]<(int)str2[i])
return false;
else i++;
}
if(str1[i])return true;
else return false;
}
/////////////////////////////////////////////////////////////////////////////////////////
void inserter(node_type *&p,string data) //插入者。
{
if(p==NULL)
{
p=new node_type(data);
p->left_child=NULL;
p->right_child=NULL;
}
else if(compare(p->data,data))
inserter(p->left_child,data);
else inserter(p->right_child,data);
}

void found(node_type *&p,node_type *&p1) //对一个树排序，并建新树。依靠插入者。
{
if(p!=NULL)
{
found(p->left_child,p1);
found(p->right_child,p1);
inserter(p1,p->data);
}
}
binary_tree order(binary_tree aa) //排序的函数
{
binary_tree bb;
found(aa.root,bb.root);
return bb;
}
binary_tree order()
{
return order(*this);
}
}; //二叉树类结束。

node_type *build_node(string x) //建立一个结点
{
node_type *new_node;
new_node=new node_type(x);
return(new_node);
}
void binary_tree::print(node_type *p)//打印
{
if(p!=NULL)
{
print(p->left_child);
print(p->right_child);
cout<<p->data<<" ";
}
}
bool IsOperand(char ch)//验证数据
{
if((ch>='0')&&(ch<='9'))
return true;
else
return false;
}
/////////////////////////////////////////////////////////////////////////
bool addition(char OperatorA,char OperatorB) //A=B返回TRUE.
{
if(OperatorA==OperatorB||(OperatorA=='*'&&OperatorB=='/')||(OperatorA=='/'&&OperatorB=='*')||(OperatorA=='+'&&OperatorB=='-')||(OperatorA=='-'&&OperatorB=='+'))
return true;
else return false;
}

bool TakesPrecedence(char OperatorA,char OperatorB) //判别符号的优先级。A>B，返回为TRUE。
{
if(OperatorA=='(')
return false;
else if(OperatorB=='(')
return false;
else if(OperatorB==')')
return true;
else if(addition(OperatorA,OperatorB)) //本函数原有逻辑错误.此处加以修正
return false;
else if(OperatorA=='^')
return true;
else if(OperatorB=='^')
return false;
else if((OperatorA=='*')||(OperatorA=='/'))
return true;
else if((OperatorB=='*')||(OperatorB=='/'))
return false;
else if((OperatorA=='+')||(OperatorA=='-'))
return true;
else return false;
}
////////////////////////////////////////////////////////////////
void copy(node_type *&r1,node_type *r2) //挎贝整个二叉树
{
if(r2==NULL)
r1=NULL;
else
{
r1=build_node(r2->data);
copy(r1->left_child,r2->left_child);
copy(r1->right_child,r2->right_child);
}
}
#endif //条件编绎结束
Top

10 楼du51（郁郁思扬）回复于 2005-06-03 13:48:22 得分 40

//////////////////////////////////////////main.cpp///////////////////////////////////
#include<iostream>
#include<string>
#include<stack>
#include "Tree.h"
//////////////////////Checks if expression if ok////////////////
bool isok(string exp) //此函数验证式子是否正确，即是否符合运算规则。
{
char check;
int error=0;
int lb=0;
int rb=0;
if(exp.size()==1)return false;
else if((IsOperator(exp[0])||IsOperator(exp[exp.size()-1]))&&exp[0]!='('&&exp[exp.size()-1]!=')') //此处若不加，在遇到某些式子时，会出现非法操作。
return false;
for(int m=0;m<exp.size();m++)
{
check=exp[m];
if(IsOperand(check)); //如果是数字，跳过，不管。
else if(IsOperator(check))
{
if(check==')')
{
rb++;
if(IsOperator(exp[m+1])&&(exp[m+1]=='+'||exp[m+1]=='-'||exp[m+1]=='*'||exp[m+1]=='/'||exp[m+1]=='^'||exp[m+1]==')'))
{
m++;
if(exp[m]==')')
rb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
else if(check=='(')
{
lb++;
if(exp[m+1]=='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
else
{
if(IsOperator(exp[m+1])&&exp[m+1]=='(')
{
m++;
lb++;
}
else if(IsOperator(exp[m+1]))
error++;
}
}
else
error++;
}
if(error==0&&lb==rb)
return(true);
else
return(false);
}
////////////////////////////////////////////////////////////////////
int main() //主函数开始
{
binary_tree etree;
stack<binary_tree>NodeStack;
stack<char>OpStack;
string infix;
char choice='y';
char c;

while(choice=='y'||choice=='Y')
{
cout<<"\n\n请输入表达式，不要带空格;\n";
cin>>infix;
cout<<"--------------------------------------------------------------------------------"<<'\n';
cout<<"表达式为: "<<infix<<'\n';

if(isok(infix))
{
for(int i=0;i<infix.size();i++)
{
c=infix[i];
if(IsOperand(c))
{
string tempstring;
tempstring=tempstring+c;
while(i+1<infix.size()&&IsOperand(infix[i+1]))
{
tempstring=tempstring+infix[++i];
}
binary_tree temp;
temp.root=build_node(tempstring);
NodeStack.push(temp);
}
////////////////////////////////////////////////
else if(c=='+'||c=='-'||c=='*'||c=='/'||c=='^')
{
if(OpStack.empty())
OpStack.push(c);
else if(OpStack.top()=='(')
OpStack.push(c);
else if(TakesPrecedence(c,OpStack.top()))
OpStack.push(c);
else
{
while(!OpStack.empty()&&(TakesPrecedence(OpStack.top(),c)||addition(OpStack.top(),c)))
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
etree.root=NULL;
}
OpStack.push(c);
}

}
else if(c=='(')
OpStack.push(c);
else if(c==')')
{
while(OpStack.top()!='(')
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
etree.root=NULL;
}
OpStack.pop();
}
}
////////////////////////////////////////////////////////
while(!OpStack.empty())
{
binary_tree temp_tree;
string thisstring="";
thisstring=thisstring+OpStack.top();
OpStack.pop();
etree.root=build_node(thisstring);
copy(temp_tree.root,NodeStack.top().root);
NodeStack.pop();
etree.root->right_child=temp_tree.root;
temp_tree.root=NULL;
copy(temp_tree.root,NodeStack.top().root);
etree.root->left_child=temp_tree.root;
NodeStack.pop();
temp_tree.root=NULL;
copy(temp_tree.root,etree.root);
NodeStack.push(temp_tree);
if(!OpStack.empty())
{
etree.root=NULL;
}
}
cout<<"打印结点如下: ";
etree.print();
binary_tree temp;
copy(temp.root,etree.root);
cout<<'\n';
cout<<"结点个数为："<<etree.counter()<<'\n';
cout<<"以下是，中间的计算结果："<<'\n';
etree.evaluate();
cout<<'\n';
cout<<"结果是: ";
cout<<etree.root->data<<'\n';
cout<<"--------------------------------------------------------------------------------"<<'\n';
cout<<"是不要进行二叉树排序，并显示？若是升序点A，若是降序点B,若不是点C"<<'\n';
char c1;
cin>>c1;
if(c1=='A'||c1=='a')
{
binary_tree temp1;
copy(temp1.root,temp.order().root); //此处代码无需再改
temp1.inprint(temp1.root);//前边程序有错,此处TEMP1为空.所以没有输出.
}
else if(c1=='B'||c1=='b')
{
binary_tree temp1;
copy(temp1.root,temp.order().root);
temp1.deprint(temp1.root);
}

cout<<"\n\nRun Program again?Enter<y/n>:";
cin>>choice;
}
else
{
cout<<"************************************************"<<'\n';
cout<<"ERROR:Invalid Expression"<<'\n';
cout<<"************************************************"<<'\n';
cout<<"\n\nRun Program again?Enter<y/n>:";
cin>>choice;
}
}
return 0;
}
//环境VC6.0
Top

11 楼hereisme（）回复于 2005-06-05 10:50:38 得分 0

我想变到MFC下面用树控件显示二叉树,如何变动?Top

12 楼naturemickey（米老鼠）回复于 2005-06-05 11:02:24 得分 0

#ifndef _BinTree_H_
#define _BinTree_H_

namespace Mickey
{

template <class T>
struct BinTreeNode
{
T _data;
BinTreeNode* _left;
BinTreeNode* _right;
BinTreeNode(T data) : _left(NULL), _right(NULL), _data(data)
{}
};

template <class T>
class BinTree
{
int d_size;
BinTreeNode<T>* d_pRoot;
BinTreeNode<T>* d_pFirst;
BinTreeNode<T>* d_pEnd;
void DelSubtree(BinTreeNode<T>* current)
{
if(current != NULL)
{
DelSubtree(current -> _left);
DelSubtree(current -> _right);
delete current;
}
}
void out(BinTreeNode<T>*) const;
void insert(T, BinTreeNode<T>*&);
void CreatTree(std::string, std::string, BinTreeNode<T>*&);
public:
BinTree(int = 0) : d_pRoot(NULL), d_pFirst(NULL), d_pEnd(NULL), d_size(0)
{}
~BinTree(){ clear(); }

int size() const
{ return d_size; }

bool empty() const
{ return d_size == 0; }

BinTreeNode<T>* begin() const
{ return d_pFirst; }

BinTreeNode<T>* end() const
{ return d_pEnd; }

void clear();

void CreatTree(std::string, std::string);//输入先根和中根

void insert(T item)/*输入可比较大小的数据，建二叉检索树*/
{ insert(item, d_pRoot); }

void print() const;

};

template <class T>
void BinTree<T>::CreatTree(std::string Pre, std::string In, BinTreeNode<T>*& pNode)
{
pNode = new BinTreeNode<T>(Pre[0]);
std::string::iterator posPre = Pre.begin();
std::string::iterator posIn = std::find(In.begin(), In.end(), Pre[0]);
posPre += (posIn - In.begin() + 1);
if(posIn != In.begin())
CreatTree(std::string(Pre.begin() + 1, posPre), std::string(In.begin(), posIn - 1), pNode->_left);
if(posIn != In.end())
CreatTree(std::string(posPre, Pre.end()), std::string(posIn + 1, In.end()), pNode->_right);
}

template <class T>
void BinTree<T>::CreatTree(std::string Pre, std::string In)
{
CreatTree(Pre, In, d_pRoot);
}

template <class T>
void BinTree<T>::insert(T item, BinTreeNode<T>*& pNode)
{
if(pNode == NULL)
{
pNode = new BinTreeNode<T>(item);
++d_size;
}
else
{
if(item < pNode -> _data) insert(item, pNode -> _left);
else if(item > pNode -> _data) insert(item, pNode -> _right);
}
}

template <class T>
void BinTree<T>::print() const
{
out(d_pRoot);
std::cout << std::endl;
}

template <class T>
void BinTree<T>::out(BinTreeNode<T>* pNode) const
{
if(pNode != NULL)
{
out(pNode -> _left);
std::cout << pNode -> _data << ' ';
out(pNode -> _right);
}
}

template <class T>
void BinTree<T>::clear()
{
DelSubtree(d_pRoot);
}

}

#endif
Top

13 楼hereisme（）回复于 2005-06-05 11:18:10 得分 0

如何在treectrl显示这个二叉树呢?Top

14 楼typ9718（死灰不然）回复于 2005-06-05 11:40:31 得分 10

楼上的你们的程序是不是长了些啊？看我的用C写的只不过是用广义表的形式实现是非递归的算法
使用一个栈保存当前2叉树的根结点，top为其栈指针，k指定其后处理的结点是双亲结点还是左孩子（k=1）或者右孩子（k=2），ch为当前处理的str中的字符。若ch=‘（’（左括号）则将创建的结点作为双亲结点进栈，并设置k=1，其后创建的结点为左孩子；若ch=‘）’（右括号），表示坐结点处理完毕，退栈；若ch=‘，’，表示其后创建的结点为右孩子；其他情况，表示要创建一个结点，并根据k的值建立他与栈中结点的关系。如此循环到str处理完毕。
void creatree(BTree *&b,char *str)
{ BT *stack[maxsize},*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
ch=str[j];
while(ch!='\0')
{ switch(ch)
{ case '(':top++;stack[top]=p;k=1;break;
case')': top--;break;
case',':k=2;break;
default:p=(BTree *)malloc(sizeof(BTree));
p->data=ch;p->lchild=p->rchild=NULL;
if(b==NULL)
B=P;
else
{ switch(k)
{case 1:stack[top]->lchild=p;break;
case 2:stack[top]->rchild=p;break;
}
}

j++;
ch=str[j];
}
}
二叉树的结点类型我在这就不定义了吧
哈哈　给分吧！！Top

15 楼littlelongboy（）回复于 2005-06-05 11:48:44 得分 0

不明白什么意思
Top

16 楼hereisme（）回复于 2005-06-05 13:05:06 得分 0

typ9718(死灰不然)的算法好像有点问题,怎么没有+,-*/之类的算先级考虑,还有那个B=P中的B是什么类型?Top

17 楼zhousqy（标准C匪徒)(甩拉，甩拉）回复于 2005-06-05 14:04:00 得分 0

顶。Top

18 楼zdy_8212（zdy_8212）回复于 2005-06-05 17:58:53 得分 0

MARKTop

19 楼hereisme（）回复于 2005-06-05 20:12:20 得分 0

代码如何移植到MFC树控件,当然,我知道用先序,但这个二叉树如何建起来,上面建得都有问题~Top

20 楼typ9718（死灰不然）回复于 2005-06-06 12:15:04 得分 50

回楼主：
我的程序是利用广义表建立二叉树
树的样子由你输入字符的顺序决定
你可以将你的表达式转换成广义表在运行这个程序
至于那个“B=P中的B”是个拼写错误　应该是b=p才对　－＿－！！（不好意思是我太粗心了）Top