【C语言数据结构】二叉树及其遍历算法

落日映苍穹つ 2024-02-26 02:44 50阅读 0赞

--------------------

#### 二叉树及其遍历算法 ####

*  代码实现

--------------------

## 代码实现 ##

#include<stdio.h>
    #include<stdlib.h>
    #include<stdbool.h>
    
    #define ElemType char
    
    //定义树结构体(二叉树结点Binary Tree Node)
    typedef struct BiTNode {
        
        //当前结点的数据
        ElemType data;
    
        //左右孩子结点
        struct BiTNode *lchild, *rchild;
    } BiTNode, *BiTree;
    
    //建立新结点
    BiTree createNode(ElemType e) {
        
        //先给新结点创建一个内存空间
        BiTNode *newNode = (BiTree) malloc(sizeof(BiTree));
    
        //把数据放入新结点
        newNode->data = e;
    
        //把左右孩子设置为空
        newNode->lchild = NULL;
        newNode->rchild = NULL;
    
        //返回新结点
        return newNode;
    }
    
    //打印当前结点的数据
    void visit(BiTree T) {
        
        printf("%c ", T->data);
    }
    
    //递归先序遍历(根左右)
    void PreOrder(BiTree T) {
        
        //直到结点为空停止打印
        if (T != NULL) {
        
            //先打印当前结点
            visit(T);
            //打印左孩子的
            PreOrder(T->lchild);
            //打印右孩子的
            PreOrder(T->rchild);
        }
    }
    
    //递归中序遍历(左根右)
    void InOrder(BiTree T) {
        
        if (T != NULL) {
        
            InOrder(T->lchild);
            visit(T);
            InOrder(T->rchild);
        }
    }
    
    //递归后序遍历(左右根)
    void PostOrder(BiTree T) {
        
        if (T != NULL) {
        
            PostOrder(T->lchild);
            PostOrder(T->rchild);
            visit(T);
        }
    }
    
    //定义链栈(用于一会儿实现非递归各种遍历算法)
    typedef struct LinkNode {
        
        //链栈的元素为树的结点
        BiTree TNode;
    
        //链栈指针
        struct LinkNode *next;
    
    } LinkNode, *LinkStack;
    
    //初始化栈
    void InitStack(LinkStack *stack) {
        
        *stack = NULL;
    }
    
    //入栈操作
    bool Push(LinkStack *stack, BiTree T) {
        
        //建立一个新的栈结点
        LinkStack new = (LinkStack) malloc(sizeof(LinkNode));
        //判断是否申请成功了内存资源
        if (new == NULL)
            return false;
        //把T结点放到栈里
        new->TNode = T;
    
        //把新结点转化为头结点
        new->next = *stack;
        *stack = new;
    
        return true;
    }
    
    //出栈操作
    bool Pop(LinkStack *stack, BiTree *T) {
        
        if (stack == NULL)
            return false;
        //把栈顶元素赋值给T
        *T = (*stack)->TNode;
        LinkStack old = *stack;
        //栈顶元素移动到下一个
        *stack = (*stack)->next;
    
        //释放出栈元素的内存空间
        free(old);
        return true;
    }
    
    //判断栈空
    bool IsEmpty(LinkStack stack) {
        
        return stack == NULL;
    }
    
    //非递归先序遍历(有点麻烦，具体看王道课本p135)
    void PreOrder2(BiTree T) {
        
        //初始化栈
        LinkNode *stack;
        InitStack(&stack);
    
        //弄个移动结点用来遍历
        BiTree P = T;
    
        //当二叉树结点或者栈不为空时
        while (P || !IsEmpty(stack)) {
        
            if (P) {
        
                //根
                visit(P);
    
                //左
                Push(&stack, P);
    
                P = P->lchild;
            } else {
        
                //右
                Pop(&stack, &P);
                P = P->rchild;
            }
        }
    }
    
    //非递归中序遍历(有点麻烦，具体看王道课本p135)
    void InOrder2(BiTree T) {
        
        //初始化链栈
        LinkStack stack;
        InitStack(&stack);
        BiTree P = T;
        //当链栈不为空或者二叉树的结点不为空时
        while (P || !IsEmpty(stack)) {
        
            if (P) {
        
                //结点入栈
                Push(&stack, P);
                //左
                P = P->lchild;
            } else {
        
                Pop(&stack, &P);
                //根
                visit(P);
                //右
                P = P->rchild;
            }
        }
    }
    
    //读取栈顶元素(为了下面的非递归后序遍历要用到才写的)
    bool GetTop(LinkStack stack, BiTree *T) {
        
        if (stack == NULL)
            return false;
        //把栈顶元素赋值给T
        *T = stack->TNode;
    
        return true;
    }
    
    //非递归后序遍历(地狱难度，难死我了反正)
    void PostOrder2(BiTree T) {
        
        //初始化栈
        LinkStack stack;
        InitStack(&stack);
    
        //定义一个遍历指针P，还有一个标识已经访问过的结点的指针r
        BiTree P = T;
        BiTree r = NULL;
    
        //老样子,二叉树结点不为空或者链栈不为空
        while (P || !IsEmpty(stack)) {
        
            if (P) {
        
                Push(&stack, P);
                //左
                P = P->lchild;
            } else {
        
                //读取栈顶元素(看看现在最左边的结点还有没有右孩子，如果有右孩子还没被访问过就先往右边跑)
                GetTop(stack, &P);
                //一直往右边跑，直到没有右孩子或者右孩子已经被访问过
                if (P->rchild && r!=P->rchild){
        
                    //右
                    P = P->rchild;
                }
                else{
        
                    Pop(&stack,&P);
    
                    //根
                    visit(P);
    
                    r = P;
                    P = NULL;
                }
            }
        }
    }
    
    //定义链队列结构体(为了接下来的层次遍历算法)
    typedef struct LQNode{
        
        //数据元素也是树的结点
        BiTree TNode;
    
        //指向下一个结点
        struct LQNode *next;
    }LQNode;
    
    typedef struct LinkQueue{
        
        //定义队首队尾指针
        LQNode *front,*rear;
    }*LinkQueue;
    
    //初始化队列
    void InitQueue(LinkQueue *queue){
        
        (*queue) = (LinkQueue)malloc(sizeof(LQNode));
        (*queue)->front = NULL;
        (*queue)->rear = NULL;
    }
    
    //入队操作
    bool EnQueue(LinkQueue *queue,BiTree T){
        
        //建立一个新的队列结点
        LQNode *newNode = (LQNode*)malloc(sizeof(LQNode));
    
        //判断内存是否分配成功
        if(newNode==NULL)
            return false;
    
        newNode->TNode = T;
        newNode->next = NULL;
    
        if((*queue)->front == NULL){
        
            (*queue)->front = newNode;
            (*queue)->rear = newNode;
        }
        else{
        
            (*queue)->rear->next = newNode;
            (*queue)->rear = newNode;
        }
        return true;
    }
    
    //出队操作
    bool DeQueue(LinkQueue *queue,BiTree *T){
        
        if((*queue) == NULL){
        
            return false;
        }
    
        *T = (*queue)->front->TNode;
        LQNode *old = (*queue)->front;
        (*queue)->front = (*queue)->front->next;
        free(old);
        return true;
    }
    
    //判断队列是否为空
    bool IsEmptyQ(LinkQueue queue){
        
        return queue->front == NULL;
    }
    
    //层次遍历
    void LevelOrder(BiTree T){
        
        LinkQueue queue;
        InitQueue(&queue);
    
        //根结点入队
        EnQueue(&queue,T);
    
        while(!IsEmptyQ(queue)){
        
            DeQueue(&queue,&T);
            visit(T);
            if(T->lchild){
        
                EnQueue(&queue,T->lchild);
            }
            if(T->rchild){
        
                EnQueue(&queue,T->rchild);
            }
        }
    }
    int main() {
        
        //建立根结点A
        BiTree root = createNode('A');
        //根结点左孩子为B
        root->lchild = createNode('B');
        //根结点右孩子为C
        root->rchild = createNode('C');
        //以下以此类推添加结点
        root->lchild->lchild = createNode('D');
        root->lchild->rchild = createNode('E');
        root->rchild->lchild = createNode('F');
        root->rchild->rchild = createNode('G');
        root->lchild->lchild->lchild = createNode('H');
    
        //大概是这样子的二叉树:
        /*                            A
                                 B        C
                               D   E    F   G
                             H
        所以手算一下
        先序遍历应该是A B D H E C F G
        中序遍历应该是H D B E A F C G
        后序遍历应该是H D E B F G C A
        层次遍历应该是A B C D E F G H
         */
        
        //递归先序遍历
        printf("递归先序遍历结果为:");
        PreOrder(root);
        printf("\n");
    
        //递归中序遍历
        printf("递归中序遍历结果为:");
        InOrder(root);
        printf("\n");
    
        //递归后序遍历
        printf("递归后序遍历结果为:");
        PostOrder(root);
        printf("\n");
    
        //非递归先序遍历
        printf("非递归先序遍历结果为:");
        PreOrder2(root);
        printf("\n");
    
        //非递归中序遍历
        printf("非递归中序遍历结果为:");
        InOrder2(root);
        printf("\n");
    
        //非递归后序遍历
        printf("非递归后序遍历结果为:");
        PostOrder2(root);
        printf("\n");
    
        //层次遍历
        printf("层次遍历结果为:");
        LevelOrder(root);
        printf("\n");
    
    
        return 0;
    }