【数据结构】二叉树三种遍历方式

桃扇骨 2021-09-21 06:04 332阅读 0赞

二叉树的遍历分三种:先序、中序、后序  
假如有一棵树  
![在这里插入图片描述][20200608182630763.png]  
先序遍历：根节点->左孩子->右孩子，则上图树的先序遍历结果为：ABC  
中序遍历：左孩子->根节点->右孩子，则上图树的遍历结果为：BAC  
后序遍历：左孩子->右孩子->根节点，则遍历结果为：BCA  
ps：注意根节点的位置，先序在第一个，中序在中间，后续在最后。

树的定义就是递归的，特别是链式存储结构的树，因此树的遍历通常使用递归的方法实现的。

#include <stdio.h>
    #include <stdlib.h>
    
    #define ERROR 0
    #define OK 1
    #define OVERFLOW -1
    #define TRUE 1
    #define FALSE 0
    
    
    typedef char ElemType;
    typedef int status;
    
    //二叉树结构体
    typedef struct BitNode { 
        ElemType data;
        struct BitNode *lNode, *rNode;
    } BiTNode, *BiTree;
    
    void createTree(BiTree &T, ElemType e) { 
        T = (BiTree) malloc(sizeof(BiTree));
        T->data = e;
        T->lNode = NULL;
        T->rNode = NULL;
    }
    
    void printNode(BiTree N) { 
        printf("%c\t", N->data);
    }
    
    
    void preOrder(BiTree T) { 
        if (T != NULL) { 
            printNode(T);
            preOrder(T->lNode);
            preOrder(T->rNode);
        }
    }
    
    void inOrder(BiTree T) { 
        if (T != NULL) { 
            inOrder(T->lNode);
            printNode(T);
            inOrder(T->rNode);
        }
    }
    
    void postOrder(BiTree T) { 
        if (T != NULL) { 
            postOrder(T->lNode);
            postOrder(T->rNode);
            printNode(T);
        }
    }
    
    //在T树中查找元素e，并将结果存储到ins_node
    status findNode(BiTree T, ElemType e, BiTree &ins_node) { 
        if (T != NULL) { 
            if (e == T->data) { 
                ins_node = T;
                return OK;
            }
            findNode(T->lNode, e, ins_node);
            findNode(T->rNode, e, ins_node);
        }
        return ERROR;
    }
    
    //在树的左节点插入
    status insertLight(BiTree &T, ElemType goal, ElemType data) { 
        if (T == NULL)
            return ERROR;
    
        BiTree tree = (BiTree) malloc(sizeof(BiTNode));
        tree->data = data;
        tree->lNode = NULL;
        tree->rNode = NULL;
    
        BiTree ins_node;
        findNode(T, goal, ins_node);//搜索节点
    
        ins_node->lNode = tree;
        return OK;
    }
    
    //在树的右节点插入
    status insertRight(BiTree &T, ElemType goal, ElemType data) { 
        if (T == NULL)
            return ERROR;
    
        BiTree tree = (BiTree) malloc(sizeof(BiTree));
        tree->data = data;
        tree->lNode = NULL;
        tree->rNode = NULL;
    
        BiTree ins_node;
        findNode(T, goal, ins_node);//搜索节点
    
        ins_node->rNode = tree;
        return OK;
    }
    
    //测试遍历方法
    int main() { 
        BiTree T;
        createTree(T, 'A');
        //A根左侧节点
        insertLight(T, 'A', 'B');
        insertRight(T,'B','C');
        insertLight(T,'C','D');
        insertRight(T,'C','E');
        //根右侧节点
        insertRight(T, 'A', 'F');
        insertRight(T,'A','F');
        insertRight(T,'F','G');
        insertLight(T,'G','H');
    
        printf("前:\t");
        preOrder(T);
        printf("\n");
    
        printf("中:\t");
        inOrder(T);
        printf("\n");
    
        printf("后:\t");
        postOrder(T);
        return 0;
    }

本文完.

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

> **想了解作者更多，请移步我的个人网站，欢迎交流、留言~**  
> **极客技术空间：[https://elltor.com/][https_elltor.com]**

[20200608182630763.png]: /images/20210920/ada1715fd37e4c4a8db6e75fb31c1e29.png
[https_elltor.com]: https://elltor.com/