我的大二叉树

#include <stdio.h> #include <malloc.h> #include <stdbool.h> #define QUEUE_SIZE 5 /** * 二叉树结点 */ typedef struct BTNode { char element; struct BTNode* left; struct BTNode* right; } BTNode, *BTNodePtr; /** * 存储若干指针的队列 */ typedef struct BTNodePtrQueue { BTNodePtr* nodePtrs; int front; int rear; } BTNodePtrQueue, *QueuePtr; /** * 初始化队列 */ QueuePtr initQueue() { QueuePtr resultQueuePtr = (QueuePtr)malloc(sizeof(struct BTNodePtrQueue)); resultQueuePtr->nodePtrs = (BTNodePtr*)malloc(QUEUE_SIZE * sizeof(BTNodePtr)); resultQueuePtr->front = 0; resultQueuePtr->rear = 1; return resultQueuePtr; }//Of initQueue /** * 判断队列是否为空 */ bool isQueueEmpty(QueuePtr paraQueuePtr) { if ((paraQueuePtr->front + 1) % QUEUE_SIZE == paraQueuePtr->rear) { return true; }//Of if return false; }//Of isQueueEmpty /** * 向队列中添加一个指针 */ void enqueue(QueuePtr paraQueuePtr, BTNodePtr paraBTNodePtr) { printf("front = %d, rear = %d.\r\n", paraQueuePtr->front, paraQueuePtr->rear); if ((paraQueuePtr->rear + 1) % QUEUE_SIZE == paraQueuePtr->front % QUEUE_SIZE) { printf("错误，尝试入队 %c，队列已满。\r\n", paraBTNodePtr->element); return; }//Of if paraQueuePtr->nodePtrs[paraQueuePtr->rear] = paraBTNodePtr; paraQueuePtr->rear = (paraQueuePtr->rear + 1) % QUEUE_SIZE; printf("元素 %c 入队完成。\r\n", paraBTNodePtr->element); }//Of enqueue /** * 从队列中删除一个元素并返回 */ BTNodePtr dequeue(QueuePtr paraQueuePtr) { if (isQueueEmpty(paraQueuePtr)) { printf("错误，队列为空\r\n"); return NULL; }//Of if paraQueuePtr->front = (paraQueuePtr->front + 1) % QUEUE_SIZE; printf("元素 %c 出队完成。\r\n", paraQueuePtr->nodePtrs[paraQueuePtr->front]->element); return paraQueuePtr->nodePtrs[paraQueuePtr->front]; }//Of dequeue /** * 使用给定字符创建二叉树结点 */ BTNodePtr constructBTNode(char paraChar) { BTNodePtr resultPtr = (BTNodePtr)malloc(sizeof(BTNode)); resultPtr->element = paraChar; resultPtr->left = NULL; resultPtr->right = NULL; return resultPtr; }//Of constructBTNode /** * 使用给定字符串构造二叉树 */ BTNodePtr stringToBTree(char* paraString) { int i; char ch; //使用队列管理指针 QueuePtr tempQueuePtr = initQueue(); BTNodePtr resultHeader; BTNodePtr tempParent, tempLeftChild, tempRightChild; i = 0; ch = paraString[i]; resultHeader = constructBTNode(ch); enqueue(tempQueuePtr, resultHeader); while (!isQueueEmpty(tempQueuePtr)) { tempParent = dequeue(tempQueuePtr); //左孩子 i++; ch = paraString[i]; if (ch == '#') { tempParent->left = NULL; } else { tempLeftChild = constructBTNode(ch); enqueue(tempQueuePtr, tempLeftChild); tempParent->left = tempLeftChild; }//Of if //右孩子 i++; ch = paraString[i]; if (ch == '#') { tempParent->right = NULL; } else { tempRightChild = constructBTNode(ch); enqueue(tempQueuePtr, tempRightChild); tempParent->right = tempRightChild; }//Of if }//Of while return resultHeader; }//Of stringToBTree /** * 层序遍历 */ void levelwise(BTNodePtr paraTreePtr) { //使用队列管理指针 char tempString[100]; int i = 0; QueuePtr tempQueuePtr = initQueue(); BTNodePtr tempNodePtr; enqueue(tempQueuePtr, paraTreePtr); while (!isQueueEmpty(tempQueuePtr)) { tempNodePtr = dequeue(tempQueuePtr); //用于输出 tempString[i] = tempNodePtr->element; i++; if (tempNodePtr->left != NULL) { enqueue(tempQueuePtr, tempNodePtr->left); }//Of if if (tempNodePtr->right != NULL) { enqueue(tempQueuePtr, tempNodePtr->right); }//Of if }//Of while tempString[i] = '\0'; printf("层序遍历: %s\r\n", tempString); }//Of levelwise /** * 前序遍历 */ void preorder(BTNodePtr tempPtr) { if (tempPtr == NULL) { return; }//Of if printf("%c", tempPtr->element); preorder(tempPtr->left); preorder(tempPtr->right); }//Of preorder /** * 中序遍历 */ void inorder(BTNodePtr tempPtr) { if (tempPtr == NULL) { return; }//Of if inorder(tempPtr->left); printf("%c", tempPtr->element); inorder(tempPtr->right); }//Of inorder /** * 后序遍历 */ void postorder(BTNodePtr tempPtr) { if (tempPtr == NULL) { return; }//Of if postorder(tempPtr->left); postorder(tempPtr->right); printf("%c", tempPtr->element); }//Of postorder /** * 主函数 */ int main() { BTNodePtr tempHeader; tempHeader = constructBTNode('c'); printf("只有一个结点，前序遍历: "); preorder(tempHeader); printf("\r\n"); char* tempString = "acde#bf######"; tempHeader = stringToBTree(tempString); printf("前序遍历: "); preorder(tempHeader); printf("\r\n"); printf("中序遍历: "); inorder(tempHeader); printf("\r\n"); printf("后序遍历: "); postorder(tempHeader); printf("\r\n"); printf("层序遍历: "); levelwise(tempHeader); printf("\r\n"); return 1; }//Of main