將搜索二叉樹轉換為鏈表

Given a Binary tree and we have to convert it to a Doubly Linked List (DLL).

給定二叉樹，我們必須將其轉換為雙鏈表(DLL)。

Algorithm:

算法：

To solve the problem we can follow this algorithm:

為了解決這個問題，我們可以遵循以下算法：

1. We start to convert the tree node to DLL from the rightmost tree node to the leftmost tree node.

   我們開始從最右邊的樹節點到最左邊的樹節點將樹節點轉換為DLL。

2. Every time we connect the right pointer of a node to the head of the DLL.

   每次我們將節點的右指針連接到DLL的頭時。

3. Connect the left pointer of the DLL to that node.

   將DLL的左指針連接到該節點。

4. Make that node to the head of the linked list.

   使該節點位于鏈接列表的開頭。

5. Repeat the process from right to left most node of the tree.

   從樹的最右端到最左端重復該過程。

C++ implementation:

C ++實現：

#include <bits/stdc++.h>
using namespace std;
struct node {
int data;
node* left;
node* right;
};
//Create a new node
struct node* create_node(int x)
{
struct node* temp = new node;
temp->data = x;
temp->left = NULL;
temp->right = NULL;
return temp;
}
//convert a BST to a DLL
void BinarytoDll(node* root, node** head)
{
if (root == NULL)
return;
BinarytoDll(root->right, head);
root->right = *head;
if (*head != NULL) {
(*head)->left = root;
}
*head = root;
BinarytoDll(root->left, head);
}
//Print the list
void print(node* head)
{
struct node* temp = head;
while (temp) {
cout << temp->data << " ";
temp = temp->right;
}
}
//print the tree in inorder traversal
void print_tree(node* root)
{
if (root == NULL) {
return;
}
print_tree(root->left);
cout << root->data << " ";
print_tree(root->right);
}
int main()
{
struct node* root = create_node(5);
root->left = create_node(6);
root->right = create_node(7);
root->left->left = create_node(8);
root->left->right = create_node(1);
root->right->right = create_node(0);
cout << "Print Tree" << endl;
print_tree(root);
struct node* head = NULL;
BinarytoDll(root, &head);
cout << "\nDoubly Linked List" << endl;
print(head);
return 0;
}

Output

輸出量

Print Tree
8 6 1 5 7 0
Doubly Linked List
8 6 1 5 7 0

翻譯自: https://www.includehelp.com/cpp-programs/convert-a-given-binary-tree-to-doubly-linked-list-dll.aspx

將搜索二叉樹轉換為鏈表