欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

二叉树的四种遍历方式(前序遍历,中序遍历,后序遍历,层序遍历)C++语言

程序员文章站 2024-03-22 19:00:04
...

不要自卑,去提升实力
互联网行业谁技术牛谁是爹
如果文章可以带给你能量,那是最好的事!请相信自己
加油o~

1、前序,中序,后序

原理差不多,利用递归,只是各自的相对顺序不同而已

2、层序遍历

用了广度优先遍历
用队列去存储根节点
只要根节点的左孩子和右孩子不为空,继续入队
然后将根节点出队
直到队列中无元素为止
出队顺序即为层序遍历顺序

代码:

/**
 *作者:魏宝航
 *2020年11月27日,下午15:08
 */
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class Node {
public:
    char ch;
    Node* left;
    Node* right;
    Node() {
        ch = '\0';
        left = NULL;
        right = NULL;
    }
    Node(char ch, Node* left, Node* right) {
        this->ch = ch;
        this->left = left;
        this->right = right;
    }
};
static int i = 0;
//#号法创建二叉树
Node* CreateTree(vector<char> arr,Node* root) {
    if (i < arr.size()) {
        char temp = arr[i++];
        if (temp == '#') {
            return NULL;
        }
        else {
            root = new Node();
            root->ch = temp;
            root->left = CreateTree(arr, root->left);
            root->right = CreateTree(arr, root->right);
        }
    }
    return root;
}
//二叉树的前序遍历
void preOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    cout << root->ch << " ";
    preOrder(root->left);
    preOrder(root->right);
}
//二叉树的中序遍历
void midOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    midOrder(root->left);
    cout << root->ch << " ";
    midOrder(root->right);
}
//二叉树的后序遍历
void postOrder(Node* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    cout << root->ch << " ";
}
//二叉树的层序遍历
void levelOrder(Node* root) {
    queue<Node*> q;
    q.push(root);
    while (!q.empty()) {
        Node* temp = q.front();
        cout << temp->ch << " ";
        q.pop();
        if (temp->left != NULL) {
            q.push(temp->left);
        }
        if (temp->right != NULL) {
            q.push(temp->right);
        }
    }
}
int main() {
    vector<char> v;
    char arr[] = { 'A','B','D','#','#','E','#','#','C','#','F','#','#' };
    char arr1[] = { '#' };
    for (int i = 0; i < 13; i++) {
        v.push_back(arr[i]);
    }
    Node* root=new Node();
    root=CreateTree(v,root);
    preOrder(root);
    midOrder(root);
    postOrder(root);
    levelOrder(root);
}