一波C語(yǔ)言二元查找樹(shù)算法題目解答實(shí)例匯總

更新時(shí)間：2016年03月15日 15:42:02 作者：wuzhekai1985

這篇文章主要介紹了一波C語(yǔ)言二元查找樹(shù)算法題目解答實(shí)例匯總,包括按層次遍歷和轉(zhuǎn)換為鏡像等基本算法題目,需要的朋友可以參考下

按層次遍歷二元樹(shù)
問(wèn)題描述：輸入一顆二元樹(shù)，從上往下按層打印樹(shù)的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
例如輸入：

輸出

8 6 10 5 7 9 11

定義二元樹(shù)（其實(shí)是二元搜索樹(shù)，但并不遍歷算法）的結(jié)點(diǎn)為：

struct BSTreeNode 
{ 
 int value; 
 BSTreeNode *left; 
 BSTreeNode *right; 
};

思路：利用隊(duì)列的先進(jìn)先出，很容易實(shí)現(xiàn)。每次取出隊(duì)列的首元素，然后將其左右子女放入隊(duì)列中。直至隊(duì)列為空即可。按這種方式進(jìn)出隊(duì)列，正好是按層遍歷二元樹(shù)。
參考代碼：

//函數(shù)功能 ： 按層次遍歷二元樹(shù) 
//函數(shù)參數(shù) ： pRoot指向根結(jié)點(diǎn) 
//返回值 ： 無(wú) 
void LevelReverse(BSTreeNode *pRoot) 
{ 
 if(pRoot == NULL) 
  return; 
 
 queue<BSTreeNode *> nodeQueue; 
 nodeQueue.push(pRoot); 
 while(nodeQueue.size()) 
 { 
  BSTreeNode * pNode = nodeQueue.front(); //取隊(duì)首元素 
  nodeQueue.pop(); //必須出隊(duì)列 
  if(pNode->left) //左子女 
   nodeQueue.push(pNode->left); 
  if(pNode->right) //右子女 
   nodeQueue.push(pNode->right); 
 
  cout<<pNode->value<<' '; 
 } 
}

       擴(kuò)展一：上文給出的代碼，所有結(jié)點(diǎn)都輸出在同一行。如果希望僅僅同層結(jié)點(diǎn)輸出在同一行，該如何修改代碼呢？
       思路：如果我們能知道每層的最后一個(gè)結(jié)點(diǎn)，那么就方便多了，輸出每層最后一個(gè)結(jié)點(diǎn)的同時(shí)，輸出一個(gè)換行符。因此，關(guān)鍵在于如何標(biāo)記每層的結(jié)束。可以考慮在每層的最后一個(gè)點(diǎn)之后，插入一個(gè)空結(jié)點(diǎn)。比如隊(duì)列中先放入根結(jié)點(diǎn)，由于第0層只有一個(gè)結(jié)點(diǎn)，因此放入一個(gè)空結(jié)點(diǎn)。然后依次取出隊(duì)列中的結(jié)點(diǎn)，將其子女放入隊(duì)列中，如果遇到空結(jié)點(diǎn)，表明當(dāng)前層的結(jié)點(diǎn)已遍歷完了，而隊(duì)列中放的恰恰是下一層的所有結(jié)點(diǎn)。如果當(dāng)前隊(duì)列為空，表明下一層無(wú)結(jié)點(diǎn)，也就說(shuō)是所有結(jié)點(diǎn)已遍歷好了。如果不為空，那么插入一個(gè)空結(jié)點(diǎn)，用于標(biāo)記下一層的結(jié)束。
      參考代碼：

