利用#号法来创建二叉树
输入:
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); }