数据结构之二叉树的遍历算法合集先序遍历中序遍历层次遍历总结

摘要：今天用C撸了一遍数据中二叉树常见操作的实现，将实现过程中感觉有意思的几个功能实现记录下来方便以后复习～

先序遍历

递归实现

void PreOrderTraverse(BiTree biTree) {//先序遍历
    if (biTree == NULL) {
        cout << "该树为空，无法遍历！" << endl;
    }
    cout << biTree->data << " ";
    if (biTree->lchild != NULL) {
        PreOrderTraverse(biTree->lchild);
    }

    if (biTree->rchild != NULL) {
        PreOrderTraverse(biTree->rchild);
    }

}

非递归实现

void PreOrderTraverse2(BiTree biTree) {//先序遍历
    stack<BiNode *> stack1;
    BiNode *biNode = biTree;

    stack1.push(biNode);


    while (biNode != NULL && !stack1.empty()) {
        biNode = stack1.top();
        stack1.pop();
        cout << biNode->data << " ";

        if (biNode->rchild != NULL) {
            stack1.push(biNode->rchild);
        }

        if (biNode->lchild != NULL) {
            stack1.push(biNode->lchild);
        }
    }
}

中序遍历

递归实现

void InOrderTraverse(BiTree biTree) {
    if (biTree == NULL) {
        cout << "该树为空，无法遍历！" << endl;
    }

    if (biTree->lchild != NULL) {
        InOrderTraverse(biTree->lchild);
    }
    cout << biTree->data << " ";
    if (biTree->rchild != NULL) {
        InOrderTraverse(biTree->rchild);
    }
}

非递归实现

void InOrderTraverse2(BiTree biTree) {
    if (biTree == NULL) {
        cout << "该树为空，无法遍历！" << endl;
    }

    stack<BiNode *> stack1;
    BiNode *biNode = biTree;

    while (biNode != NULL || !stack1.empty()) {
        if (biNode != NULL) {
            stack1.push(biNode);
            biNode = biNode->lchild;
        } else {
            biNode = stack1.top();
            stack1.pop();
            cout << biNode->data << " ";
            biNode = biNode->rchild;
        }
    }
}

层次遍历

递归实现

二叉树Depth（）的实现

int Depth(BiTree biTree) {

    if (biTree == NULL) {
        return 0;
    }

    int u = Depth(biTree->lchild);
    int v = Depth(biTree->rchild);

    return u > v ? u   1 : v   1;
}

遍历实现

void LevelOrderTraverse(BiTree biTree) {
    for (int i = 1; i <= Depth(biTree);   i) {
        LevelOrderTraversePrint(biTree, i);
    }
}

void LevelOrderTraversePrint(BiTree biTree, int depth) {
    if (biTree == NULL) {
        cout << "该树为空，无法遍历！" << endl;
    }
    if (depth == 1) {
        cout << biTree->data << " ";
        return;
    } else {
        if (biTree->lchild != NULL) {
            LevelOrderTraversePrint(biTree->lchild, depth - 1);
        }


        if (biTree->rchild != NULL) {
            LevelOrderTraversePrint(biTree->rchild, depth - 1);
        }
    }
}

非递归实现

void PreOrderTraverse2(BiTree biTree) {//先序遍历

    stack<BiNode *> stack1;
    BiNode *biNode = biTree;

    stack1.push(biNode);

    while (biNode != NULL && !stack1.empty()) {
        biNode = stack1.top();
        stack1.pop();
        cout << biNode->data << " ";

        if (biNode->rchild != NULL) {
            stack1.push(biNode->rchild);
        }
        if (biNode->lchild != NULL) {
            stack1.push(biNode->lchild);
        }
    }
}

总结

遍历的时候使用非递归算法比采用递归算法的效率高效，但是同时非递归的算法实现比递归算法更难（除了层次遍历，个人觉得层次遍历的非递归实现反而比递归实现更简单）。

最后

以上就是大方蜡烛为你收集整理的数据结构之二叉树的遍历算法合集先序遍历中序遍历层次遍历总结的全部内容，希望文章能够帮你解决数据结构之二叉树的遍历算法合集先序遍历中序遍历层次遍历总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。