C++如何將二叉搜索樹轉(zhuǎn)換成雙向循環(huán)鏈表(雙指針或數(shù)組)

更新時間：2022年05月12日 15:09:44 作者：秦楓-_-

這篇文章主要介紹了C++如何將二叉搜索樹轉(zhuǎn)換成雙向循環(huán)鏈表(雙指針或數(shù)組)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教

二叉搜索樹轉(zhuǎn)換成雙向循環(huán)鏈表

在這里插入圖片描述

本文解法基于性質(zhì)：二叉搜索樹的中序遍歷為遞增序列。

將二叉搜索樹轉(zhuǎn)換成一個 “排序的循環(huán)雙向鏈表”，其中包含三個要素：

1.排序鏈表：節(jié)點應(yīng)從小到大排序，因此應(yīng)使用中序遍歷

2.“從小到大”訪問樹的節(jié)點。雙向鏈表：在構(gòu)建相鄰節(jié)點的引用關(guān)系時，設(shè)前驅(qū)節(jié)點 pre 和當(dāng)前節(jié)點 cur ，

不僅應(yīng)構(gòu)建 pre.right= cur，也應(yīng)構(gòu)建 cur.left = pre 。

3.循環(huán)鏈表：設(shè)鏈表頭節(jié)點 head 和尾節(jié)點 tail，則應(yīng)構(gòu)建 head.left = tail 和 tail.right = head 。

雙指針：

class Solution {
private:
    Node* head, * pre = NULL;
public:
    Node* treeToDoublyList(Node* root) {//雙指針做法
        if (!root) return NULL;
        inorder(root);
        head->left = pre;
        pre->right = head;
        return head;
    }
    void inorder(Node* root)
    {
        if (root == NULL)return;
        inorder(root->left);
        root->left = pre;
        if (pre)
            pre->right = root;
        else head = root;
        pre = root;
        inorder(root->right);
    }
};

數(shù)組方法：很簡單就不做介紹了，就是先把節(jié)點都放進(jìn)數(shù)組然后在建立聯(lián)系。

Node* treeToDoublyList(Node* root) {
        if (!root) return NULL;
        vector<Node*> nodelist;
        inorder(nodelist, root);
        int l = nodelist.size();
        if (l == 1)
        {
            nodelist[0]->right = nodelist[0];
            nodelist[0]->left = nodelist[0];
            return nodelist[0];
        }
        for (int i = 1; i < l - 1; i++) {
            nodelist[i]->left = nodelist[i - 1];
            nodelist[i]->right = nodelist[i + 1];
        }
        nodelist[0]->left = nodelist[l - 1];
        nodelist[0]->right = nodelist[1];
        nodelist[l - 1]->right = nodelist[0];
        nodelist[l - 1]->left = nodelist[l - 2];
        return nodelist[0];
    }
    void inorder(vector<Node*>& nodelist, Node* root)
    {
        if (root == NULL)return;
        inorder(nodelist, root->left);
        nodelist.push_back(root);
        inorder(nodelist, root->right);
    }

二叉搜索樹與雙向鏈表(C++中等區(qū))

題目：輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的循環(huán)雙向鏈表。要求不能創(chuàng)建任何新的節(jié)點，只能調(diào)整樹中節(jié)點指針的指向。

為了讓您更好地理解問題，以下面的二叉搜索樹為例：

在這里插入圖片描述

我們希望將這個二叉搜索樹轉(zhuǎn)化為雙向循環(huán)鏈表。鏈表中的每個節(jié)點都有一個前驅(qū)和后繼指針。對于雙向循環(huán)鏈表，第一個節(jié)點的前驅(qū)是最后一個節(jié)點，最后一個節(jié)點的后繼是第一個節(jié)點。

下圖展示了上面的二叉搜索樹轉(zhuǎn)化成的鏈表。“head” 表示指向鏈表中有最小元素的節(jié)點。

在這里插入圖片描述

特別地，我們希望可以就地完成轉(zhuǎn)換操作。當(dāng)轉(zhuǎn)化完成以后，樹中節(jié)點的左指針需要指向前驅(qū)，樹中節(jié)點的右指針需要指向后繼。還需要返回鏈表中的第一個節(jié)點的指針。

解題思路

本文解法基于性質(zhì)：二叉搜索樹的中序遍歷為遞增序列。

將二叉搜索樹轉(zhuǎn)換成一個 “排序的循環(huán)雙向鏈表” ，其中包含三個要素：

排序鏈表：節(jié)點應(yīng)從小到大排序，因此應(yīng)使用中序遍歷 “從小到大”訪問樹的節(jié)點；
雙向鏈表：在構(gòu)建相鄰節(jié)點（設(shè)前驅(qū)節(jié)點 pre ，當(dāng)前節(jié)點 cur ）關(guān)系時，不僅應(yīng) pre.right =cur，也應(yīng) cur.left = pre 。
循環(huán)鏈表：設(shè)鏈表頭節(jié)點 head 和尾節(jié)點 tail ，則應(yīng)構(gòu)建 head.left = tail，和 tail.right = head 。

在這里插入圖片描述

代碼展示

代碼如下：

class Solution {
public:
    Node* treeToDoublyList(Node* root) {
        if(!root) return NULL;
        mid(root);
        //進(jìn)行頭節(jié)點和尾節(jié)點的相互指向，這兩句的順序也是可以顛倒的
        head->left=pre;
        pre->right=head;
        return head;
    }
    void mid(Node* cur)
    {
        if(!cur) return;
        mid(cur->left);
        //pre用于記錄雙向鏈表中位于cur左側(cè)的節(jié)點，即上一次迭代中的cur,當(dāng)pre==null時，cur左側(cè)沒有節(jié)點,即此時cur為雙向鏈表中的頭節(jié)點
        if(pre==NULL) head=cur;
        //反之，pre!=null時，cur左側(cè)存在節(jié)點pre，需要進(jìn)行pre.right=cur的操作。
        else pre->right=cur;
        //pre是否為null對這句沒有影響,且這句放在上面兩句if else之前也是可以的。
        cur->left=pre;
        //pre指向當(dāng)前的cur
        pre=cur;
        //全部迭代完成后，pre指向雙向鏈表中的尾節(jié)點
        mid(cur->right);
    }
private:
    Node* head,*pre;
};