c++设计算法将按顺序方式存储在数组中的二叉树转换为二叉链表形式。
以下是将按顺序方式存储在数组中的二叉树转换为二叉链表形式的C++算法:
#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
void convertToLinkedList(TreeNode* root, TreeNode*& prev) {
if (root == nullptr) {
return;
}
convertToLinkedList(root->left, prev);
// 将当前节点的左子树指向上一个节点
root->left = prev;
if (prev != nullptr) {
prev->right = root;
}
prev = root;
convertToLinkedList(root->right, prev);
}
TreeNode* convertToLinkedList(TreeNode* root) {
TreeNode* prev = nullptr;
convertToLinkedList(root, prev);
// 找到链表的头节点
while (root != nullptr && root->left != nullptr) {
root = root->left;
}
return root;
}
void printLinkedList(TreeNode* head) {
while (head != nullptr) {
std::cout << head->val << " ";
head = head->right;
}
std::cout << std::endl;
}
int main() {
// 创建二叉树
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(6);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(7);
// 转换为链表
TreeNode* head = convertToLinkedList(root);
// 打印链表
printLinkedList(head);
return 0;
}
这个算法使用了中序遍历的思想,首先将左子树转换为链表形式,然后将当前节点连接到上一个节点的右侧,最后将右子树转换为链表形式。转换后,返回链表的头节点并打印链表的值
原文地址: https://www.cveoy.top/t/topic/ixMW 著作权归作者所有。请勿转载和采集!