Êý¾Ý½á¹¹¼¯ÖÐÉÏ»ú

ÊÔÑ鱨¸æ

ѧԺ£º ¼ÆËã»ú¿ÆѧÓë¼¼Êõ רҵ£º¼ÆËã»ú¿ÆѧÓë¼¼Êõ

ѧºÅ£º °à¼¶£º ÐÕÃû£º

2010/11/26

ÌâÄ¿£º¶þ²æÊ÷µÄ´´½¨Óë±éÀú

Ò»¡¢ÊµÑéÄ¿µÄ

1£®Ñ§»áʵÏÖ¶þ²æÊ÷½áµã½á¹¹ºÍ¶Ô¶þ²æÊ÷µÄ»ù±¾²Ù×÷¡£

2£®ÕÆÎÕ¶Ô¶þ²æÊ÷ÿÖÖ²Ù×÷µÄ¾ßÌåʵÏÖ£¬Ñ§»áÀûÓõݹéºÍ·ÇµÝ¹é·½·¨±àд¶Ô¶þ²æÊ÷ÕâÖֵݹéÊý¾Ý½á¹¹½øÐд¦ÀíµÄËã·¨¡£

¶þ¡¢ÊµÑéÒªÇó

1£®ÈÏÕæÔĶÁºÍÕÆÎպͱ¾ÊµÑéÏà¹ØµÄ½Ì²ÄÄÚÈÝ¡£

2£®±àдÍêÕû³ÌÐòÍê³ÉÏÂÃæµÄʵÑéÄÚÈݲ¢ÉÏ»úÔËÐС£

3£®ÕûÀí²¢ÉϽ»ÊµÑ鱨¸æ¡£

Èý¡¢ÊµÑéÄÚÈÝ

1£®±àд³ÌÐòÈÎÒâÊäÈë¶þ²æÊ÷µÄ½áµã¸öÊýºÍ½áµãÖµ£¬¹¹ÔìÒ»¿Ã¶þ²æÊ÷£¬²ÉÓÃÈýÖֵݹéºÍ·ÇµÝ¹é±éÀúËã·¨(Ç°Ðò¡¢ÖÐÐò¡¢ºóÐò)¶ÔÕâ¿Ã¶þ²æÊ÷½øÐбéÀú¡£

ËÄ¡¢ÊµÑé²½Öè

Ô´³ÌÐò´úÂë

#include

#include

using namespace std;

template

struct BinTreeNode //¶þ²æÊ÷½áµãÀඨÒå

{

T data; //Êý¾ÝÓò

BinTreeNode *leftChild,*rightChild; //×ó×ÓÅ®¡¢ÓÒ×ÓÅ®Óò

BinTreeNode(T x=T(),BinTreeNode* l =NULL,BinTreeNode* r = NULL )

:data(x),leftChild(l),rightChild(r){} //¿ÉÑ¡Ôñ²ÎÊýµÄĬÈϹ¹Ô캯Êý

};

//-------------------------------------------------------------------------

template

void PreOrder_2(BinTreeNode *p) //·ÇµÝ¹éÇ°Ðò±éÀú

{

stack * > S;

while(p!=NULL || !S.empty())

{

while(p!=NULL)

{

cout<data; //·ÃÎʸù½áµã

S.push(p);

p=p->leftChild; //±éÀúÖ¸Õë½øµ½×ó×ÓÅ®½áµã

}

if(!S.empty()) //Õ»²»¿ÕʱÍËÕ»

{

p=S.top();

S.pop();

p = p->rightChild; //±éÀúÖ¸Õë½øµ½ÓÒ×ÓÅ®½áµã

}

}

}

//----------------------------------------------------------------

template

void InOrder_2(BinTreeNode *p) //·ÇµÝ¹éÖÐÐò±éÀú

{

stack* > S;

do

{

while(p!=NULL) //±éÀúÖ¸Õëδµ½×î×óϵĽáµã£¬²»¿Õ

{

S.push(p);

p=p->leftChild;

}

if(!S.empty()) //Õ»²»¿ÕʱÍËÕ»

{

p=S.top();

S.pop();

cout<data;

p=p->rightChild;

}

}

while(p !=NULL || !S.empty());

}

//------------------------------------------------------------------

