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

Previous in This Category: 資料結構作業五之一:Creat PreOrder Binary Tree Next in This Category: 資料結構作業五之三:Thread InOrder Binary Tree

