假设二叉树的结点值是字符,根据输入的一棵二叉树的扩展先序遍历序列建立一棵以二叉链表表示的二叉树
时间: 2024-01-23 16:43:47 浏览: 87
二叉树的扩展先序遍历序列是指按照先序遍历的顺序,如果一个结点没有左子树,则在该结点后面加上一个特殊字符(如'#'),表示该结点的左子树为空;如果一个结点没有右子树,则在该结点后面加上一个特殊字符(如'#'),表示该结点的右子树为空。例如,对于下面的二叉树:
```
A
/ \
B C
/ \
D E
```
它的扩展先序遍历序列为:AB##CDE###
根据扩展先序遍历序列建立二叉树的过程可以采用递归的方式,具体步骤如下:
1. 如果遇到一个特殊字符(如'#'),则返回空指针(表示该子树为空);
2. 否则,创建一个新的结点,并将当前字符赋值给该结点的值;
3. 递归调用函数,创建该结点的左子树(参数为扩展先序遍历序列的下一个字符);
4. 递归调用函数,创建该结点的右子树(参数为扩展先序遍历序列的下一个字符);
5. 返回该结点的指针。
根据上述步骤,可以编写如下的代码:
```C++
#include <iostream>
#include <string>
using namespace std;
class TreeNode {
public:
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
class BinaryTree {
public:
TreeNode* buildTree(string s) {
int i = 0;
return buildTreeHelper(s, i);
}
private:
TreeNode* buildTreeHelper(string s, int& i) {
if (i >= s.size() || s[i] == '#') {
i++;
return NULL;
}
TreeNode* root = new TreeNode(s[i++]);
root->left = buildTreeHelper(s, i);
root->right = buildTreeHelper(s, i);
return root;
}
};
int main() {
string s = "AB##CDE###";
BinaryTree bt;
TreeNode* root = bt.buildTree(s);
return 0;
}
```
在上述代码中,buildTree函数接受一个扩展先序遍历序列的字符串作为参数,返回一个指向根结点的指针。buildTreeHelper是递归函数,它根据扩展先序遍历序列创建二叉树。在main函数中,我们使用扩展先序遍历序列"AB##CDE###"创建了一棵二叉树,并将根结点的指针保存在root变量中。
阅读全文