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

Previous in This Category: 資料結構作業四:Inverse Linking List & Double Linking List. Next in This Category: 資料結構作業五之二:Parent PostOrder Binary Tree

