四、若將下圖當作樹，請分別用陣列與鏈結串列（Linked List）的方式來表示。 （20 分）

// Define the structure for a tree node
struct TreeNode {
int value;
TreeNode *left;
TreeNode *right;

TreeNode(int val) : value(val), left(nullptr), right(nullptr) {}
};

int main() {
// Create nodes as per the tree in the image
TreeNode *root = new TreeNode(1);

TreeNode *node2 = new TreeNode(2);
TreeNode *node3 = new TreeNode(3);
TreeNode *node4 = new TreeNode(4);
TreeNode *node5 = new TreeNode(5);
TreeNode *node6 = new TreeNode(6);

// Connect the nodes
root->left = node2;
root->right = node3;

node2->left = node4;

node3->right = node5;

node4->left = node6;

// The tree is now represented in memory as per the image

// Cleanup: Since we’re using raw pointers, we’ll need to manually deallocate memory.
// Note: In a real-world application, consider using smart pointers for better memory management.
delete root;
delete node2;
delete node3;
delete node4;
delete node5;
delete node6;

return 0;
}

index:   1  2  3  4  5  6
value:  [1, 2, 3, 4, 5, 6]