template

void PostOrder_2(BinTreeNode *p) //·ÇµÝ¹éºóÐò±éÀú

{

stack * > S;

stack tag;//¶¨ÒåÒ»¸öеÄÕ»ÓÃÀ´±£´ætagÓòÅбð¸ù½áµãµÄ×óÓÒ×ÓÊ÷ÊÇ·ñ¾ù±éÀú¹ý

while(p != NULL || !S.empty()) //×ó×ÓÊ÷¾­¹ý½áµã¼ÓL½øÕ»

{

while(p!=NULL)

{

S.push(p); //Ê×ÏȽ«tºÍtagΪ0ÈëÕ»£¬±éÀú×ó×ÓÊ÷

tag.push(0);//±éÀú×ó×ÓÊ÷Ç°µÄÏÖ³¡±£»¤

p=p->leftChild;

}

while( !S.empty() && tag.top()==1)

{

p=S.top();

S.pop();

tag.pop();

cout<data; //×îºó·ÃÎʸù½áµã¡£

}

if( !S.empty())

{

tag.pop();

tag.push(1);//±éÀúÓÒ×ÓÊ÷Ç°µÄÏÖ³¡±£»¤,ÐÞ¸ÄÕ»¶¥tagΪ1£¬±éÀúÓÒ×ÓÊ÷

p=S.top(); // È¡Õ»¶¥±£´æµÄÖ¸Õë

p=p->rightChild;

}

else

break;

}

}

//--------------------------------------------------------------------

template

void InOrder_1(BinTreeNode * subTree)

{//µÝ¹éº¯Êý£ºÖÐÐò´ÎÐò±éÀúÒÔsubTreeΪ¸ùµÄ×ÓÊ÷¡£

if(subTree !=NULL) //NULLÊǵݹéÖÕÖ¹Ìõ¼þ

{

InOrder_1(subTree->leftChild); //ÖÐÐò±éÀú¸ùµÄ×ó×ÓÊ÷

cout<data; //·ÃÎʸù½áµã

InOrder_1(subTree->rightChild); //ÖÐÐò±éÀú¸ùµÄÓÒ×ÓÊ÷

}

}

//--------------------------------------------------------------------------

template

void PreOrder_1(BinTreeNode * subTree)

{//µÝ¹éº¯Êý£ºÇ°Ðò±éÀúÒÔsubTreeΪ¸ùµÄ¶þ²æÊ÷¡£

if(subTree !=NULL) //µÝ¹é½áÊøÌõ¼þ

{

cout<data;//·ÃÎʸù½áµã

PreOrder_1(subTree->leftChild); //Ç°Ðò±éÀú¸ùµÄ×ó×ÓÊ÷

PreOrder_1(subTree->rightChild); //Ç°Ðò±éÀú¸ùµÄÓÒ×ÓÊ÷

}

}

//---------------------------------------------------------------------------

template

void PostOrder_1(BinTreeNode * subTree)

{//µÝ¹éº¯Êý£ººóÐò´ÎÐò±éÀúÒÔsubTreeΪ¸ùµÄ×ÓÊ÷¡£

if(subTree !=NULL) //NULLÊǵݹéÖÕÖ¹Ìõ¼þ

{

PostOrder_1(subTree->leftChild); //ºóÐò±éÀú¸ùµÄ×ó×ÓÊ÷

PostOrder_1(subTree->rightChild); //ºóÐò±éÀú¸ùµÄÓÒ×ÓÊ÷

cout<data; //·ÃÎʸù½áµã

}

}

//--------------------------------------------------------------------------

template

void CreateBinTree(BinTreeNode * & subTree)

{//µÝ¹é·½Ê½½¨Á¢¶þ²æÊ÷

T item;

cin>>item;

if(item !=-1)

{

subTree = new BinTreeNode();

if(subTree == NULL)

{

cerr<<"´æ´¢·ÖÅä´í£¡"<

exit(1);

}

subTree->data = item;

CreateBinTree(subTree->leftChild); //µÝ¹é½¨Á¢×ó×ÓÊ÷

CreateBinTree(subTree->rightChild); //µÝ¹é½¨Á¢ÓÒ×ÓÊ÷

}

else subTree = NULL; //·â±ÕÖ¸Ïò¿Õ×ÓÊ÷µÄÖ¸Õë

}

