一波C語(yǔ)言二元查找樹(shù)算法題目解答實(shí)例匯總
按層次遍歷二元樹(shù)
問(wèn)題描述：輸入一顆二元樹(shù)，從上往下按層打印樹(shù)的每個(gè)結(jié)點(diǎn)，同一層中按照從左往右的順序打印。
例如輸入：
8 / / 6 10 / / / / 5 7 9 11
輸出
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é)果：
8 / / 6 10 / / / / 5 7 9 11
因此返回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)整指針的指向。
10 / / 6 14 / / / / 4 8 12 16
轉(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 / / 5 12 / / 4 7
則打印出兩條路徑：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ù)：
思路：對(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;
}
相關(guān)文章
多態(tài)是指同樣的消息被不同的對(duì)象接收時(shí)導(dǎo)致不同的行為。本文通過(guò)實(shí)例代碼給大家介紹了C++多態(tài)性與虛函數(shù)的相關(guān)知識(shí)，感興趣的朋友一起看看吧2020-02-02
C語(yǔ)言雙向鏈表的表示與實(shí)現(xiàn)實(shí)例詳解
這篇文章主要介紹了C語(yǔ)言雙向鏈表的表示與實(shí)現(xiàn)，對(duì)于研究數(shù)據(jù)結(jié)構(gòu)域算法的朋友有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-07-07
C++中的動(dòng)態(tài)規(guī)劃子序列問(wèn)題分析探討
可能有些讀者有接觸過(guò)動(dòng)態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動(dòng)態(tài)規(guī)劃這個(gè)東西，別擔(dān)心，我這篇文章會(huì)為讀者做一個(gè)入門，好讓讀者掌握這個(gè)重要的知識(shí)點(diǎn)2023-03-03
C語(yǔ)言中進(jìn)行函數(shù)指針回調(diào)的實(shí)現(xiàn)步驟
在 C 語(yǔ)言中,函數(shù)指針的回調(diào)是一種強(qiáng)大的編程技術(shù),它允許我們?cè)谔囟ǖ氖录l(fā)生或特定的條件滿足時(shí),調(diào)用由用戶定義的函數(shù),這種機(jī)制增加了程序的靈活性和可擴(kuò)展性,使得代碼更具通用性和可重用性,本文給大家介紹了C語(yǔ)言中進(jìn)行函數(shù)指針回調(diào)的實(shí)現(xiàn)步驟,需要的朋友可以參考下2024-07-07
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)高斯噪聲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C++設(shè)計(jì)模式之單例模式,本文同時(shí)給出了數(shù)種單例模式的實(shí)現(xiàn)代碼,需要的朋友可以參考下，希望能夠給你帶來(lái)幫助2021-09-09
這篇文章主要為大家介紹了C++實(shí)現(xiàn)xml解析器示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
以下是對(duì)C++中的虛函數(shù)進(jìn)行了詳細(xì)的分析介紹，需要的朋友可以過(guò)來(lái)參考下2013-08-08
從下面表中的數(shù)據(jù)來(lái)看寫入用時(shí)vector和deque很快，因?yàn)樗麄儍?nèi)存分配次數(shù)少，關(guān)聯(lián)容器和list都是一個(gè)一個(gè)分配的，一個(gè)一個(gè)分配也會(huì)造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
這篇文章主要介紹了C++11新特性-std::tuple的使用方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10