May 1, 2009

資料結構作業五之四:Universal PreOrder Binary Tree

#include <iostream.h>
#include <stdlib.h>

typedef struct TreeNode
{
 char Data;
 struct TreeNode *LChild, *RChild;
}TreeNode;

typedef  TreeNode *TreePtr;

void PUSH(TreePtr node);
TreePtr POP(void);

void TreeLink (TreePtr Head, TreePtr Left, TreePtr Right);
int Universal_PreOrder(TreePtr Root);

int gSP = 0;
int gLimit = 99;
TreePtr Stack[100];


void main(void)
{
 TreePtr BinaryTree_Ex1[6];
 char Data_Ex1[6] = {'R', 'A', 'B', 'C', 'D', 'E'};

 TreePtr BinaryTree_Ex2[10];
 char Data_Ex2[10] = {'R', 'A', 'B', 'D', 'C', 'E', 'F', 'G', 'H', 'I'};

 int i;

//=========================================
 for(i=0; i < 6 ; i++)
 {
  BinaryTree_Ex1[i] = (TreePtr) malloc(sizeof(TreeNode));
  BinaryTree_Ex1[i]->Data = Data_Ex1[i];
  BinaryTree_Ex1[i]->LChild = NULL;
  BinaryTree_Ex1[i]->RChild = NULL;
 }
 TreeLink(BinaryTree_Ex1[0], BinaryTree_Ex1[1], NULL);
 TreeLink(BinaryTree_Ex1[1], BinaryTree_Ex1[2], BinaryTree_Ex1[3]);
 TreeLink(BinaryTree_Ex1[2], BinaryTree_Ex1[4], BinaryTree_Ex1[5]);

 cout << "Universal PreOrder Binary Tree, EX1"   << endl;
 cout << "=====================================" << endl;

 cout << "Step 1)" << endl;
 cout << "     Root" << endl;
 cout << "      /" << endl;
 cout << "     A" << endl;
 cout << "    /\\   " << endl;
 cout << "    B C" << endl;
 cout << "   /\\"  << endl;
 cout << "  D E"  << endl << endl;
 
 cout << "Step 2) ";
 Universal_PreOrder(BinaryTree_Ex1[0]);
 cout << endl;
 cout << endl;
//=========================================
 for(i=0; i < 10 ; i++)
 {
  BinaryTree_Ex2[i] = (TreePtr) malloc(sizeof(TreeNode));
  BinaryTree_Ex2[i]->Data = Data_Ex2[i];
  BinaryTree_Ex2[i]->LChild = NULL;
  BinaryTree_Ex2[i]->RChild = NULL;
 }
 TreeLink(BinaryTree_Ex2[0], BinaryTree_Ex2[1], NULL);
 TreeLink(BinaryTree_Ex2[1], BinaryTree_Ex2[2], BinaryTree_Ex2[3]);
 TreeLink(BinaryTree_Ex2[2], BinaryTree_Ex2[4], NULL);
 TreeLink(BinaryTree_Ex2[3], BinaryTree_Ex2[5], BinaryTree_Ex2[6]);
 TreeLink(BinaryTree_Ex2[5], NULL, BinaryTree_Ex2[7]);
 TreeLink(BinaryTree_Ex2[6], NULL, BinaryTree_Ex2[8]);
 TreeLink(BinaryTree_Ex2[8], BinaryTree_Ex2[9], NULL);

 cout << "Universal PreOrder Binary Tree, EX2"   << endl; 
 cout << "=====================================" << endl;

 cout << "Step 1)"  << endl;
 cout << "       Root" << endl;
 cout << "       /"  << endl;
 cout << "      A"  << endl;
 cout << "     /\\   "  << endl;
 cout << "    B  D"  << endl;
 cout << "   /   /\\"  << endl;
 cout << "  C   E  F" << endl;
 cout << "       \\  \\" << endl;
 cout << "        G  H" << endl;
 cout << "          /" << endl;
 cout << "         I"  << endl;
 
 cout << "Step 2) ";
 Universal_PreOrder(BinaryTree_Ex2[0]);
 cout << endl;
 //=========================================
}

 

void PUSH(TreePtr node)
{
 Stack[gSP] = node;
 gSP++;

 if(gSP > gLimit)
 {
  cout << "Stack is Full";
 }
}

TreePtr POP(void)
{

 TreePtr node;
 gSP--;

 if(gSP < 0)
 {
  cout << "Stack is Smpty";
  return NULL;
 }

 node = Stack[gSP];
 return node;
}

void TreeLink (TreePtr Root, TreePtr Left, TreePtr Right)
{
  Root->LChild = Left;
  Root->RChild = Right;
}

int Universal_PreOrder(TreePtr Root)
{
 TreePtr TempLink;
 TempLink = Root->LChild;  // (Root).LC -> Pointer

 if(TempLink == NULL)
  return 0; // End if Point = 0

Begin:
 if(TempLink->LChild == NULL)
 { // (Pointer).LC = 0? Yes
  if(TempLink->RChild == NULL)
  { // (Pointer).RC = 0? Yes
   cout << TempLink->Data; // Out (Pointer).Data

   while(1)
   {
    if(gSP == 0)
     return 0; // End if Stack = 0
    
    TempLink = POP();   // PopStack to "Pointer"
    TempLink = TempLink->RChild; // (Pointer).RC->Pointer

    if(TempLink != NULL)
     break; // Pointer = 0? No
   }
   goto Begin;
  } else { // (Pointer).RC = 0? No
   cout << TempLink->Data;  // Out (Pointer).Data
   TempLink = TempLink->RChild; // (Pointer).RC->Pointer
   goto Begin;
  }
 } else { // (Pointer).LC = 0? No
   cout << TempLink->Data;  // Out (Pointer).Data
   PUSH(TempLink);   // Push "Pointer" into Stack
   TempLink = TempLink->LChild; // (Pointer).LC->Pointer
   goto Begin;
 }
 return 0;
}


Today's Visitors: 0 Total Visitors: 37
Personal Category: 台北科技大學 Topic: goups / school-wise / school clubs
Previous in This Category: 資料結構作業五之三:Thread InOrder Binary Tree   Next in This Category: 超~精簡的VC6 Debug功能簡介
[Trackback URL]

Post A Comment









Yes No



Please input the magic number:

( Prevent the annoy garbage messages )
( What if you cannot see the numbers? )
Please input the magic number

誰來收藏
Loading ...
unlog_NVPO 0