void InOrderBinaryTree(bitree *root)
{
bitree *p;
bitree *s[MAX_STACK_LEVEL];
int top = 0;
short int IsStop;
p = root;
IsStop = FALSE;
while (! IsStop)
{
while ( (p != NULL) && (! IsStop) )
{
if (top < MAX_STACK_LEVEL-1)
{
top++;
s[top] = p;
p = p -> lchild;
}
else {
printf("Stack overflow !\n");
IsStop = TRUE;
}
}
if (! IsStop)
{
if (top != 0)
{
p = s[top];
printf("%c ", p -> data);
top--;
p = p -> rchild;
}
else
IsStop = TRUE;
}
}
}
// 二叉樹后序遍歷 - 遞回版本
void PostOrderRetrieveBinaryTree(bitree *root)
{
// [上機作業 1] - 自己上機實作 ...}
void PostOrderBinaryTree(bitree *root)
{
bitree *p;
bitree *pre = NULL;
bitree *s[MAX_STACK_LEVEL];
int top = 0;
p = root;
while ( (top != 0) || (p != NULL) )
{
while(p != NULL)
{
if (top < MAX_STACK_LEVEL-1)
{
top++;
s[top] = p;
p = p -> lchild;
}
else
{
printf("Stack overflow !\n");
return;
}
}
if(top != 0)
{
p = s[top];
if ( (p -> rchild == NULL) || (p -> rchild == pre) )
{
printf("%c ", p -> data);
top--;
pre = p;
p = NULL;
}
else {
p = p -> rchild;
}
}
}
}
void LevelOrderBinaryTree(bitree *root)
{
bitree *p;
bitree *q[MAX_QUEUE_LENGTH];
int front = MAX_QUEUE_LENGTH - 1;
int rear = MAX_QUEUE_LENGTH - 1;
short int IsStop;
p = root;
IsStop = FALSE;
while (! IsStop)
{
if (p != NULL)
{
printf("%c ", p -> data);
if (p -> lchild != NULL)
{
if ( ((rear + 1) % MAX_QUEUE_LENGTH) == front )
{
printf("Queue full !\n");
IsStop = TRUE;
}
else
{
rear = (rear + 1) % MAX_QUEUE_LENGTH;
q[rear] = p -> lchild;
};
}
if (p -> rchild != NULL)
{
if ( ((rear + 1) % MAX_QUEUE_LENGTH) == front )
{
printf("Queue full !\n");
IsStop = TRUE;
}
else
{
rear = (rear + 1) % MAX_QUEUE_LENGTH;
q[rear] = p -> rchild;
};
}
}
if (rear != front)
{
p = q[(front + 1) % MAX_QUEUE_LENGTH];
front = (front + 1) % MAX_QUEUE_LENGTH;
}
else
IsStop = TRUE;
}
}
bitree *FindTargetNode(bitree *root, char targetdata)
{
bitree *p;
bitree *T;
bitree *s[MAX_STACK_LEVEL];
int top = 0;
short int IsStop;
p = root;
IsStop = FALSE;
while (! IsStop)
{
while ( (p != NULL) && (! IsStop) )
{
if (p -> data == targetdata)
{
T = p;
IsStop = TRUE;
}
else
{
if (top < MAX_STACK_LEVEL-1) {
top++;
s[top] = p;
p = p -> lchild;
}
else
{
printf("Stack overflow !\n");
T = NULL;
IsStop = TRUE;
}
}
}
if (! IsStop)
{
if (top != 0)
{
p = s[top];
top--;
p = p -> rchild;
}
else
{
T = NULL;
IsStop = TRUE;
}
}
}
return T;
}
bitree *FindTargetNode(bitree *root, enum BinaryTreeNodeTypeSet NodeType)
{
bitree *p;
bitree *T;
bitree *s[MAX_STACK_LEVEL];
int top = 0;
short int IsStop;
short int b;
p = root;
IsStop = FALSE;
while (! IsStop)
{
while ( (p != NULL) && (! IsStop) )
{
switch(NodeType)
{
case HAS_NO_CHILD :
b = ( (p -> lchild == NULL) && (p -> rchild == NULL) );
break;
case HAS_NO_LEFTCHILD :
b = ( (p -> lchild == NULL) );
break;
case HAS_NO_RIGHTCHILD :
b = ((p -> rchild == NULL) );
break;
default :
break;
}
if (b)
{
T = p;
IsStop = TRUE;
}
else
{
if (top < MAX_STACK_LEVEL-1)
{
top++;
s[top] = p;
p = p -> lchild;
}
else
{
printf("Stack overflow !\n");
T = NULL;
IsStop = TRUE;
}
}
}
if (! IsStop)
{
if (top != 0)
{
p = s[top];
top--;
p = p -> rchild;
}
else
{
T = NULL;
IsStop = TRUE;
}
}
}
return T;
}
void AddChild(bitree *root, char newdata, enum BinaryTreeNodeTypeSet NodeType)
{
bitree *T;
bitree *p;
T = FindTargetNode(root, NodeType);
if (T != NULL)
{
p = new bitree;
p -> lchild = NULL;
p -> data = newdata;
p -> rchild = NULL;
switch (NodeType)
{
case HAS_NO_CHILD :
T -> lchild = p;
break;
case HAS_NO_LEFTCHILD :
T -> lchild = p;
break;
case HAS_NO_RIGHTCHILD :
T -> rchild = p;
break;
default :
break;
}
}
}
void AddLeftChild(bitree *root, char targetdata, char newdata)
{
bitree *T;
bitree *p;
T = FindTargetNode(root, targetdata);
if (T == NULL) // 未找到 targetdata，則生成一個新節點 ...
{
AddChild(root, newdata, HAS_NO_LEFTCHILD);
}
else
{
p = new bitree;
p -> lchild = NULL;
p -> data = newdata;
p -> rchild = NULL;
T -> lchild = p;
};
}
// 將值 newdata 作為值為 targetdata 的節點的右孩子插入 ...
void AddRightChild(bitree *root, char targetdata, char newdata)
{
// [上機作業 2-1] - 自己上機實作 ...
}
// 洗掉值為 targetdata 的節點的左孩子 ...
// 注意：為方便起見，將洗掉該節點的左孩子及左孩子的所有子節點 ...
void DeleteLeftChild(bitree *root, char targetdata)
{
bitree *T;
// 先尋找該節點指標 ...
T = FindTargetNode(root, targetdata);
if (T != NULL)
{
DestroyBinaryTree(T -> lchild);
T -> lchild = NULL;
}
}
// 洗掉值為 targetdata 的節點的右孩子 ...
void DeleteRightChild(bitree *root, char targetdata)
{
// [上機作業 2-2] - 自己上機實作 ...
}
// 統計二叉樹中葉子節點個數 ...
// 下面的 'int &count' 使用了 C++ 中的“參考”語法，詳見課堂 ppt ...
void CountBinaryTreeLeafNodeNum(bitree *root, int &count)
{
if (root == NULL)
return;
else
{
if ( (root -> lchild == NULL) && (root -> rchild == NULL) )
{
count++;
return;
}
else
{
CountBinaryTreeLeafNodeNum(root -> lchild, count);
CountBinaryTreeLeafNodeNum(root -> rchild, count);
}
}
}
// [上機作業 3] - 從下面的任務中任意選一題完成，包括設計函式頭、引數表和具體的代碼設計 ...
//
// (3-1) - 給定一個資料值，計算包含該資料值的節點的度。
//
// (3-2) - 給定一個資料值，列印輸出包含該資料值的節點的祖先節點。
//
// (3-3) - 給定一個資料值，列印輸出包含該資料值的節點的兄弟節點。
//
// (3-4) - 給定一個資料值，計算包含該資料值的節點的層數。
//
// (3-5) - 計算二叉樹的高度。
//
// (3-6) - 計算二叉樹的度。
//
// (3-7) - 輸入引數為根指標，判斷給定的二叉樹是否為滿二叉樹。
void main()
{
char ch;
FILE *fp;
char *filename = "BinaryTreeData.txt"; ...
bitree *root;
int LeafNodeNum;
int &count = LeafNodeNum;
printf("**********************************\n");
printf("! Menu Selection !\n");
printf("! !\n");
printf("! 1) Input from file !\n");
printf("! 2) Input from keyboard !\n");
printf("! 0) Exit !\n");
printf("! !\n");
printf("**********************************\n");
printf("Your choice[1/2/0] : ");
do
{
ch = getchar();
}
while ( (ch != '0') && (ch != '1') && (ch != '2') );
switch (ch)
{
case '1' : // 從檔案輸入
if ((fp = fopen(filename, "r")) == NULL)
{
printf("Error open binary tree data file !\n");
return;
}
root = CreateBinaryTree(fp);
fclose(fp);
break;
case '2' : // 從鍵盤輸入
printf("Input data to create a binary tree :\n");
root = CreateBinaryTree();
break;
case '0' : // 退出
return;
break;
default :
return;
break;
}
printf("\nThe pre-order is : \n");
//PreOrderRetrieveBinaryTree(root);
PreOrderBinaryTree(root);
// 中序 ...
printf("\nThe in-order is : \n");
//InOrderRetrieveBinaryTree(root);
InOrderBinaryTree(root);
// 后序 ...
printf("\nThe post-order is : \n");
//PostOrderRetrieveBinaryTree(root);
PostOrderBinaryTree(root);
// 層序 ...
printf("\nThe level-order is : \n");
LevelOrderBinaryTree(root);
// 輸出葉子節點的個數 ...
LeafNodeNum = 0; // 變數清 0 ...
CountBinaryTreeLeafNodeNum(root, count);
printf("\nThe number of leaf node is : %d\n", LeafNodeNum);
AddLeftChild(root, '2', '7');
printf("\nAfter [ADD] operation, The pre-order is : \n");
PreOrderRetrieveBinaryTree(root);
//PreOrderBinaryTree(root);
printf("\nAfter [ADD] operation, The post-order is : \n");
//PostOrderRetrieveBinaryTree(root);
PostOrderBinaryTree(root);
printf("\nAfter [ADD] operation, The level-order is : \n");
LevelOrderRetrieveBinaryTree(root);
// 洗掉子節點 ...
DeleteLeftChild(root, '3');
printf("\nAfter [DELETE] operation, The pre-order is : \n");
PreOrderRetrieveBinaryTree(root);
//PreOrderBinaryTree(root);
printf("\nAfter [DELETE] operation, The post-order is : \n");
//PostOrderRetrieveBinaryTree(root);
PostOrderBinaryTree(root);
printf("\nAfter [DELETE] operation, The level-order is : \n");
LevelOrderRetrieveBinaryTree(root);
// 輸出葉子節點的個數 ...
LeafNodeNum = 0; // 變數清 0 ...
CountBinaryTreeLeafNodeNum(root, count);
printf("\nThe number of leaf node is : %d\n", LeafNodeNum);
DestroyBinaryTree(root);
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/146109.html
標籤：基礎類