int main()

{

BinTreeNode * Tree = NULL;

cout<<"ÇëÊäÈëÿ¸ö½áµã£¬»Ø³µÈ·ÈÏ£¬²¢ÒÔ-1½áÊø£º";

CreateBinTree(Tree);

cout<<"ÏÈÐò±éÀú¶þ²æÊ÷½á¹û£º";

PreOrder_1(Tree);

cout<

cout<<"ÖÐÐò±éÀú¶þ²æÊ÷½á¹û£º";

InOrder_1(Tree);

cout<

cout<<"ºóÐò±éÀú¶þ²æÊ÷½á¹û£º";

PostOrder_1(Tree);

cout<

cout<<"·ÇµÝ¹éÇ°Ðò±éÀú¶þ²æÊ÷½á¹û£º";

PreOrder_2(Tree);

cout<

cout<<"·ÇµÝ¹éÖÐÐò±éÀú¶þ²æÊ÷½á¹û£º";

InOrder_2(Tree);

cout<

cout<<"·ÇµÝ¹éºóÐò±éÀú¶þ²æÊ÷½á¹û£º";

PostOrder_2(Tree);

cout<

return 1;

}

µÚ¶þƪ£º¶þ²æÊ÷±éÀú ʵÑ鱨¸æ

Êý¾Ý½á¹¹ÊµÑ鱨¸æ

±¨¸æÌâÄ¿£º¶þ²æÊ÷µÄ»ù±¾²Ù×÷

ѧÉú°à¼¶£º

ѧÉúÐÕÃû£ºÑ§ºÅ£º

Ò»£®ÊµÑéÄ¿µÄ

1¡¢ »ù±¾ÒªÇó£ºÉî¿ÌÀí½â¶þ²æÊ÷ÐÔÖʺ͸÷ÖÖ´æ´¢½á¹¹µÄÌص㼰ÊÊÓ÷¶Î§£»ÕÆÎÕÓÃÖ¸ÕëÀàÐÍÃèÊö¡¢·ÃÎʺʹ¦Àí¶þ²æÊ÷µÄÔËË㣻ÊìÁ·ÕÆÎÕ¶þ²æÊ÷µÄ±éÀúËã·¨£»¡£

2¡¢ ½Ï¸ßÒªÇó: ÔÚ±éÀúËã·¨µÄ»ù´¡ÉÏÉè¼Æ¶þ²æÊ÷¸ü¸´ÔÓ²Ù×÷Ëã·¨£»ÈÏʶ¹þ·òÂüÊ÷¡¢¹þ·òÂü±àÂëµÄ×÷ÓúÍÒâÒå;ÕÆÎÕÊ÷ÓëÉ­ÁֵĴ洢Óë±ãÀû¡£

¶þ. ʵÑéѧʱ£º

¿ÎÄÚʵÑéѧʱ£º3ѧʱ

¿ÎÍâʵÑéѧʱ£º6ѧʱ

Èý£®ÊµÑéÌâÄ¿

1£® ÒÔ¶þ²æÁ´±íΪ´æ´¢½á¹¹£¬ÊµÏÖ¶þ²æÊ÷µÄ´´½¨¡¢±éÀú£¨ÊµÑéÀàÐÍ£ºÑéÖ¤ÐÍ£©

1£©ÎÊÌâÃèÊö£ºÔÚÖ÷³ÌÐòÖÐÉè¼ÆÒ»¸ö¼òµ¥µÄ²Ëµ¥£¬·Ö±ðµ÷ÓÃÏàÓ¦µÄº¯Êý¹¦ÄÜ£º

1¡­½¨Á¢Ê÷

2¡­Ç°Ðò±éÀúÊ÷

3¡­ÖÐÐò±éÀúÊ÷

4¡­ºóÐò±éÀúÊ÷

5¡­Çó¶þ²æÊ÷µÄ¸ß¶È

6¡­Çó¶þ²æÊ÷µÄÒ¶×Ó½Úµã

7¡­·ÇµÝ¹éÖÐÐò±éÀúÊ÷

0¡­½áÊø

