第C++如何將二叉搜索樹轉(zhuǎn)換成雙向循環(huán)鏈表(雙指針或數(shù)組)目錄二叉搜索樹轉(zhuǎn)換成雙向循環(huán)鏈表二叉搜索樹與雙向鏈表(C++中等區(qū))解題思路代碼展示

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

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

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

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

2.從小到大訪問樹的節(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。

雙指針：

classSolution{

private:

Node*head,*pre=NULL;

public:

Node*treeToDoublyList(Node*root){//雙指針做法

if(!root)returnNULL;

inorder(root);

head-left=pre;

pre-right=head;

returnhead;

voidinorder(Node*root)

if(root==NULL)return;

inorder(root-left);

root-left=pre;

if(pre)

pre-right=root;

elsehead=root;

pre=root;

inorder(root-right);

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

Node*treeToDoublyList(Node*root){

if(!root)returnNULL;

vectorNode*nodelist;

inorder(nodelist,root);

intl=nodelist.size();

if(l==1)

nodelist[0]-right=nodelist[0];

nodelist[0]-left=nodelist[0];

returnnodelist[0];

for(inti=1;il-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];

returnnodelist[0];

voidinorder(vectorNode*nodelist,Node*root)

if(root==NULL)return;

inorder(nodelist,root-left);

nodelist.push_back(root);

inorder(nodelist,root-right);

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

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

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

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

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

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

解題思路

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

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

排序鏈表：節(jié)點(diǎn)應(yīng)從小到大排序，因此應(yīng)使用中序遍歷從小到大訪問樹的節(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。

代碼展示

代碼如下：

classSolution{

public:

Node*treeToDoublyList(Node*root){

if(!root)returnNULL;

mid(root);

//進(jìn)行頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的相互指向，這兩句的順序也是可以顛倒的

head-left=pre;

pre-right=head;

returnhead;

voidmid(Node*cur)

if(!cur)return;

mid(cur-left);

//pre用于記錄雙向鏈表中位于cur左側(cè)的節(jié)點(diǎn)，即上一次迭代中的cur,當(dāng)pre==null時(shí)，cur左側(cè)沒有節(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的操作。

elsepre-right=cur;

//pre是否為null對這句沒有影響,且這句放在上面兩句ifelse之前也是可以的。

cur-left=pre;

//pre指向當(dāng)前的cur

pre=cur;

//全部迭代完成后，pre指向雙向鏈表中的尾節(jié)點(diǎn)

mid(c