May 1, 2009

資料結構作業五之二:Parent PostOrder Binary Tree

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

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

typedef  TreeNode *TreePtr;
void TreeLink (TreePtr Root, TreePtr Mom, TreePtr Left, TreePtr Right);
int Parent_PostOrder(TreePtr Root);
void PUSH(TreePtr node);
TreePtr POP(void);


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

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

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

 cout << "Parent PostOrder 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) ";
 Parent_PostOrder(BinaryTree[0]);
 cout << endl;
}
 


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

int Parent_PostOrder(TreePtr Root)
{
 TreePtr TempLink, RootNode;
 int L=1;
 RootNode = TempLink = Root;

 if( (TempLink->LChild == NULL) && (TempLink->RChild == NULL) )
 { // Empty Head? Yes
  cout << "Tree is empty!!" << endl;
  return 0;
 }

 while(1)
 {
  TempLink = TempLink->LChild; // Get (LC)
  TempLink->Counter++;  // Increment (Counter)

  Begin:
  if((TempLink->LChild == NULL) && (TempLink->RChild == NULL))
  { // Leaf? = Yes
   cout << TempLink->Data;   // Out (Data)
   TempLink = TempLink->Parent; // Get (Parent)
   
   if(TempLink == RootNode)
    return 0; // End if TempLink = Rootnode
   else
   { // Root? No
    TempLink->Counter++; // Increment (Counter)
    break;
   }
  } else  { // Leaf? = No
   if(TempLink->Counter != 1)
    break; // Get First Times? No
  }
 }

 while(1)
 {
  if(TempLink->Counter == 2)
  { // Get Second Times? Yes
   TempLink = TempLink->RChild; // Get (RC)
   TempLink->Counter++;  // Increment (Counter)
   goto Begin;
  } else { // Get Second Times? No
   cout << TempLink->Data;   // Out (Data)
   TempLink = TempLink->Parent; // Get (Parent)

   if(TempLink == RootNode)
    return 0; // End if TempLink = RootNode
   else
   { // Root? No
    TempLink->Counter++; // Increment (Counter)
   }
  }
 }
}



Today's Visitors: 0 Total Visitors: 31
Personal Category: 台北科技大學 Topic: goups / school-wise / school clubs
Previous in This Category: 資料結構作業五之一:Creat PreOrder Binary Tree   Next in This Category: 資料結構作業五之三:Thread InOrder Binary Tree
[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