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 rất thẳng thắn. Chúng tôi sẽ duyệt qua cây nhị phân theo thứ tự tạo các nút của danh sách được liên kết kép cùng với và cuối cùng làm cho bên trái và bên phải lần lượt là các nút trước đó và tiếp theo.
Ví dụ
#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;
} Đầu ra
25 12 30 10 36 15