將搜索二叉樹轉(zhuǎn)換為鏈表

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

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

Algorithm:

算法：

To solve the problem we can follow this algorithm:

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

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

我們開始從最右邊的樹節(jié)點到最左邊的樹節(jié)點將樹節(jié)點轉(zhuǎn)換為DLL。

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

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

Connect the left pointer of the DLL to that node.

將DLL的左指針連接到該節(jié)點。

Make that node to the head of the linked list.

使該節(jié)點位于鏈接列表的開頭。

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

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

C++ implementation:

C ++實現(xiàn)：

#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

將搜索二叉樹轉(zhuǎn)換為鏈表

總結(jié)

以上是生活随笔為你收集整理的将搜索二叉树转换为链表_将给定的二叉树转换为双链表（DLL）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。