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

Previous in This Category: 資料結構作業五之二:Parent PostOrder Binary Tree Next in This Category: 資料結構作業五之四:Universal PreOrder Binary Tree

