Trong hướng dẫn này, chúng ta sẽ thảo luận về một chương trình để chuyển đổi một cây nhị phân thành một danh sách được liên kết kép.
Đối với điều này, chúng tôi sẽ được cung cấp một cây nhị phân. Nhiệm vụ của chúng ta là chuyển đổi nó thành một danh sách được liên kết kép sao cho các con trỏ trái và phải trở thành các con trỏ trước đó và tiếp theo. Ngoài ra, thứ tự tuần tự của danh sách được liên kết kép phải bằng với thứ tự truyền tải nhỏ hơn của cây nhị phân.
Đối với điều này, chúng tôi đang có một cách tiếp cận khác. Chúng ta sẽ duyệt qua cây nhị phân theo cách ngược lại. Cùng với đó, chúng tôi sẽ tạo các nút mới và di chuyển con trỏ đầu đến nút mới nhất; điều này sẽ tạo ra danh sách được liên kết kép từ cuối đến đầu.
Ví dụ
#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;
} Đầu ra
Doubly Linked list: 0 1 2 3 4 5 6 7 8 9