一波C語言二元查找樹算法題目解答實例匯總
按層次遍歷二元樹
問題描述：輸入一顆二元樹，從上往下按層打印樹的每個結點，同一層中按照從左往右的順序打印。
例如輸入：
8 / / 6 10 / / / / 5 7 9 11
輸出
8 6 10 5 7 9 11
定義二元樹（其實是二元搜索樹，但并不遍歷算法）的結點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思路：利用隊列的先進先出，很容易實現(xiàn)。每次取出隊列的首元素，然后將其左右子女放入隊列中。直至隊列為空即可。按這種方式進出隊列，正好是按層遍歷二元樹。
參考代碼：
//函數(shù)功能 ： 按層次遍歷二元樹
//函數(shù)參數(shù) ： pRoot指向根結點
//返回值 ： 無
void LevelReverse(BSTreeNode *pRoot)
{
if(pRoot == NULL)
return;
queue<BSTreeNode *> nodeQueue;
nodeQueue.push(pRoot);
while(nodeQueue.size())
{
BSTreeNode * pNode = nodeQueue.front(); //取隊首元素
nodeQueue.pop(); //必須出隊列
if(pNode->left) //左子女
nodeQueue.push(pNode->left);
if(pNode->right) //右子女
nodeQueue.push(pNode->right);
cout<<pNode->value<<' ';
}
}
擴展一：上文給出的代碼，所有結點都輸出在同一行。如果希望僅僅同層結點輸出在同一行，該如何修改代碼呢？
思路：如果我們能知道每層的最后一個結點，那么就方便多了，輸出每層最后一個結點的同時，輸出一個換行符。因此，關鍵在于如何標記每層的結束?？梢钥紤]在每層的最后一個點之后，插入一個空結點。比如隊列中先放入根結點，由于第0層只有一個結點，因此放入一個空結點。然后依次取出隊列中的結點，將其子女放入隊列中，如果遇到空結點，表明當前層的結點已遍歷完了，而隊列中放的恰恰是下一層的所有結點。如果當前隊列為空，表明下一層無結點，也就說是所有結點已遍歷好了。如果不為空，那么插入一個空結點，用于標記下一層的結束。
參考代碼：
void LevelReverse(BSTreeNode *pRoot)
{
if(pRoot == NULL)
return;
queue<BSTreeNode *> nodeQueue;
nodeQueue.push(pRoot);
nodeQueue.push(NULL); //放入空結點，作為層的結束符
while(nodeQueue.size())
{
BSTreeNode * pNode = nodeQueue.front(); //取隊首元素
nodeQueue.pop(); //必須出隊列
if(pNode)
{
if(pNode->left) //左子女
nodeQueue.push(pNode->left);
if(pNode->right) //右子女
nodeQueue.push(pNode->right);
cout<<pNode->value<<' ';
}
else if(nodeQueue.size()) //如果結點為空并且隊列也為空，那么所有結點都已訪問
{
nodeQueue.push(NULL);
cout<<endl;
}
}
}
擴展二：之前討論的都是從上往下、從左往右遍歷二叉樹，那么如果希望自下往上、從左右往右遍歷二叉樹，該如何修改代碼呢？
思路：比較簡單的方法，首先遍歷二叉樹，將所有結點保存在一個數(shù)組中，遍歷的同時記錄每一層在數(shù)組中的起止位置。然后根據(jù)起止位置，就可以自下往上的打印二叉樹的結點。
//每層的起止位置
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; //用以存放所有結點
vector<Pos> pos; //用以記錄每層的起止位置
vec.push_back(pRoot);
int level = 0; //樹的層數(shù)
int cur = 0;
int last = 1;
while(cur < vec.size())
{
last = vec.size();
pos.push_back(Pos(cur, last)); //記錄當前層的起止位置
while(cur < last) //遍歷當前層的結點，將子女放入數(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;
}
}
輸入一顆二元查找樹，將該樹轉換為它的鏡像
問題描述：輸入一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換后的二元查找樹中，左子樹的結點都大于右子樹的結點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉換。
例如輸入：
8 / / 6 10 // // 5 7 9 11
輸出：
8 / / 10 6 // // 11 9 7 5
定義二元查找樹的結點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思路：題目要求用兩種方法，遞歸和循環(huán)，其實質是一樣的。
解法一：用遞歸。假設當前結點為pNode，只需交換該結點的左右子女，然后分別遞歸求解左子樹和右子樹即可。代碼極為簡單。
解法二：用循環(huán)，需要一個輔助棧完成，每次取棧頂元素交換左右子女，然后將左右子女分別壓入輔助棧，當棧中元素為空時，結束循環(huán)。其實不論是遞歸也好，循環(huán)也好，都是利用棧的特性完成。
參考代碼：
//函數(shù)功能 ： 輸入一顆二元查找樹，將該樹轉換為它的鏡像
//函數(shù)參數(shù) ： pRoot為根結點
//返回值 ： 根結點
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
BSTreeNode * pRight = pRoot->right;
BSTreeNode * pLeft = pRoot->left;
pRoot->left = Mirror_Solution1(pRight); //轉化右子樹
pRoot->right = Mirror_Solution1(pLeft); //轉化左子樹
}
return pRoot;
}
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
stack<BSTreeNode *> stk; //輔助棧
stk.push(pRoot); //壓入根結點
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ù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結果。如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結果：
8 / / 6 10 / / / / 5 7 9 11
因此返回true。如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結果是這個序列，因此返回false。
思路：分析后序遍歷的特點，序列的最后一個數(shù)應該是根結點，剩余的節(jié)點分為兩個連續(xù)的子序列，前一子序列的值小于最后一個數(shù)，后一子序列的值大于最后一個數(shù)。然后遞歸求解這兩個子序列。
如果是判斷是前序遍歷也很簡單，只不過根節(jié)點變?yōu)榱说谝粋€數(shù)，剩余的節(jié)點也是分為兩個連續(xù)的子序列。如果判斷是中序遍歷，更方便，只需掃描一遍，檢查序列是不是排好序的，如果沒有排好序，就不是中序遍歷的結果。
把二元查找樹轉變成排序的雙向鏈表
問題描述：輸入一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點，只調整指針的指向。
10 / / 6 14 / / / / 4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16
思路：利用遞歸的思想求解，分別調整某結點的左右子樹，調整完后，將該結點的左指針指向左子樹的最大節(jié)點，右指針指向右子樹的最小節(jié)點。
代碼如下：
BSTreeNode * Convert(BSTreeNode *node)
{
if(node == NULL)
return NULL;
BSTreeNode *leftMax,*rightMin;
leftMax = node->left;
rightMin = node->right;
//找到左子樹的最大結點
while(leftMax != NULL && leftMax->right != NULL)
leftMax = leftMax->right;
//找到右子樹的最小結點
while(rightMin != NULL && rightMin->left != NULL)
rightMin = rightMin->left;
//遞歸求解
Convert(node->right);
Convert(node->left);
//將左右子樹同根結點連起來，只不過是以兄弟的關系
if(leftMax != NULL)
leftMax->right = node;
if(rightMin != NULL)
rightMin->left = node;
node->left = leftMax;
node->right = rightMin;
return node;
}
測試當中，需要建立二叉搜索樹，下面給出建立及遍歷二叉樹的代碼。
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ù)相等的所有路徑。
例如輸入整數(shù)22和如下二元樹
10 / / 5 12 / / 4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節(jié)點的數(shù)據(jù)結構定義為：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};
思路：遞歸的思想。很多樹的題目都是用遞歸解決的，例如把二元查找樹轉變成排序的雙向鏈表（樹）。遞歸的終止條件為當前為空結點或當前結點的值大于剩余和。如果當前結點的值等于剩余和，并且是葉結點，那么打印路徑。否則，將剩余和減去當前結點的值，遞歸求解。至于路徑的記錄，可以利用棧的思想來實現(xiàn)。
代碼：
void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path)
{
//結點為空或值大于當前和
if(pNode == NULL || pNode->data > sum)
return;
path.push_back(pNode->data);
//判斷是不是葉結點
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();
}
判斷二叉樹是不是平衡的
問題描述：輸入一棵二叉樹的根結點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。例如下圖中的二叉樹就是一棵平衡二叉樹：
思路：對于樹的題目，第一反應就是用遞歸。對于以某個結點為根的樹，只需計算出它的左右子樹的深度，如果深度相差小于等于1，則遞歸判斷它的左右子樹是不是平衡樹；否則肯定不是平衡二叉樹。這個問題的關鍵是要計算樹的深度，如果是自頂向下，會有很多重復的計算。計算以1為根的樹的深度，會牽涉到以2為根、以3為根的子樹。計算以2為根的樹的深度，會牽涉到以4為根、以5為根的子樹。由于要遍歷每個結點，判斷以該結點為根的樹是不是平衡二叉樹。所以計算以1為根的樹的深度，與計算以2為根的樹的深度，會重復計算以4為根、以5為根的子樹的深度。
消除重復辦法，當時是能記錄下之前計算過的子樹的深度，下次使用就不用重新計算。這就需要自底向上的計算深度。慶幸的是遞歸解決樹的問題，就是自底向上的過程。因為我們在遞歸求解中，先要得出子樹的解，子樹的解最終會轉換為葉結點的解。可以利用后序遍歷的方法，遍歷每個結點時，先判斷它的左右子樹是不是平衡二叉樹，同時記錄下左右子樹的深度，然后判斷該結點為根的樹是不是平衡二叉樹，至于該樹的深度計算很方便，取左右子樹中較大的深度+1就可以了。這里左右子樹的深度在遞歸求解中已經計算出來，不需要重復計算了。
參考代碼：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};
//函數(shù)功能 ： 判斷二叉樹是不是平衡的
//函數(shù)參數(shù) ： pRoot為根結點，pDepth為根結點的深度。
//返回值 ： 是否平衡的
bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth)
{
if(pRoot == NULL)
{
*pDepth = 0;
return true;
}
int leftDepth, rightDepth; //左右子樹的深度
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;
}
相關文章
這篇文章主要介紹了C語言函數(shù)的基本使用和遞歸小結,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
strings命令分析淺談Go和C++編譯時的一點小區(qū)別
今天小編就為大家分享一篇關于strings命令分析淺談Go和C++編譯時的一點小區(qū)別，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-04-04
這篇文章主要為大家詳細介紹了C++圖書管理系統(tǒng)程序源代碼，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
本文主要介紹了C++多線程std::call_once的使用，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-03-03
C語言選擇、循環(huán)、函數(shù)、數(shù)組與操作符
這篇文章主要介紹了C語言選擇、循環(huán)、函數(shù)、數(shù)組與操作符，文章基于C語言展開對主題的詳細介紹，下文內容需要的小伙伴可以參考一下2022-04-04
這篇文章主要介紹了C語言 動態(tài)內存分配的詳解及實例的相關資料,需要的朋友可以參考下2016-09-09
引用是C++一個很重要的特性,顧名思義是某一個變量或對象的別名，對引用的操作與對其所綁定的變量或對象的操作完全等價,這篇文章主要給大家總結介紹了C++中引用的相關知識點,需要的朋友可以參考下2022-04-04
這篇文章主要介紹了C++前綴樹字典樹的學習與模擬實現(xiàn)代碼示例,Trie又被稱為前綴樹、字典樹，所以當然是一棵樹,上面這棵Trie樹包含的字符串集合是{in,inn,int,tea,ten,to},每個節(jié)點的編號是我們?yōu)榱嗣枋龇奖慵由先サ?需要的朋友可以參考下2023-07-07
這篇文章主要介紹了C語言判定一棵二叉樹是否為二叉搜索樹的方法,結合實例形式綜合對比分析了C語言針對二叉搜索樹判定的原理、算法、效率及相關實現(xiàn)技巧,需要的朋友可以參考下2018-08-08
Objective-C語言中方法的傳遞有二種：①Selector ② Blocks，本文主要說一下Selector，本文以Objective-C 消息傳遞機制進行詳細介紹，關于Blocks會在后續(xù)總結一下2012-11-11