C++將二叉樹轉為雙向鏈表及斷定兩個鏈表能否訂交

C++將二叉樹轉為雙向鏈表及斷定兩個鏈表能否訂交。本站提示廣大學習愛好者：（C++將二叉樹轉為雙向鏈表及斷定兩個鏈表能否訂交）文章只能為提供參考，不一定能成為您想要的結果。以下是C++將二叉樹轉為雙向鏈表及斷定兩個鏈表能否訂交正文

把二叉查找樹改變成排序的雙向鏈表
例如：

轉換成雙向鏈表

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
};

起首論述下二叉排序樹：

它起首如果一棵二元樹，在這基本上它或許是一棵空樹；或許是具有以下性質的二元樹： （1）若左子樹不空，則左子樹上一切結點的值均小於它的根結點的值； （2）若右子樹不空，則右子樹上一切結點的值均年夜於它的根結點的值； （3）左、右子樹也分離為二元查找樹

處理思緒：

中序遍歷獲得的即為排序好的鏈表次序，是以須要處理的就是指針的指向成績。

好吧，我起首想到的不是遍歷進程中修正指針指向（後來看他人代碼了......）

最開端的思緒是在中序遍歷進程中左孩子要拜訪以後節點的父節點，是以中序遍歷進程中應該傳遞以後節點和父節點。這就招致了root（根）節點與其他節點的處置方法分歧。

後來想到既然中序遍歷是一個排序好的鏈表，那末遍歷進程中將以後拜訪節點的地址放入一個指針數組。遍歷停止後經由過程這個指針數組便可以便利的曉得每一個節點的先驅和後繼節點，再更改節點指向便可。

最初看到了他人的代碼，總結以下：

head指針指向鏈表表頭，index指針指向鏈表尾節點。

一切節點的左指針都指向前一節點，右指針都指向後一節點。

是以：（中央進程）

• 以後節點的左指針指向表尾節點；
• 表尾節點的右指針指向以後節點；
• 更新，尾節點指向以後節點；

（關於表頭，即尾節點指向NULL）,初始化Head節點。

代碼以下：

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

斷定倆個鏈表能否訂交

給出倆個單向鏈表的頭指針，好比 h1，h2，斷定這倆個鏈表能否訂交。

為了簡化成績，我們假定倆個鏈表均不帶環。

成績擴大：

假如須要求出倆個鏈表訂交的第一個節點列

鏈表界說

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

• 假如不帶環，那末分離遍歷兩個鏈表到尾節點；
• 若果兩個鏈表訂交，那末尾節點必定訂交；
• 假如兩個鏈表不訂交，那末尾節點必定不訂交；

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

假如須要求出倆個鏈表訂交的第一個節點列？

網上看到了如許的一個解法：設置兩個指針fast和slow，初始值都指向頭，slow每次進步一步，fast每次進步二步，假如鏈表存在環，則fast一定先輩入環，而slow落後入環，兩個指針一定相遇。(固然，fast先行頭到尾部為NULL，則為無環鏈表)，如許便可以斷定兩個鏈表能否訂交了，法式以下：

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;
}

上面看看怎樣找環的進口，當fast與slow相遇時，slow確定沒有走遍歷完鏈表，而fast曾經在環內輪回了n圈(1<=n)。假定slow走了s步，則fast走了2s步（fast步數還等於s 加上在環上多轉的n圈），設環長為r，則：

2s = s + nr
s= nr

設全部鏈表長L，進口環與相遇點間隔為x，終點到環進口點的間隔為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)為相遇點到環進口點的間隔，由此可知，從鏈表頭到環進口點等於(n-1)輪回內環+相遇點到環進口點（從相遇點向後遍歷輪回回到進口點的間隔），因而我們從鏈表頭、與相遇點分離設一個指針，每次各走一步，兩個指針一定相遇，且相遇點為環進口點，也即為兩個鏈表的第一個雷同節點。法式描寫以下：

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;
}