二叉树遍历C语言实现

一、二叉树遍历

这里不细说原理了，如果不懂原理，赶紧去找Googe Baidu吧！别让他们等太久了 🏃！ 接下来直接上代码了 GitHub

二、Code

typedef struct BinaryNode{
    char value;
    struct BinaryNode *lChild;
    struct BinaryNode *rChild;
}BinaryNode,*BinaryTree;

1.前序遍历

//前序遍历
//递归实现
void PreorderRecursionTraversal(BinaryTree T){
    if (NULL != T) {
        printf("%c ",T->value);
        PreorderRecursionTraversal(T->lChild);
        PreorderRecursionTraversal(T->rChild);
    }
}

//非递归实现
void PreorderTraversal(BinaryTree T){
    std::stack<BinaryTree> stack;
    BinaryTree p=T;
    while (NULL!=p || !stack.empty()) {
        if (NULL != p) {
            stack.push(p);
            printf("%c ",p->value);
            p=p->lChild;
        }else{
            p=stack.top();
            stack.pop();
            p=p->rChild;
        }
    }
}

2.中序遍历

//中序遍历
//递归实现
void InorderRecursionTraversal(BinaryTree T){
    if (NULL != T) {
        InorderRecursionTraversal(T->lChild);
        printf("%c ",T->value);
        InorderRecursionTraversal(T->rChild);
    }
}

//非递归实现
void InorderTraversal(BinaryTree T){
    std::stack<BinaryTree> stack;
    BinaryTree p=T;
    while (NULL!=p || !stack.empty()) {
        if (NULL != p) {
            stack.push(p);
            p=p->lChild;
        }else{
            p=stack.top();
            printf("%c ",p->value);
            stack.pop();
            p=p->rChild;
        }
    }
}

3.后序遍历

//后序遍历
//递归实现
void PostorderRecursionTraversal(BinaryTree T){
    if (NULL != T) {
        PostorderRecursionTraversal(T->lChild);
        PostorderRecursionTraversal(T->rChild);
        printf("%c ",T->value);
    }
}

//非递归实现(完全想不到思路，参考网上的)
typedef struct BinaryAuxiliaryNode{
    BinaryNode *node;
    char flag;
}BinaryAuxiliaryNode,*BinaryAuxiliaryTree;


void PostorderTraversal(BinaryTree T){
    std::stack<BinaryAuxiliaryTree> stack;
    BinaryTree p=T;
    BinaryAuxiliaryTree aTree;
    while (NULL!=p || !stack.empty()) {
        //遍历左子树
        while (NULL != p) {
            aTree=(BinaryAuxiliaryTree)malloc(sizeof(BinaryAuxiliaryNode));
            aTree->node=p;
            //访问过左子树
            aTree->flag='L';
            stack.push(aTree);
            p=p->lChild;
        }
        //左右子树访问完毕，访问根结点
        while (!stack.empty() && stack.top()->flag=='R') {
            aTree=stack.top();
            stack.pop();
            printf("%c ",aTree->node->value);
        }
        //遍历右子树
        if (!stack.empty()) {
            aTree=stack.top();
            //访问过右子树
            aTree->flag='R';
            p=aTree->node;
            p=p->rChild;
        }
    }
    
}

三、测试

四、总结

1. 其实二叉树的遍历，只有后续遍历的非递归实现复杂一些，其他的实现代码都很简洁。
2. 如果初学二叉树，可以拿出笔纸一步一步模拟代码的执行流程，写出遍历结果。
3. 还有一点想提的就是要学会运用辅助空间来解决问题，当然根据实际情况也有不同，比如程序由于某些因素限制（比如内存...），无法使用辅助空间