คำอธิบายปัญหา
ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมแปลง binary tree เป็น doubly linked list
สำหรับนี้ เราจะได้รับ binary tree งานของเราคือแปลงมันเป็น doubly linked list โดยที่ pointer ซ้ายและขวาจะกลายเป็น previous และ next pointers ตามลำดับ ลำดับของ doubly linked list ต้องเท่ากับ inorder traversal ของ binary tree
สำหรับนี้ เรามีวิธีการที่ตรงไปตรงมา เราจะเดินทาง (traverse) binary tree แบบ inorder ทำให้โหนดของ doubly linked list ไปพร้อมกัน และสุดท้ายทำให้ left และ right กลายเป็น previous และ next nodes ตามลำดับ
ตัวอย่างโค้ด
#include <iostream> using namespace std; //node structure of binary tree struct node{ int data; node* left; node* right; }; //traversing and making nodes for //doubly linked list void binarytodll(node *root, node **head){ if (root == NULL) return; static node* prev = NULL; //converting left subtree binarytodll(root->left, head); if (prev == NULL) *head = root; else { root->left = prev; prev->right = root; } prev = root; //converting right subtree binarytodll(root->right, head); } //allocating a new node node* newNode(int data) { node* new_node = new node; new_node->data = data; new_node->left = new_node->right = NULL; return (new_node); } //printing nodes of doubly linked list void print_dll(node *node){ while (node!=NULL) { cout << node->data << " "; node = node->right; } } int main(){ node *root = newNode(10); root->left = newNode(12); root->right = newNode(15); root->left->left = newNode(25); root->left->right = newNode(30); root->right->left = newNode(36); node *head = NULL; binarytodll(root, &head); print_dll(head); return 0; }ผลลัพธ์
25 12 30 10 36 15
