快捷導(dǎo)航

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

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

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

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

在這里插入圖片描述

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

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

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

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

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

3.循環(huán)鏈表：設(shè)鏈表頭節(jié)點(diǎn) head 和尾節(jié)點(diǎn) 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ǎn)單就不做介紹了，就是先把節(jié)點(diǎn)都放進(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);
    }

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

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

為了讓您更好地理解問(wèn)題，以下面的二叉搜索樹(shù)為例：

在這里插入圖片描述

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

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

在這里插入圖片描述

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

解題思路

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

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

排序鏈表：節(jié)點(diǎn)應(yīng)從小到大排序，因此應(yīng)使用中序遍歷 “從小到大”訪問(wèn)樹(shù)的節(jié)點(diǎn)；
雙向鏈表：在構(gòu)建相鄰節(jié)點(diǎn)（設(shè)前驅(qū)節(jié)點(diǎn) pre ，當(dāng)前節(jié)點(diǎn) cur ）關(guān)系時(shí)，不僅應(yīng) pre.right =cur，也應(yīng) cur.left = pre 。
循環(huán)鏈表：設(shè)鏈表頭節(jié)點(diǎn) head 和尾節(jié)點(diǎn) 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é)點(diǎn)和尾節(jié)點(diǎn)的相互指向，這兩句的順序也是可以顛倒的
        head->left=pre;
        pre->right=head;
        return head;
    }
    void mid(Node* cur)
    {
        if(!cur) return;
        mid(cur->left);
        //pre用于記錄雙向鏈表中位于cur左側(cè)的節(jié)點(diǎn)，即上一次迭代中的cur,當(dāng)pre==null時(shí)，cur左側(cè)沒(méi)有節(jié)點(diǎn),即此時(shí)cur為雙向鏈表中的頭節(jié)點(diǎn)
        if(pre==NULL) head=cur;
        //反之，pre!=null時(shí)，cur左側(cè)存在節(jié)點(diǎn)pre，需要進(jìn)行pre.right=cur的操作。
        else pre->right=cur;
        //pre是否為null對(duì)這句沒(méi)有影響,且這句放在上面兩句if else之前也是可以的。
        cur->left=pre;
        //pre指向當(dāng)前的cur
        pre=cur;
        //全部迭代完成后，pre指向雙向鏈表中的尾節(jié)點(diǎn)
        mid(cur->right);
    }
private:
    Node* head,*pre;
};