井号法(#)创建二叉树(利用前序遍历来建树)C++实现

简介: 井号法(#)创建二叉树(利用前序遍历来建树)C++实现

利用#号法来创建二叉树

输入:

ABD##E##C#F##

对应该输入的二叉树应为这样

解题思路:

vector数组存储输入的节点数据

用前序遍历的顺序去建树

如果是#,则表明该节点为空

否则先创建左子树,然后右子树

递归调用

代码:

/**
 *作者:魏宝航
 *2020年11月26日,下午23:55
 */
#include<iostream>
#include<vector>
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);
}
int main() {
    int n;
    cin >> n;
    vector<char> v;
    for (int i = 0; i < n; i++) {
        char ch;
        cin >> ch;
        v.push_back(ch);
    }
    Node* root=new Node();
    root=CreateTree(v,root);
    preOrder(root); 
}


目录
相关文章
|
6月前
|
C++
二叉树进阶面试题(精华总结)【C++版本】
二叉树进阶面试题(精华总结)【C++版本】
|
6月前
|
存储 编译器 数据库
【C/C++ 数据结构 】线索二叉树全解析:从数学原理到C++实现
【C/C++ 数据结构 】线索二叉树全解析:从数学原理到C++实现
127 0
|
4月前
|
存储 C++
【C++】二叉树进阶之二叉搜索树(下)
【C++】二叉树进阶之二叉搜索树(下)
32 4
|
4月前
|
Java 编译器 C++
【C++】二叉树进阶之二叉搜索树(上)
【C++】二叉树进阶之二叉搜索树(上)
35 3
|
4月前
|
算法 C++
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
【C++高阶】高效搜索的秘密:深入解析搜索二叉树
40 2
|
6月前
|
存储 C++
【C++】二叉树进阶 -- 详解
【C++】二叉树进阶 -- 详解
|
6月前
|
存储 算法 数据管理
C++中利用随机策略优化二叉树操作效率的实现方法
C++中利用随机策略优化二叉树操作效率的实现方法
112 1
|
6月前
|
存储 C++
【C++练级之路】【Lv.14】二叉搜索树(进化的二叉树——BST)
【C++练级之路】【Lv.14】二叉搜索树(进化的二叉树——BST)
【C++练级之路】【Lv.14】二叉搜索树(进化的二叉树——BST)
|
6月前
|
存储 C++
二叉树的操作(C++实现)
二叉树的操作(C++实现)
|
6月前
|
算法 C++ 开发者
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
【C/C++ 数据结构 】二叉树基本性质:具有n个结点的完全二叉树的深度为[log2n]+1或者[log2(n+1)]...
84 0