May 1, 2009

資料結構作業五之三:Thread InOrder Binary Tree

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

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

typedef  TreeNode *TreePtr;

void TreeLink (TreePtr Root, TreePtr Left, TreePtr Right, int LT, int RT);
int Thread_InOrder(TreePtr Root);


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]->LChild = NULL;
  BinaryTree[i]->RChild = NULL;
  BinaryTree[i]->Counter = NULL;
 }

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

 cout << "Thread InOrder 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) ";
 Thread_InOrder(BinaryTree[0]);
 cout << endl;
}

 

void TreeLink (TreePtr Root, TreePtr Left, TreePtr Right, int LT, int RT)
{
  Root->LChild = Left;
  Root->RChild = Right;
 Root->LThread = LT;
 Root->RThread = RT;
}

int Thread_InOrder(TreePtr Root)
{
 TreePtr TempLink, RootNode;

 RootNode = TempLink = Root; // Get (Root)

 if( (TempLink->LChild == NULL) && (TempLink->RChild == NULL) )
 {
  cout << "Tree is empty!!";
  return 0; // End if Headeris empty.
 }

 TempLink = TempLink->LChild; // Get (LC)
 TempLink->Counter++;
 while(1)
 {
  if((TempLink->LThread == 0) && (TempLink->RThread == 0))
  { // Node? Yes
   if(TempLink->Counter == 2)
   { // Get twice? Yes
    cout << TempLink->Data;  // Out (Data)
    TempLink = TempLink->RChild; // Get (RC)
    TempLink->Counter++;
   } else { // Get twice? No
    TempLink = TempLink->LChild; // Get (LC)
    TempLink->Counter++;
   }
   
  } else { // Node? No
   cout << TempLink->Data;  // Out (Data)
   TempLink = TempLink->RChild; // Get (RC)
   TempLink->Counter++;
  }
  
  if(TempLink == RootNode)
   return 0; // End if Root
 }
}


Today's Visitors: 0 Total Visitors: 55
Personal Category: 台北科技大學 Topic: goups / school-wise / school clubs
Previous in This Category: 資料結構作業五之二:Parent PostOrder Binary Tree   Next in This Category: 資料結構作業五之四:Universal PreOrder 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