void LevelReverse(BSTreeNode *pRoot) 
{ 
 if(pRoot == NULL) 
  return; 
 queue<BSTreeNode *> nodeQueue; 
 nodeQueue.push(pRoot); 
 nodeQueue.push(NULL); //放入空結(jié)點(diǎn)，作為層的結(jié)束符 
 while(nodeQueue.size()) 
 { 
  BSTreeNode * pNode = nodeQueue.front(); //取隊(duì)首元素 
  nodeQueue.pop(); //必須出隊(duì)列 
  if(pNode) 
  { 
   if(pNode->left) //左子女 
    nodeQueue.push(pNode->left); 
   if(pNode->right) //右子女 
    nodeQueue.push(pNode->right); 
   cout<<pNode->value<<' '; 
  } 
  else if(nodeQueue.size()) //如果結(jié)點(diǎn)為空并且隊(duì)列也為空，那么所有結(jié)點(diǎn)都已訪問(wèn) 
  { 
   nodeQueue.push(NULL); 
   cout<<endl; 
  } 
 } 
}

擴(kuò)展二：之前討論的都是從上往下、從左往右遍歷二叉樹(shù)，那么如果希望自下往上、從左右往右遍歷二叉樹(shù)，該如何修改代碼呢？
思路：比較簡(jiǎn)單的方法，首先遍歷二叉樹(shù)，將所有結(jié)點(diǎn)保存在一個(gè)數(shù)組中，遍歷的同時(shí)記錄每一層在數(shù)組中的起止位置。然后根據(jù)起止位置，就可以自下往上的打印二叉樹(shù)的結(jié)點(diǎn)。

//每層的起止位置 
struct Pos 
{ 
 int begin; 
 int end; 
 Pos(int b, int e): begin(b),end(e) {} 
}; 
void LevelReverse(BSTreeNode *pRoot) 
{ 
 if(pRoot == NULL) 
  return; 
 
 vector<BSTreeNode*> vec; //用以存放所有結(jié)點(diǎn) 
 vector<Pos> pos;   //用以記錄每層的起止位置 
 vec.push_back(pRoot); 
 
 int level = 0; //樹(shù)的層數(shù) 
 int cur = 0; 
 int last = 1; 
 
 while(cur < vec.size()) 
 { 
  last = vec.size(); 
  pos.push_back(Pos(cur, last)); //記錄當(dāng)前層的起止位置 
 
  while(cur < last) //遍歷當(dāng)前層的結(jié)點(diǎn)，將子女放入數(shù)組中 
  { 
   if(vec[cur]->left) //先是左然后是右。如果希望自由向左，交換一下順序即可 
    vec.push_back(vec[cur]->left); 
   if(vec[cur]->right) 
    vec.push_back(vec[cur]->right); 
   cur++; 
  } 
  level++; //層數(shù)加1 
 } 
 
 for(int i = level - 1; i >= 0; i--) //自下往上遍歷 
 { 
  for(int j = pos[i].begin; j < pos[i].end; j++) 
   cout<<vec[j]->value<<' '; 
  cout<<endl; 
 } 
}

輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像
問(wèn)題描述：輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹(shù)中，左子樹(shù)的結(jié)點(diǎn)都大于右子樹(shù)的結(jié)點(diǎn)。用遞歸和循環(huán)兩種方法完成樹(shù)的鏡像轉(zhuǎn)換。
例如輸入：

 8
 / /
 6 10
 // //
5 7 9 11

輸出：

 8
 / /
 10 6
 // //
11 9 7 5

定義二元查找樹(shù)的結(jié)點(diǎn)為：

struct BSTreeNode 
{ 
 int value; 
 BSTreeNode *left; 
 BSTreeNode *right; 
};

      思路：題目要求用兩種方法，遞歸和循環(huán)，其實(shí)質(zhì)是一樣的。
      解法一：用遞歸。假設(shè)當(dāng)前結(jié)點(diǎn)為pNode，只需交換該結(jié)點(diǎn)的左右子女，然后分別遞歸求解左子樹(shù)和右子樹(shù)即可。代碼極為簡(jiǎn)單。
      解法二：用循環(huán)，需要一個(gè)輔助棧完成，每次取棧頂元素交換左右子女，然后將左右子女分別壓入輔助棧，當(dāng)棧中元素為空時(shí)，結(jié)束循環(huán)。其實(shí)不論是遞歸也好，循環(huán)也好，都是利用棧的特性完成。
      參考代碼：

