資料結構作業五之四: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;
}

Previous in This Category: 資料結構作業五之三:Thread InOrder Binary Tree Next in This Category: 超~精簡的VC6 Debug功能簡介

