May 1, 2009

資料結構作業五之一:Creat 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 Creat_PreOrder(TreePtr Root);

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

void main(void)
{
 TreePtr BinaryTree[11];
 char Data[11] = {'=','A','/','*','F','+','-','B','C','D','E'};
 int i;

 for(i=0; i < 11 ; i++)
 {
  BinaryTree[i] = (TreePtr) malloc(sizeof(TreeNode));
  BinaryTree[i]->Data = Data[i];
  BinaryTree[i]->LChild = NULL;
  BinaryTree[i]->RChild = NULL;
 }

 TreeLink(BinaryTree[0], BinaryTree[1], BinaryTree[2]);
 TreeLink(BinaryTree[2], BinaryTree[3], BinaryTree[4]);
 TreeLink(BinaryTree[3], BinaryTree[5], BinaryTree[6]);
 TreeLink(BinaryTree[5], BinaryTree[7], BinaryTree[8]);
 TreeLink(BinaryTree[6], BinaryTree[9], BinaryTree[10]);

 cout << "Creat PreOrder Binary Tree"   << endl;
 cout << "===========================" << endl;
 cout << "Step 1) A=(B+C)*(D-E)/F"   << endl << endl;
 cout << "Step 2)"  << endl;
 cout << "      ="  << endl;
 cout << "    /   \\   " << endl;
 cout << "   a   \'/\'"  << endl;
 cout << "      /  \\"  << endl;
 cout << "     *    F" << endl;
 cout << "    /  \\"  << endl;
 cout << "   +    -"  << endl;
 cout << "  / \\  / \\"  << endl;
 cout << " B  C  D  E" << endl << endl;

 cout << "Step 3) ";
 Creat_PreOrder(BinaryTree[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];
 Stack[gSP] = NULL;
 return node;
}

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

int Creat_PreOrder(TreePtr Root)
{
 TreePtr TempLink;
 int L=1;
 TempLink = Root;

 if( (TempLink->LChild == NULL) && (TempLink->RChild == NULL) )
 {
  cout << "Tree is empty!!"; // Empty Header?
  return 0;
 }
 cout << TempLink->Data;
 PUSH(Root);
 while(1)
 {
  if(L)
   TempLink = TempLink->LChild; // Get (LC)

  if((TempLink->LChild != NULL) || (TempLink->RChild != NULL))
  { // Leaf? No
   cout << TempLink->Data; // Out Data
   PUSH(TempLink);  // Push into Stack
   L= 1;
  }
  else
  { // Leaf? Yes
   cout << TempLink->Data; // Out Data
   if(gSP == 0)
   { // Stack Empty? Yes
    break;
   }
   else
   { // Stack Empty? No
    TempLink = POP();   // Pop from Stack
    TempLink = TempLink->RChild; // Get (RC)
    L = 0;
   }
  }
 }
 cout << endl;
 return 0;
}



Today's Visitors: 0 Total Visitors: 43
[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