//函數(shù)功能 ： 輸入一顆二元查找樹(shù)，將該樹(shù)轉(zhuǎn)換為它的鏡像 
//函數(shù)參數(shù) ： pRoot為根結(jié)點(diǎn) 
//返回值 ： 根結(jié)點(diǎn) 
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot) 
{ 
 if(pRoot != NULL) 
 { 
  BSTreeNode * pRight = pRoot->right; 
  BSTreeNode * pLeft = pRoot->left; 
  pRoot->left = Mirror_Solution1(pRight); //轉(zhuǎn)化右子樹(shù) 
  pRoot->right = Mirror_Solution1(pLeft); //轉(zhuǎn)化左子樹(shù) 
 } 
 return pRoot; 
} 
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot) 
{ 
 if(pRoot != NULL) 
 { 
  stack<BSTreeNode *> stk; //輔助棧 
  stk.push(pRoot);   //壓入根結(jié)點(diǎn) 
  while(stk.size()) 
  { 
   BSTreeNode *pNode = stk.top(); 
   BSTreeNode *pLeft = pNode->left; 
   BSTreeNode* pRight = pNode->right; 
   stk.pop(); 
 
   if(pLeft != NULL) 
    stk.push(pLeft); 
   if(pRight != NULL) 
    stk.push(pRight); 
   pNode->left = pRight; //交換左右子女 
   pNode->right = pLeft; 
  } 
 } 
 return pRoot; 
}

判斷整數(shù)序列是不是二元查找樹(shù)的后序遍歷結(jié)果
問(wèn)題描述：輸入一個(gè)整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹(shù)的后序遍歷的結(jié)果。如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹(shù)的后序遍歷結(jié)果：

因此返回true。如果輸入7、4、6、5，沒(méi)有哪棵樹(shù)的后序遍歷的結(jié)果是這個(gè)序列，因此返回false。
思路：分析后序遍歷的特點(diǎn)，序列的最后一個(gè)數(shù)應(yīng)該是根結(jié)點(diǎn)，剩余的節(jié)點(diǎn)分為兩個(gè)連續(xù)的子序列，前一子序列的值小于最后一個(gè)數(shù)，后一子序列的值大于最后一個(gè)數(shù)。然后遞歸求解這兩個(gè)子序列。
如果是判斷是前序遍歷也很簡(jiǎn)單，只不過(guò)根節(jié)點(diǎn)變?yōu)榱说谝粋€(gè)數(shù)，剩余的節(jié)點(diǎn)也是分為兩個(gè)連續(xù)的子序列。如果判斷是中序遍歷，更方便，只需掃描一遍，檢查序列是不是排好序的，如果沒(méi)有排好序，就不是中序遍歷的結(jié)果。

把二元查找樹(shù)轉(zhuǎn)變成排序的雙向鏈表
問(wèn)題描述：輸入一棵二元查找樹(shù)，將該二元查找樹(shù)轉(zhuǎn)換成一個(gè)排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點(diǎn)，只調(diào)整指針的指向。

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

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

思路：利用遞歸的思想求解，分別調(diào)整某結(jié)點(diǎn)的左右子樹(shù)，調(diào)整完后，將該結(jié)點(diǎn)的左指針指向左子樹(shù)的最大節(jié)點(diǎn)，右指針指向右子樹(shù)的最小節(jié)點(diǎn)。
代碼如下：