2£©ÊµÑéÒªÇó£ºÔÚ³ÌÐòÖж¨ÒåÏÂÊöº¯Êý£¬²¢ÊµÏÖÒªÇóµÄº¯Êý¹¦ÄÜ£º

CreateBinTree(BinTree &T): °´´Ó¼üÅÌÊäÈëµÄÇ°ÐòÐòÁУ¬´´½¨Ê÷

Preorder(BinTree &T)£ºÇ°Ðò±éÀúÊ÷£¨µÝ¹é£©

Inorder(BinTree &T)£ºÖÐÐò(µÝ¹é)±éÀúÊ÷

Postorder(BinTree &T): ºóÐò±éÀúÊ÷£¨µÝ¹é£©

PostTreeDepth(BinTree &T)£ºÊ÷µÄ¸ß¶È

leaf(BinTree &T):Ê÷µÄÒ¶×Ó½Úµã

InorderN(BinTree &T)£ºÖÐÐò(·ÇµÝ¹é)±éÀúÊ÷

3)Êý¾Ý½á¹¹

² ¶þ²æÁ´±í´æ´¢Êý¾ÝÀàÐͶ¨Òå

typedef struct node{

TElemType data;

struct node *lchild,*rchild;

}BinTNode;

ÔªËØÀàÐÍ£º

int CreateBinTree(BinTree &T);

void Preorder(BinTree &T);

void Inorder(BinTree &T);

void Postorder(BinTree &T);

void InorderN(BinTree &T);

int PostTreeDepth(BinTree &T);

int leaf(BinTree &T);

2¡¢±àдË㷨ʵÏÖ¶þ²æÊ÷µÄ·ÇµÝ¹éÖÐÐò±éÀúºÍÇó¶þ²æÊ÷¸ß¶È¡£

1£©ÎÊÌâÃèÊö£ºÊµÏÖ¶þ²æÊ÷µÄ·ÇµÝ¹éÖÐÐò±éÀúºÍÇó¶þ²æÊ÷¸ß¶È

2£©ÊµÑéÒªÇó£ºÒÔ¶þ²æÁ´±í×÷Ϊ´æ´¢½á¹¹

3) ʵÏÖ¹ý³Ì£º

1¡¢ÊµÏַǵݹéÖÐÐò±éÀú´úÂ룺

void CBiTree::InorderN(BinTree &T)

{

BinTree stack[MAX],p;

int top=0;p=T;

do

{

while(p!=NULL)

{

stack[top]=p;;

top=top+1;

p=p->lchild;

};

if(top>0)

{

top=top-1;

p=stack[top];

printf("%3c",p->data );

p=p->rchild;

}

}

while(p!=NULL||top!=0);

}

2¡¢Çó¶þ²æÊ÷¸ß¶È£º

int CBiTree::PostTreeDepth(BinTree &T)

{

int l,r,max;

if(T!=NULL)

{

l=PostTreeDepth(T->lchild );

r=PostTreeDepth(T->rchild );

max=l>r?l:r;

return(max+1);

}

else return(0);

}

ʵÑé²½Ö裺

1£© н¨Ò»¸ö»ùÓÚConsole ApplicationµÄ¹¤³Ì£¬¹¤³ÌÃû³ÆBiTreeTest£»

2£© н¨Ò»¸öÀàCBiTree¶þ²æÊ÷Àà¡£

3£© ÔÚÀàCBiTreeµÄÍ·ÎļþÉÏ·½¶¨Òå¶þ²æÁ´±í´æ´¢Êý¾ÝÀàÐͽṹÌåBiTNode¡£

4£© ÔÚÀàCBiTreeÖж¨Ò庯ÊýCreateBinTree£¨£©£»Preorder()£»Inorder()£»Postorder();PostTreeDepth();InorderN()£»

5£© ʵÏÖº¯ÊýCreateBinTree£¨£©£»Preorder()£»Inorder()£»Postorder();PostTreeDepth();InorderN()£»

6£© ÔÚÖ÷º¯ÊýÖж¨Òå¶ÔÏó£¬Í¨¹ý¶ÔÏóµ÷Óú¯Êý£¬ÊµÏÖ¸÷¸öº¯ÊýµÄ²Ù×÷¡£

ÔËÐнá¹û£º