#include <limits.h>
#include <math.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
typedef int ElementType;
typedef struct TreeNode {
ElementType Data;
struct TreeNode *Left;
struct TreeNode *Right;
} * BinTree_t;
#define ElementQueueType BinTree_t
typedef struct QueueNode {
ElementQueueType data;
struct QueueNode *next;
} * QNode_t;
typedef struct QueueHeader {
QNode_t front;
QNode_t rear;
} * Queue_t;
Queue_t CreateQueue(void) {
Queue_t Q = (Queue_t)malloc(sizeof(struct QueueHeader));
Q->front = NULL;
Q->rear = NULL;
return Q;
}
void AddQ(Queue_t Q, ElementQueueType item) {
if (!Q) {
return;
}
QNode_t temp = (QNode_t)malloc(sizeof(struct QueueNode));
if (!item) {
temp->data = NULL;
} else {
temp->data = item;
}
temp->next = NULL;
if (!Q->front && !Q->rear) {
Q->front = temp;
Q->rear = temp;
} else {
Q->rear->next = temp;
Q->rear = temp;
}
}
int IsEmptyQ(Queue_t Q) { return !Q->front; }
ElementQueueType DeleteQ(Queue_t Q) {
if (!Q) {
return NULL;
}
if (IsEmptyQ(Q)) {
return NULL;
}
QNode_t temp = Q->front;
ElementQueueType tempdata;
if (Q->front == Q->rear) {
Q->front = NULL;
Q->rear = NULL;
} else {
Q->front = Q->front->next;
}
tempdata = temp->data;
free(temp);
return tempdata;
}
void DisposeQueue(Queue_t Q) {
while (!IsEmptyQ(Q)) {
DeleteQ(Q);
}
free(Q);
}
void PrintQueue(Queue_t Q) {
if (IsEmptyQ(Q)) {
return;
}
printf("打印队列数据元素：\n");
QNode_t temp = Q->front;
for (; temp; temp = temp->next) {
printf("0x%3lX ", (unsigned long int)temp->data & 0xFFF);
}
printf("\n");
}
#define ElementStackType BinTree_t
typedef struct StackNode // node defination
{
ElementStackType data;
struct StackNode *next;
} * Stack_t;
int IsEmpty(Stack_t S) { return !S->next; }
Stack_t CreateStack(void) {
Stack_t S = (Stack_t)malloc(sizeof(struct StackNode));
S->next = NULL;
return S;
}
ElementStackType Pop(Stack_t S) {
ElementStackType temp;
Stack_t tmepNode = S->next;
if (tmepNode != NULL) {
temp = tmepNode->data;
S->next = tmepNode->next;
free(tmepNode);
return temp;
} else {
return NULL;
}
}
void MakeEmpty(Stack_t S) {
while (S->next != NULL) {
Pop(S);
}
}
void DisposeStack(Stack_t S) {
MakeEmpty(S);
free(S);
}
void Push(Stack_t S, ElementStackType X) {
Stack_t tempNode = S->next;
Stack_t newNode = (Stack_t)malloc(sizeof(struct StackNode));
newNode->data = X;
if (tempNode != NULL) {
newNode->next = tempNode;
} else {
newNode->next = NULL;
}
S->next = newNode;
}
ElementStackType Top(Stack_t S) {
if (S->next != NULL) {
return S->next->data;
} else {
return NULL;
}
}
void PrintStack(Stack_t S) {
Stack_t tep = S->next;
while (tep != NULL) {
printf("addr=0x%3lX dataadd=0x%3lX nextaddr=0x%3lX\n",
(unsigned long int)tep & 0xFFF,
(unsigned long int)tep->data & 0xFFF,
(unsigned long int)tep->next & 0xFFF);
tep = tep->next;
}
}
BinTree_t CreateTreeNode(int dat) {
BinTree_t new = (BinTree_t)malloc(sizeof(struct TreeNode));
new->Data = dat;
new->Left = NULL;
new->Right = NULL;
return new;
}
void ConnectNode(BinTree_t root, BinTree_t left, BinTree_t right) {
if (!root) {
printf("error in null\n");
return;
}
root->Left = left;
root->Right = right;
}
void LevelOrderTraversal(BinTree_t BT) {
Queue_t myqueue = CreateQueue();
BinTree_t temp = NULL;
AddQ(myqueue, BT);
while (!IsEmptyQ(myqueue)) {
temp = DeleteQ(myqueue);
if (temp != NULL) {
printf("%d ", temp->Data);
AddQ(myqueue, temp->Left);
AddQ(myqueue, temp->Right);
}
}
DisposeQueue(myqueue);
}
int FindTreeHeight(BinTree_t BT) {
int rightlen, leftlen, maxlen;
if (BT) {
rightlen = FindTreeHeight(BT->Right);
leftlen = FindTreeHeight(BT->Left);
maxlen = leftlen > rightlen ? leftlen : rightlen;
return maxlen + 1;
} else {
return 0;
}
}
void DrawTree(BinTree_t BT) {
int height = FindTreeHeight(BT);
int cnt = 0;
Queue_t myqueue = CreateQueue();
BinTree_t temp = NULL;
int width = 0;
AddQ(myqueue, BT);
for (int i = 0; i < height; i++) {
cnt = (int)pow(2, i);
width = pow(2, height - i + 1);
while (cnt--) {
temp = DeleteQ(myqueue);
if (temp != NULL) {
printf("%*d%*c", width, temp->Data, width, ' ');
AddQ(myqueue, temp->Left);
AddQ(myqueue, temp->Right);
} else {
printf("%p ", temp);
}
}
printf("\n");
if (i != height - 1) {
int nextwidth = (int)pow(2, height - i);
for (int J = 0; J < (int)pow(2, i); J++) {
printf("%*c%*c", width, '+', width, ' ');
}
printf("\n");
for (int k = 0; k < (int)pow(2, i + 1); k++) {
if ((k % 2) == 0) {
printf("%*c", nextwidth, '-');
for (uint8_t z = 0; z < nextwidth; z++) {
printf("-");
}
} else {
for (uint8_t z = 0; z < nextwidth; z++) {
printf("-");
}
printf("%*c", nextwidth, ' ');
}
}
printf("\n");
}
printf("\r");
}
DisposeQueue(myqueue);
}
BinTree_t FindElement(BinTree_t BST, ElementType Dat) {
BinTree_t temp = BST;
if (BST == NULL) {
return NULL;
}
while (temp) {
if (Dat > temp->Data) {
temp = temp->Right;
} else if (Dat < temp->Data) {
temp = temp->Left;
} else {
return temp;
}
}
return NULL;
}
BinTree_t FindMax(BinTree_t BST) {
if (BST->Right == NULL) {
return BST;
}
return FindMax(BST->Right);
}
BinTree_t FindMin(BinTree_t BST) {
BinTree_t tmp = BST;
while (tmp->Left) {
tmp = tmp->Left;
}
return tmp;
}
BinTree_t DeleteElementBST(BinTree_t BST, ElementType Dat) {
BinTree_t tmpNode;
if (BST == NULL) {
return NULL;
} else if (Dat < BST->Data) {
BST->Left = DeleteElementBST(BST->Left, Dat);
} else if (Dat > BST->Data) {
BST->Right = DeleteElementBST(BST->Right, Dat);
} else if (BST->Left && BST->Right) {
tmpNode = FindMin(BST->Right);
BST->Data = tmpNode->Data;
BST->Right = DeleteElementBST(BST->Right, BST->Data);
} else {
tmpNode = BST;
if (BST->Left == NULL) {
BST = BST->Right;
} else if (BST->Right == NULL) {
BST = BST->Left;
}
free(tmpNode);
}
return BST;
}
void InsertNode(ElementType X, BinTree_t BST) {
if (BST == NULL) {
return;
}
BinTree_t newNode = (BinTree_t)malloc(sizeof(struct TreeNode));
BinTree_t temp = BST;
BinTree_t last = BST;
newNode->Data = X;
newNode->Left = newNode->Right = NULL;
while (temp) {
last = temp;
if (X > temp->Data) {
temp = temp->Right;
} else if (X < temp->Data) {
temp = temp->Left;
} else if (X == temp->Data) {
printf("已经存在相同元素");
return;
}
}
if (X > last->Data) {
last->Right = newNode;
} else {
last->Left = newNode;
}
}
void UseageHelp(void) {
printf("\n \
搜索树的操作\n \
(1).创建新的搜索树;\n \
(2).输出树高度;\n \
(3).层序遍历;\n \
(4).绘制二叉树;\n \
(5).寻找某元素:\n \
(6).递归寻找最大值:\n \
(7).循环寻找最小值:\n \
(8).插入一个元素:\n \
(9).删除一个元素:\n \
(h).帮助;\n \
(q).quit;\n \
");
}
BinTree_t CreateBinTree(void) {
printf("Create Binary Tree like this: \n\
90 \n\
| \n\
------------------------ \n\
| | \n\
50 150 \n\
| | \n\
------------- ------------- \n\
| | | | \n\
20 75 95 175 \n\
| | | | \n\
------- ------- ------- ------- \n\
| | | | | | | | \n\
5 nil nil 80 92 111 nil nil \n\
");
BinTree_t A = CreateTreeNode(90);
BinTree_t B = CreateTreeNode(50);
BinTree_t C = CreateTreeNode(150);
BinTree_t D = CreateTreeNode(20);
BinTree_t E = CreateTreeNode(75);
BinTree_t F = CreateTreeNode(95);
BinTree_t G = CreateTreeNode(175);
BinTree_t H = CreateTreeNode(5);
BinTree_t I = CreateTreeNode(25);
BinTree_t J = CreateTreeNode(66);
BinTree_t K = CreateTreeNode(80);
BinTree_t L = CreateTreeNode(92);
BinTree_t M = CreateTreeNode(111);
ConnectNode(A, B, C);
ConnectNode(B, D, E);
ConnectNode(D, H, NULL);
ConnectNode(E, NULL, K);
ConnectNode(C, F, G);
ConnectNode(F, L, M);
ConnectNode(G, NULL, NULL);
return A;
}
BinTree_t BinaryTree = NULL;
int main(int argc, char const *argv[]) {
BinTree_t tmp = NULL;
int empdat = 0;
UseageHelp();
while (1) {
switch (getchar()) {
case '1':
BinaryTree = CreateBinTree();
printf("创建成功!\n");
break;
case '2':
printf("输出树高度:%d", FindTreeHeight(BinaryTree));
printf("\n");
break;
case '3':
printf("层序遍历:");
LevelOrderTraversal(BinaryTree);
printf("\n");
break;
case '4':
printf("绘制二叉树:\n");
DrawTree(BinaryTree);
printf("\n");
break;
case '5':
printf("寻找某元素:\n");
printf("请输入元素值:");
scanf("%d", &empdat);
tmp = FindElement(BinaryTree, empdat);
if (!tmp) {
printf("not find the node");
} else {
printf("find the node");
}
printf("\n");
break;
case '6':
printf("递归寻找最大值:\n");
tmp = FindMax(BinaryTree);
printf("%d", tmp->Data);
printf("\n");
break;
case '7':
printf("递归寻找小最值:\n");
tmp = FindMin(BinaryTree);
printf("%d", tmp->Data);
printf("\n");
break;
case '8':
printf("插入一个元素:\n");
printf("请输入需要插入的值:");
scanf("%d", &empdat);
InsertNode(empdat, BinaryTree);
printf("\n");
break;
case '9':
printf("删除一个元素:\n");
printf("请输入需要删除的值:");
scanf("%d", &empdat);
DeleteElementBST(BinaryTree, empdat);
printf("\n");
break;
case 'h':
UseageHelp();
break;
case 'q':
exit(0);
break;
default:
break;
}
}
return 0;
}
|