BSTreeNode * Convert(BSTreeNode *node) 
{ 
 if(node == NULL) 
  return NULL; 
 BSTreeNode *leftMax,*rightMin; 
 leftMax = node->left;  
 rightMin = node->right; 
 //找到左子樹(shù)的最大結(jié)點(diǎn) 
 while(leftMax != NULL && leftMax->right != NULL) 
  leftMax = leftMax->right; 
 //找到右子樹(shù)的最小結(jié)點(diǎn) 
 while(rightMin != NULL && rightMin->left != NULL) 
  rightMin = rightMin->left; 
 //遞歸求解 
 Convert(node->right); 
 Convert(node->left); 
 //將左右子樹(shù)同根結(jié)點(diǎn)連起來(lái)，只不過(guò)是以兄弟的關(guān)系 
 if(leftMax != NULL) 
  leftMax->right = node; 
 if(rightMin != NULL) 
  rightMin->left = node; 
 node->left = leftMax; 
 node->right = rightMin; 
 return node; 
}

測(cè)試當(dāng)中，需要建立二叉搜索樹(shù)，下面給出建立及遍歷二叉樹(shù)的代碼。

struct BSTreeNode 
{ 
 int value; 
 BSTreeNode *left; 
 BSTreeNode *right; 
}; 
BSTreeNode * Insert(BSTreeNode *p, int x) 
{ 
 if(p == NULL) 
 { 
  p = new BSTreeNode; 
  p->value = x; 
  p->left = NULL; 
  p->right = NULL; 
 } 
 else 
 { 
  if(p->value > x) 
   p->left = Insert(p->left, x); 
  if(p->value < x) 
   p->right = Insert(p->right, x); 
 } 
 return p; 
} 
void Traverse(BSTreeNode *p) //中序遍歷 
{ 
 if(p == NULL) 
  return; 
 Traverse(p->left); 
 cout<<p->value<<' '; 
 Traverse(p->right); 
}

在二元樹(shù)中找出和為某一值的所有路徑（樹(shù)）
問(wèn)題描述：輸入一個(gè)整數(shù)和一棵二元樹(shù)。從樹(shù)的根結(jié)點(diǎn)開(kāi)始往下訪問(wèn)一直到葉結(jié)點(diǎn)所經(jīng)過(guò)的所有結(jié)點(diǎn)形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。
例如輸入整數(shù)22和如下二元樹(shù)

則打印出兩條路徑：10, 12和10, 5, 7。
二元樹(shù)節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)定義為：

struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};

思路：遞歸的思想。很多樹(shù)的題目都是用遞歸解決的，例如把二元查找樹(shù)轉(zhuǎn)變成排序的雙向鏈表（樹(shù)）。遞歸的終止條件為當(dāng)前為空結(jié)點(diǎn)或當(dāng)前結(jié)點(diǎn)的值大于剩余和。如果當(dāng)前結(jié)點(diǎn)的值等于剩余和，并且是葉結(jié)點(diǎn)，那么打印路徑。否則，將剩余和減去當(dāng)前結(jié)點(diǎn)的值，遞歸求解。至于路徑的記錄，可以利用棧的思想來(lái)實(shí)現(xiàn)。
代碼：

void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path) 
{ 
 //結(jié)點(diǎn)為空或值大于當(dāng)前和 
 if(pNode == NULL || pNode->data > sum) 
  return; 
 path.push_back(pNode->data); 
 //判斷是不是葉結(jié)點(diǎn) 
 bool isLeaf = (pNode->pLeft == NULL && pNode->pRight == NULL)? true: false; 
 //找到一條路徑，打印 
 if(pNode->data == sum && isLeaf) 
 { 
  vector<int>::iterator iter = path.begin(); 
  for(; iter != path.end(); iter++) 
   cout<<*iter<<' '; 
  cout<<endl; 
 } 
 else 
 { 
  //求剩余和 
  sum = sum - pNode->data; 
  //遞歸求解 
  FindPath(pNode->pLeft, sum, path); 
  FindPath(pNode->pRight, sum, path); 
 } 
 path.pop_back(); 
}

