21-数据结构_链式二叉树-遍历实现

客官°小女子只卖身不卖艺 2021-11-10 21:08 172阅读 0赞

# 零, 链式二叉树 #

![SouthEast][]

# 一, 结点定义 与 创建链式二叉树 #

// binary tree node
    typedef struct BTNode
    {
        char data;
        struct BTNode * pLChild;    // 指向左孩子
        struct BTNode * pRChild;    // 指向右孩子
    } BTNode, * PBTNode;

// 创建二叉树
    PBTNode createBTree(void)
    {   
        // 根
        PBTNode pA = (PBTNode) malloc( sizeof( BTNode ) );
    
        PBTNode pB = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pC = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pD = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pE = (PBTNode) malloc( sizeof( BTNode ) );
    
        // A : 左-B , 右-C
        pA->data = 'A';
        pA->pLChild = pB;
        pA->pRChild = pC;
    
        // B : 左-空, 右-空
        pB->data = 'B';
        pB->pLChild = NULL;
        pB->pRChild = NULL;
    
        // C : 左-D , 右-空
        pC->data = 'C';
        pC->pLChild = pD;
        pC->pRChild = NULL;
    
        // D : 左-空, 右-E
        pD->data = 'D';
        pD->pLChild = NULL;
        pD->pRChild = pE;
    
        // E : 左-空, 右-空
        pE->data = 'E';
        pE->pLChild = NULL;
        pE->pRChild = NULL;
    
        return pA;
    }

# 二, 先序遍历 #

// 遍历- 先序
    void preTraverseBTree(PBTNode pRoot)
    {    
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 根
        printf("%c ", pRoot->data);
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            preTraverseBTree(pRoot->pLChild);
        }
               
        // 右
        if (NULL != pRoot->pRChild)
        {
            preTraverseBTree(pRoot->pRChild);
        }
        return;
    }

# 三, 中序遍历 #

// 中序遍历
    void inTraverseBTree(PBTNode pRoot)
    {   
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            inTraverseBTree(pRoot->pLChild);
        }
               
        // 根
        printf("%c ", pRoot->data);
    
        // 右
        if (NULL != pRoot->pRChild)
        {
            inTraverseBTree(pRoot->pRChild);
        }
        return;
    }

# 四, 后序遍历 #

// 后序遍历
    void postTraverseBTree(PBTNode pRoot)
    {
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            postTraverseBTree(pRoot->pLChild);
        }
              
        // 右
        if (NULL != pRoot->pRChild)
        {
            postTraverseBTree(pRoot->pRChild);
        }    
    
        // 根
        printf("%c ", pRoot->data);
    
        return;
    }

# 五, 完整程序 #

#include <stdio.h>
    #include <malloc.h>
    #include <stdbool.h>
    
    // binary tree node
    typedef struct BTNode
    {
        char data;
        struct BTNode * pLChild;    // 指向左孩子
        struct BTNode * pRChild;    // 指向右孩子
    } BTNode, * PBTNode;
    
    // 创建二叉树
    PBTNode createBTree(void);
    // 先序遍历
    void preTraverseBTree(PBTNode pRoot);
    // 中序遍历
    void inTraverseBTree(PBTNode pRoot);
    // 后序遍历
    void postTraverseBTree(PBTNode pRoot);
    
    
    int main(void)
    {
        PBTNode pBTree = NULL;
    
        pBTree = createBTree();
        
        printf("\n先序遍历:\n");
        preTraverseBTree(pBTree);
    
        printf("\n中序遍历:\n");    
        inTraverseBTree(pBTree);
    
        printf("\n中序遍历:\n");    
        postTraverseBTree(pBTree);
    
        free(pBTree);
    
        return 0;
    }
    
    
    // 创建二叉树
    PBTNode createBTree(void)
    {   
        // 根
        PBTNode pA = (PBTNode) malloc( sizeof( BTNode ) );
    
        PBTNode pB = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pC = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pD = (PBTNode) malloc( sizeof( BTNode ) );
        PBTNode pE = (PBTNode) malloc( sizeof( BTNode ) );
    
        // A : 左-B , 右-C
        pA->data = 'A';
        pA->pLChild = pB;
        pA->pRChild = pC;
    
        // B : 左-空, 右-空
        pB->data = 'B';
        pB->pLChild = NULL;
        pB->pRChild = NULL;
    
        // C : 左-D , 右-空
        pC->data = 'C';
        pC->pLChild = pD;
        pC->pRChild = NULL;
    
        // D : 左-空, 右-E
        pD->data = 'D';
        pD->pLChild = NULL;
        pD->pRChild = pE;
    
        // E : 左-空, 右-空
        pE->data = 'E';
        pE->pLChild = NULL;
        pE->pRChild = NULL;
    
        return pA;
    }
    
    // 遍历- 先序
    void preTraverseBTree(PBTNode pRoot)
    {    
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 根
        printf("%c ", pRoot->data);
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            preTraverseBTree(pRoot->pLChild);
        }
               
        // 右
        if (NULL != pRoot->pRChild)
        {
            preTraverseBTree(pRoot->pRChild);
        }
        return;
    }
    
    // 中序遍历
    void inTraverseBTree(PBTNode pRoot)
    {   
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            inTraverseBTree(pRoot->pLChild);
        }
               
        // 根
        printf("%c ", pRoot->data);
    
        // 右
        if (NULL != pRoot->pRChild)
        {
            inTraverseBTree(pRoot->pRChild);
        }
        return;
    }
    
    // 后序遍历
    void postTraverseBTree(PBTNode pRoot)
    {
        if (NULL ==pRoot)
        {
            return;
        }
    
        // 左
        if (NULL != pRoot->pLChild)
        {
            postTraverseBTree(pRoot->pLChild);
        }
              
        // 右
        if (NULL != pRoot->pRChild)
        {
            postTraverseBTree(pRoot->pRChild);
        }    
    
        // 根
        printf("%c ", pRoot->data);
    
        return;
    }

[SouthEast]: /images/20211109/3eddda040ffa4e42b4cfc147eb69308c.png