数据结构--------二叉树的定义及遍历操作的实现

/*                         二叉树的链式存储以及基本操作                                     */

#include<stdio.h>
#include<stdlib.h>

//树的节点
typedef struct BTNode{
    int data;
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode,*BTTree;


// 辅助队列节点  
typedef struct LinkNode {  
    BTNode *data;  
    struct LinkNode *next;  
} LinkNode;  

// 辅助队列  
typedef struct LinkQueue {  
    LinkNode *front;  
    LinkNode *rear;  
} LinkQueue;



void visit(BTTree T)
{
    if (T != NULL)
        printf("%d ",T->data);
}


/*                        先序遍历：根左右                                    */
void preOrder(BTTree T)
{
    if (T != NULL)
    {
        visit(T);
        preOrder(T->lchild);
        preOrder(T->rchild);
    }
}

/*                        中序遍历：左根右                                    */
void InOrder(BTTree T)
{
    if (T != NULL)
    {
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}


/*                        后序遍历：左右根                                    */
void postOrder(BTTree T)
{
    if (T != NULL)
    {
        postOrder(T->lchild);
        postOrder(T->rchild);
        visit(T);
    }
}


/*                        求树高                                    */
int treeDepth(BTTree T)
{
    if (T == NULL)
        return 0; //空树。树高为0
    else{
        int l = treeDepth(T->lchild);
        int r = treeDepth(T->rchild);
        return l>r ? l+1:r+1; //树的高度等于左右子树高度+1
    }
}

/*                        树的建立                                    */
BTNode* createNode(int data) {  
    BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));  
    newNode->data = data;  
    newNode->lchild = NULL;  
    newNode->rchild = NULL;  
    return newNode;  
} 


/*                        销毁树                                    */
void freeTree(BTTree T) {  
    if (T != NULL) {  
        freeTree(T->lchild);    // 递归释放左子树  
        freeTree(T->rchild);    // 递归释放右子树  
        free(T);                // 释放当前节点  
    }  
}

  

// 初始化队列  
void initQueue(LinkQueue *queue) {  
    queue->front = queue->rear = NULL;  //不带头节点的队列
}  

// 入队  
void enqueue(LinkQueue *queue, BTNode *node) {  
    LinkNode *newNode = (LinkNode *)malloc(sizeof(LinkNode));  
    newNode->data = node;  
    newNode->next = NULL;  
    if (queue->rear == NULL) {  
        queue->front = queue->rear = newNode;  //队列为空，插入第一个新节点后头指针，尾指针都指向第一个节点
    } else {  
        queue->rear->next = newNode;  //队尾入队
        queue->rear = newNode;  //更新队尾指针
    }  
}  

// 出队  
int dequeue(LinkQueue *queue, BTNode **node) {  
    if (queue->front == NULL) {  
        return 0; // 队列为空  
    }  
    LinkNode *temp = queue->front;  
    *node = temp->data;  
    queue->front = queue->front->next;  
    if (queue->front == NULL) {  
        queue->rear = NULL; // 队列变空  
    }  
    free(temp);  
    return 1; // 成功出队  
}  

// 判断队列是否为空  
int isQueueEmpty(LinkQueue *queue) {  
    return queue->front == NULL;  
}  

/* 层序遍历 */  
void levelOrder(BTTree T) {  
    LinkQueue queue;  
    initQueue(&queue);  
    BTNode *p = NULL;  

    if (T != NULL) {  
        enqueue(&queue, T); // 将根节点入队  
        
        while (!isQueueEmpty(&queue)) {  
            dequeue(&queue, &p); // 出队  
            visit(p); // 访问节点  

            // 将左右子节点入队  
            if (p->lchild != NULL) {  
                enqueue(&queue, p->lchild);  
            }  
            if (p->rchild != NULL) {  
                enqueue(&queue, p->rchild);  
            }  
        }  
    }  
}  


int main() {  
    // 创建二叉树  
    BTTree root = createNode(1);  
    root->lchild = createNode(2);  
    root->rchild = createNode(3);  
    root->lchild->lchild = createNode(4);  
    root->lchild->rchild = createNode(5);  
    root->rchild->lchild = createNode(6);  
    root->rchild->rchild = createNode(7);
    root->lchild->lchild->lchild = createNode(8);
    root->rchild->rchild->rchild = createNode(9); 

    // 先序遍历  
    printf("先序遍历: ");  
    preOrder(root);  
    printf("\n");  

    // 中序遍历  
    printf("中序遍历: ");  
    InOrder(root);  
    printf("\n");  

    // 后序遍历  
    printf("后序遍历: ");  
    postOrder(root);  
    printf("\n");  

    //层序遍历
    printf("层序遍历：");
    levelOrder(root);
    printf("\n");

    // 求树高  
    printf("树的高度: %d\n", treeDepth(root)); 
 

    // 释放内存  
    freeTree(root);  

    return 0;  
}  

运行结果如下图