判斷二叉樹(shù)是不是平衡的
問(wèn)題描述：輸入一棵二叉樹(shù)的根結(jié)點(diǎn)，判斷該樹(shù)是不是平衡二叉樹(shù)。如果某二叉樹(shù)中任意結(jié)點(diǎn)的左右子樹(shù)的深度相差不超過(guò)1，那么它就是一棵平衡二叉樹(shù)。例如下圖中的二叉樹(shù)就是一棵平衡二叉樹(shù)：

2016315154803523.gif (199×180)

思路：對(duì)于樹(shù)的題目，第一反應(yīng)就是用遞歸。對(duì)于以某個(gè)結(jié)點(diǎn)為根的樹(shù)，只需計(jì)算出它的左右子樹(shù)的深度，如果深度相差小于等于1，則遞歸判斷它的左右子樹(shù)是不是平衡樹(shù)；否則肯定不是平衡二叉樹(shù)。這個(gè)問(wèn)題的關(guān)鍵是要計(jì)算樹(shù)的深度，如果是自頂向下，會(huì)有很多重復(fù)的計(jì)算。計(jì)算以1為根的樹(shù)的深度，會(huì)牽涉到以2為根、以3為根的子樹(shù)。計(jì)算以2為根的樹(shù)的深度，會(huì)牽涉到以4為根、以5為根的子樹(shù)。由于要遍歷每個(gè)結(jié)點(diǎn)，判斷以該結(jié)點(diǎn)為根的樹(shù)是不是平衡二叉樹(shù)。所以計(jì)算以1為根的樹(shù)的深度，與計(jì)算以2為根的樹(shù)的深度，會(huì)重復(fù)計(jì)算以4為根、以5為根的子樹(shù)的深度。

消除重復(fù)辦法，當(dāng)時(shí)是能記錄下之前計(jì)算過(guò)的子樹(shù)的深度，下次使用就不用重新計(jì)算。這就需要自底向上的計(jì)算深度。慶幸的是遞歸解決樹(shù)的問(wèn)題，就是自底向上的過(guò)程。因?yàn)槲覀冊(cè)谶f歸求解中，先要得出子樹(shù)的解，子樹(shù)的解最終會(huì)轉(zhuǎn)換為葉結(jié)點(diǎn)的解?？梢岳煤笮虮闅v的方法，遍歷每個(gè)結(jié)點(diǎn)時(shí)，先判斷它的左右子樹(shù)是不是平衡二叉樹(shù)，同時(shí)記錄下左右子樹(shù)的深度，然后判斷該結(jié)點(diǎn)為根的樹(shù)是不是平衡二叉樹(shù)，至于該樹(shù)的深度計(jì)算很方便，取左右子樹(shù)中較大的深度+1就可以了。這里左右子樹(shù)的深度在遞歸求解中已經(jīng)計(jì)算出來(lái)，不需要重復(fù)計(jì)算了。

參考代碼：

struct BinaryTreeNode 
{ 
  int data; 
  BinaryTreeNode *pLeft; 
  BinaryTreeNode *pRight; 
}; 
//函數(shù)功能 ： 判斷二叉樹(shù)是不是平衡的 
//函數(shù)參數(shù) ： pRoot為根結(jié)點(diǎn)，pDepth為根結(jié)點(diǎn)的深度。 
//返回值 ：  是否平衡的 
bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth) 
{ 
  if(pRoot == NULL) 
  { 
    *pDepth = 0; 
    return true; 
  } 
  int leftDepth, rightDepth; //左右子樹(shù)的深度 
  if(IsBalanced(pRoot->pLeft, &leftDepth)&& 
    IsBalanced(pRoot->pRight, &rightDepth)) 
  { 
    int diff = leftDepth - rightDepth; 
    if(diff == 0 || diff == 1 || diff == -1) //相差為0或1或-1 
    { 
      *pDepth = 1 + (leftDepth > rightDepth ? leftDepth: rightDepth);  
      return true; 
    } 
    else 
      return false; 
  } 
  return false; 
}

您可能感興趣的文章: