คำอธิบายปัญหา
ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง binary tree เป็น doubly linked list
สำหรับนี้ เราจะได้รับ binary tree งานของเราคือแปลงมันเป็น doubly linked list โดยที่ pointer ซ้ายและขวาจะกลายเป็น previous และ next pointers ตามลำดับ ลำดับลำดับของ doubly linked list ต้องเท่ากับ inorder traversal ของ binary tree
สำหรับนี้ เรามีวิธีการที่แตกต่าง เราจะเดินทาง (traverse) binary tree แบบ reverse inorder พร้อมกับเราจะสร้างโหนดใหม่และย้าย head pointer ไปที่โหนดล่าสุด ซึ่งจะสร้าง doubly linked list จากท้ายไปหัว
ตัวอย่างโค้ด
#include <stdio.h> #include <stdlib.h> //node structure for tree struct Node{ int data; Node *left, *right; }; //converting the binary tree to //doubly linked list void binary_todll(Node* root, Node** head_ref){ if (root == NULL) return; //converting right subtree binary_todll(root->right, head_ref); //inserting the root value to the //doubly linked list root->right = *head_ref; //moving the head pointer if (*head_ref != NULL) (*head_ref)->left = root; *head_ref = root; //converting left subtree binary_todll(root->left, head_ref); } //allocating new node for doubly linked list Node* newNode(int data){ Node* node = new Node; node->data = data; node->left = node->right = NULL; return node; } //printing doubly linked list void print_dll(Node* head){ printf("Doubly Linked list:\n"); while (head) { printf("%d ", head->data); head = head->right; } } int main(){ Node* root = newNode(5); root->left = newNode(3); root->right = newNode(6); root->left->left = newNode(1); root->left->right = newNode(4); root->right->right = newNode(8); root->left->left->left = newNode(0); root->left->left->right = newNode(2); root->right->right->left = newNode(7); root->right->right->right = newNode(9); Node* head = NULL; binary_todll(root, &head); print_dll(head); return 0; }ผลลัพธ์
Doubly Linked list: 0 1 2 3 4 5 6 7 8 9
