把二叉查找樹轉(zhuǎn)變成排序的雙向鏈表
例如：

轉(zhuǎn)換成雙向鏈表

4=6=8=10=12=14=16

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

首先闡述下二叉排序樹：

它首先要是一棵二元樹，在這基礎(chǔ)上它或者是一棵空樹；或者是具有下列性質(zhì)的二元樹： （1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值； （2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值； （3）左、右子樹也分別為二元查找樹

解決思路：

中序遍歷得到的即為排序好的鏈表順序，因此需要解決的就是指針的指向問題。

好吧，我首先想到的不是遍歷過程中修改指針指向（后來看別人代碼了......）

最開始的思路是在中序遍歷過程中左孩子要訪問當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)，因此中序遍歷過程中應(yīng)當(dāng)傳遞當(dāng)前節(jié)點(diǎn)和父節(jié)點(diǎn)。這就導(dǎo)致了root（根）節(jié)點(diǎn)與其他節(jié)點(diǎn)的處理方式不同。

后來想到既然中序遍歷是一個(gè)排序好的鏈表，那么遍歷過程中將當(dāng)前訪問節(jié)點(diǎn)的地址放入一個(gè)指針數(shù)組。遍歷結(jié)束后通過這個(gè)指針數(shù)組就可以方便的知道每個(gè)節(jié)點(diǎn)的前驅(qū)和后繼節(jié)點(diǎn)，再更改節(jié)點(diǎn)指向即可。

最后看到了別人的代碼，總結(jié)如下：

head指針指向鏈表表頭，index指針指向鏈表尾節(jié)點(diǎn)。

所有節(jié)點(diǎn)的左指針都指向前一節(jié)點(diǎn)，右指針都指向后一節(jié)點(diǎn)。

因此：（中間過程）

• 當(dāng)前節(jié)點(diǎn)的左指針指向表尾節(jié)點(diǎn)；
• 表尾節(jié)點(diǎn)的右指針指向當(dāng)前節(jié)點(diǎn)；
• 更新，尾節(jié)點(diǎn)指向當(dāng)前節(jié)點(diǎn)；

（對(duì)于表頭，即尾節(jié)點(diǎn)指向NULL）,初始化Head節(jié)點(diǎn)。

代碼如下：

void convertToDoubleList(BSTreeNode* pCurrent)
{
  pCurrent->m_pLeft=pIndex;
  if (pIndex == NULL)
  {
    pHead=pCurrent;
  }
  else
  {
    pIndex->m_pRight=pCurrent;
  }
  pIndex=pCurrent;
}

判斷倆個(gè)鏈表是否相交

給出倆個(gè)單向鏈表的頭指針，比如 h1，h2，判斷這倆個(gè)鏈表是否相交。

為了簡(jiǎn)化問題，我們假設(shè)倆個(gè)鏈表均不帶環(huán)。

問題擴(kuò)展：

如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列

鏈表定義

typedef struct node
{
  int data;
  struct node * next;
}List;

• 如果不帶環(huán)，那么分別遍歷兩個(gè)鏈表到尾節(jié)點(diǎn)；
• 若果兩個(gè)鏈表相交，那么尾節(jié)點(diǎn)一定相交；
• 如果兩個(gè)鏈表不相交，那么尾節(jié)點(diǎn)一定不相交；

int isJoinedNocylic(List * h1,List * h2)
{
  while(h1 != NULL)
    h1 = h1->next;
  while(h2 != NULL)
    h2 = h2->next;
   
  return h1 == h2;
}

如果需要求出倆個(gè)鏈表相交的第一個(gè)節(jié)點(diǎn)列？

網(wǎng)上看到了這樣的一個(gè)解法：設(shè)置兩個(gè)指針fast和slow，初始值都指向頭，slow每次前進(jìn)一步，fast每次前進(jìn)二步，如果鏈表存在環(huán)，則fast必定先進(jìn)入環(huán)，而slow后進(jìn)入環(huán)，兩個(gè)指針必定相遇。(當(dāng)然，fast先行頭到尾部為NULL，則為無環(huán)鏈表)，這樣就可以判斷兩個(gè)鏈表是否相交了，程序如下：

int isCycle(List * h)
{
  List * p1, * p2;
  p1 = p2 = h;
  int flag;
   
  while(p2 != NULL && p2->next != NULL)
  {
    p1 = p1->next;
    p2 = p2->next->next;
    if(p1 == p2)
    {  
      flag = 1;
      break;
    }
  }
   
  flag = 0; 
  return flag;
}

下面看看怎么找環(huán)的入口，當(dāng)fast與slow相遇時(shí)，slow肯定沒有走遍歷完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈(1<=n)。假設(shè)slow走了s步，則fast走了2s步（fast步數(shù)還等于s 加上在環(huán)上多轉(zhuǎn)的n圈），設(shè)環(huán)長為r，則：

2s = s + nr
s= nr

設(shè)整個(gè)鏈表長L，入口環(huán)與相遇點(diǎn)距離為x，起點(diǎn)到環(huán)入口點(diǎn)的距離為a。

a + x = nr
a + x = (n – 1)r +r = (n-1)r + L - a
a = (n-1)r + (L – a – x)

(L – a – x)為相遇點(diǎn)到環(huán)入口點(diǎn)的距離，由此可知，從鏈表頭到環(huán)入口點(diǎn)等于(n-1)循環(huán)內(nèi)環(huán)+相遇點(diǎn)到環(huán)入口點(diǎn)（從相遇點(diǎn)向后遍歷循環(huán)回到入口點(diǎn)的距離），于是我們從鏈表頭、與相遇點(diǎn)分別設(shè)一個(gè)指針，每次各走一步，兩個(gè)指針必定相遇，且相遇點(diǎn)為環(huán)入口點(diǎn)，也即為兩個(gè)鏈表的第一個(gè)相同節(jié)點(diǎn)。程序描述如下：

List * isJoined(List * h1,List * h2)
{
  List * ph1,*p1,*p2;
  int flag;
 
  ph1 = h1; 
  while(ph1->next != NULL)
    ph1 = ph1->next;  
  ph1->next = h2;
 
  if(0 == isCycle(h1))
  {
    flag = 0;
  }
  else
  {
    p1 = h1;
    while(p1 != p2)
    {
      p1 = p1->next;
      p2 = p2->next;
    }
    flag = p1;
  }
   
  return flag;
}

最新評(píng)論