ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมเพื่อแปลงไบนารีทรีเป็นรายการที่เชื่อมโยงเป็นสองเท่า
สำหรับสิ่งนี้เราจะได้รับไบนารีทรี งานของเราคือการแปลงเป็นรายการที่เชื่อมโยงแบบทวีคูณเพื่อให้ตัวชี้ซ้ายและขวากลายเป็นตัวชี้ก่อนหน้าและถัดไป นอกจากนี้ ลำดับของรายการที่เชื่อมโยงแบบทวีคูณจะต้องเท่ากับการข้ามผ่านที่ไม่เป็นระเบียบของไบนารีทรี
สำหรับสิ่งนี้เรากำลังมีแนวทางที่แตกต่างออกไป เราจะข้ามต้นไม้ไบนารีในทางที่กลับกันไม่เรียงลำดับ เราจะสร้างโหนดใหม่และย้ายตัวชี้ส่วนหัวไปเป็นโหนดล่าสุด สิ่งนี้จะสร้างรายการที่เชื่อมโยงเป็นสองเท่าตั้งแต่ต้นจนจบ
ตัวอย่าง
#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
