假设二叉树中每个结点的值为单个字符,写一个将一棵以二叉链方式存储的二叉树b转换成对应的顺序存储结构a的代码
时间: 2023-06-07 15:12:17 浏览: 47
可以按照二叉树的中序遍历方式,将节点的值按照顺序存储到数组中,然后再遍历数组,构建对应的顺序存储结构。
代码示例(C++):
```C++
struct TreeNode{
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
void inorder(TreeNode* root, char* arr, int &pos){
if(root == NULL){
return;
}
inorder(root->left, arr, pos);
arr[pos++] = root->val;
inorder(root->right, arr, pos);
}
void createTree(TreeNode* &root){
char ch;
cin >> ch;
if(ch == '#'){ // '#' 表示空节点
root = NULL;
}
else{
root = new TreeNode(ch);
createTree(root->left);
createTree(root->right);
}
}
void convertToSequential(TreeNode* root, char* arr){
int pos = 0;
inorder(root, arr, pos);
TreeNode* p = root;
for(int i = 0; i < pos; i++){
p->val = arr[i];
if(i != pos - 1){
p->left = new TreeNode('#');
p = p->left;
}
else{
p->left = NULL;
}
}
}
int main(){
TreeNode* root;
createTree(root); // 输入二叉树
int nodeNum = 0;
inorder(root, NULL, nodeNum);
char* arr = new char[nodeNum];
convertToSequential(root, arr); // 将二叉树转换为顺序存储结构
// 输出顺序存储结构
for(int i = 0; i < nodeNum; i++){
cout << arr[i];
if(i != nodeNum - 1){
cout << "-";
}
}
return 0;
}
```
相关推荐
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)