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