一波C語言二元查找樹算法題目解答實例匯總
按層次遍歷二元樹
問題描述：輸入一顆二元樹，從上往下按層打印樹的每個結(jié)點，同一層中按照從左往右的順序打印。
例如輸入：
8 / / 6 10 / / / / 5 7 9 11
輸出
8 6 10 5 7 9 11
定義二元樹（其實是二元搜索樹，但并不遍歷算法）的結(jié)點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思路：利用隊列的先進先出，很容易實現(xiàn)。每次取出隊列的首元素，然后將其左右子女放入隊列中。直至隊列為空即可。按這種方式進出隊列，正好是按層遍歷二元樹。
參考代碼：
//函數(shù)功能 ： 按層次遍歷二元樹
//函數(shù)參數(shù) ： pRoot指向根結(jié)點
//返回值 ： 無
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<<' ';
}
}
擴展一：上文給出的代碼，所有結(jié)點都輸出在同一行。如果希望僅僅同層結(jié)點輸出在同一行，該如何修改代碼呢？
思路：如果我們能知道每層的最后一個結(jié)點，那么就方便多了，輸出每層最后一個結(jié)點的同時，輸出一個換行符。因此，關(guān)鍵在于如何標(biāo)記每層的結(jié)束?？梢钥紤]在每層的最后一個點之后，插入一個空結(jié)點。比如隊列中先放入根結(jié)點，由于第0層只有一個結(jié)點，因此放入一個空結(jié)點。然后依次取出隊列中的結(jié)點，將其子女放入隊列中，如果遇到空結(jié)點，表明當(dāng)前層的結(jié)點已遍歷完了，而隊列中放的恰恰是下一層的所有結(jié)點。如果當(dāng)前隊列為空，表明下一層無結(jié)點，也就說是所有結(jié)點已遍歷好了。如果不為空，那么插入一個空結(jié)點，用于標(biāo)記下一層的結(jié)束。
參考代碼：
void LevelReverse(BSTreeNode *pRoot)
{
if(pRoot == NULL)
return;
queue<BSTreeNode *> nodeQueue;
nodeQueue.push(pRoot);
nodeQueue.push(NULL); //放入空結(jié)點，作為層的結(jié)束符
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()) //如果結(jié)點為空并且隊列也為空，那么所有結(jié)點都已訪問
{
nodeQueue.push(NULL);
cout<<endl;
}
}
}
擴展二：之前討論的都是從上往下、從左往右遍歷二叉樹，那么如果希望自下往上、從左右往右遍歷二叉樹，該如何修改代碼呢？
思路：比較簡單的方法，首先遍歷二叉樹，將所有結(jié)點保存在一個數(shù)組中，遍歷的同時記錄每一層在數(shù)組中的起止位置。然后根據(jù)起止位置，就可以自下往上的打印二叉樹的結(jié)點。
//每層的起止位置
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é)點
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)); //記錄當(dāng)前層的起止位置
while(cur < last) //遍歷當(dāng)前層的結(jié)點，將子女放入數(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;
}
}
輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像
問題描述：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
8 / / 6 10 // // 5 7 9 11
輸出：
8 / / 10 6 // // 11 9 7 5
定義二元查找樹的結(jié)點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思路：題目要求用兩種方法，遞歸和循環(huán)，其實質(zhì)是一樣的。
解法一：用遞歸。假設(shè)當(dāng)前結(jié)點為pNode，只需交換該結(jié)點的左右子女，然后分別遞歸求解左子樹和右子樹即可。代碼極為簡單。
解法二：用循環(huán)，需要一個輔助棧完成，每次取棧頂元素交換左右子女，然后將左右子女分別壓入輔助棧，當(dāng)棧中元素為空時，結(jié)束循環(huán)。其實不論是遞歸也好，循環(huán)也好，都是利用棧的特性完成。
參考代碼：
//函數(shù)功能 ： 輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像
//函數(shù)參數(shù) ： pRoot為根結(jié)點
//返回值 ： 根結(jié)點
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
BSTreeNode * pRight = pRoot->right;
BSTreeNode * pLeft = pRoot->left;
pRoot->left = Mirror_Solution1(pRight); //轉(zhuǎn)化右子樹
pRoot->right = Mirror_Solution1(pLeft); //轉(zhuǎn)化左子樹
}
return pRoot;
}
BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
stack<BSTreeNode *> stk; //輔助棧
stk.push(pRoot); //壓入根結(jié)點
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ù)序列是不是二元查找樹的后序遍歷結(jié)果
問題描述：輸入一個整數(shù)數(shù)組，判斷該數(shù)組是不是某二元查找樹的后序遍歷的結(jié)果。如果是返回true，否則返回false。
例如輸入5、7、6、9、11、10、8，由于這一整數(shù)序列是如下樹的后序遍歷結(jié)果：
8 / / 6 10 / / / / 5 7 9 11
因此返回true。如果輸入7、4、6、5，沒有哪棵樹的后序遍歷的結(jié)果是這個序列，因此返回false。
思路：分析后序遍歷的特點，序列的最后一個數(shù)應(yīng)該是根結(jié)點，剩余的節(jié)點分為兩個連續(xù)的子序列，前一子序列的值小于最后一個數(shù)，后一子序列的值大于最后一個數(shù)。然后遞歸求解這兩個子序列。
如果是判斷是前序遍歷也很簡單，只不過根節(jié)點變?yōu)榱说谝粋€數(shù)，剩余的節(jié)點也是分為兩個連續(xù)的子序列。如果判斷是中序遍歷，更方便，只需掃描一遍，檢查序列是不是排好序的，如果沒有排好序，就不是中序遍歷的結(jié)果。
把二元查找樹轉(zhuǎn)變成排序的雙向鏈表
問題描述：輸入一棵二元查找樹，將該二元查找樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結(jié)點，只調(diào)整指針的指向。
10 / / 6 14 / / / / 4 8 12 16
轉(zhuǎn)換成雙向鏈表
4=6=8=10=12=14=16
思路：利用遞歸的思想求解，分別調(diào)整某結(jié)點的左右子樹，調(diào)整完后，將該結(jié)點的左指針指向左子樹的最大節(jié)點，右指針指向右子樹的最小節(jié)點。
代碼如下：
BSTreeNode * Convert(BSTreeNode *node)
{
if(node == NULL)
return NULL;
BSTreeNode *leftMax,*rightMin;
leftMax = node->left;
rightMin = node->right;
//找到左子樹的最大結(jié)點
while(leftMax != NULL && leftMax->right != NULL)
leftMax = leftMax->right;
//找到右子樹的最小結(jié)點
while(rightMin != NULL && rightMin->left != NULL)
rightMin = rightMin->left;
//遞歸求解
Convert(node->right);
Convert(node->left);
//將左右子樹同根結(jié)點連起來，只不過是以兄弟的關(guān)系
if(leftMax != NULL)
leftMax->right = node;
if(rightMin != NULL)
rightMin->left = node;
node->left = leftMax;
node->right = rightMin;
return node;
}
測試當(dāng)中，需要建立二叉搜索樹，下面給出建立及遍歷二叉樹的代碼。
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ù)和一棵二元樹。從樹的根結(jié)點開始往下訪問一直到葉結(jié)點所經(jīng)過的所有結(jié)點形成一條路徑。打印出和與輸入整數(shù)相等的所有路徑。
例如輸入整數(shù)22和如下二元樹
10 / / 5 12 / / 4 7
則打印出兩條路徑：10, 12和10, 5, 7。
二元樹節(jié)點的數(shù)據(jù)結(jié)構(gòu)定義為：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};
思路：遞歸的思想。很多樹的題目都是用遞歸解決的，例如把二元查找樹轉(zhuǎn)變成排序的雙向鏈表（樹）。遞歸的終止條件為當(dāng)前為空結(jié)點或當(dāng)前結(jié)點的值大于剩余和。如果當(dāng)前結(jié)點的值等于剩余和，并且是葉結(jié)點，那么打印路徑。否則，將剩余和減去當(dāng)前結(jié)點的值，遞歸求解。至于路徑的記錄，可以利用棧的思想來實現(xiàn)。
代碼：
void FindPath(BinaryTreeNode *pNode,int sum,vector<int> &path)
{
//結(jié)點為空或值大于當(dāng)前和
if(pNode == NULL || pNode->data > sum)
return;
path.push_back(pNode->data);
//判斷是不是葉結(jié)點
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();
}
判斷二叉樹是不是平衡的
問題描述：輸入一棵二叉樹的根結(jié)點，判斷該樹是不是平衡二叉樹。如果某二叉樹中任意結(jié)點的左右子樹的深度相差不超過1，那么它就是一棵平衡二叉樹。例如下圖中的二叉樹就是一棵平衡二叉樹：
思路：對于樹的題目，第一反應(yīng)就是用遞歸。對于以某個結(jié)點為根的樹，只需計算出它的左右子樹的深度，如果深度相差小于等于1，則遞歸判斷它的左右子樹是不是平衡樹；否則肯定不是平衡二叉樹。這個問題的關(guān)鍵是要計算樹的深度，如果是自頂向下，會有很多重復(fù)的計算。計算以1為根的樹的深度，會牽涉到以2為根、以3為根的子樹。計算以2為根的樹的深度，會牽涉到以4為根、以5為根的子樹。由于要遍歷每個結(jié)點，判斷以該結(jié)點為根的樹是不是平衡二叉樹。所以計算以1為根的樹的深度，與計算以2為根的樹的深度，會重復(fù)計算以4為根、以5為根的子樹的深度。
消除重復(fù)辦法，當(dāng)時是能記錄下之前計算過的子樹的深度，下次使用就不用重新計算。這就需要自底向上的計算深度。慶幸的是遞歸解決樹的問題，就是自底向上的過程。因為我們在遞歸求解中，先要得出子樹的解，子樹的解最終會轉(zhuǎn)換為葉結(jié)點的解?？梢岳煤笮虮闅v的方法，遍歷每個結(jié)點時，先判斷它的左右子樹是不是平衡二叉樹，同時記錄下左右子樹的深度，然后判斷該結(jié)點為根的樹是不是平衡二叉樹，至于該樹的深度計算很方便，取左右子樹中較大的深度+1就可以了。這里左右子樹的深度在遞歸求解中已經(jīng)計算出來，不需要重復(fù)計算了。
參考代碼：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};
//函數(shù)功能 ： 判斷二叉樹是不是平衡的
//函數(shù)參數(shù) ： pRoot為根結(jié)點，pDepth為根結(jié)點的深度。
//返回值 ： 是否平衡的
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;
}
相關(guān)文章
多態(tài)是指同樣的消息被不同的對象接收時導(dǎo)致不同的行為。本文通過實例代碼給大家介紹了C++多態(tài)性與虛函數(shù)的相關(guān)知識，感興趣的朋友一起看看吧2020-02-02
這篇文章主要介紹了C語言雙向鏈表的表示與實現(xiàn)，對于研究數(shù)據(jù)結(jié)構(gòu)域算法的朋友有一定的參考借鑒價值,需要的朋友可以參考下2014-07-07
可能有些讀者有接觸過動態(tài)規(guī)劃，可能也有一些讀者以前完全不知道動態(tài)規(guī)劃這個東西，別擔(dān)心，我這篇文章會為讀者做一個入門，好讓讀者掌握這個重要的知識點2023-03-03
C語言中進行函數(shù)指針回調(diào)的實現(xiàn)步驟
在 C 語言中,函數(shù)指針的回調(diào)是一種強大的編程技術(shù),它允許我們在特定的事件發(fā)生或特定的條件滿足時,調(diào)用由用戶定義的函數(shù),這種機制增加了程序的靈活性和可擴展性,使得代碼更具通用性和可重用性,本文給大家介紹了C語言中進行函數(shù)指針回調(diào)的實現(xiàn)步驟,需要的朋友可以參考下2024-07-07
這篇文章主要為大家詳細(xì)介紹了OpenCV實現(xiàn)高斯噪聲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-06-06
這篇文章主要介紹了C++設(shè)計模式之單例模式,本文同時給出了數(shù)種單例模式的實現(xiàn)代碼,需要的朋友可以參考下，希望能夠給你帶來幫助2021-09-09
這篇文章主要為大家介紹了C++實現(xiàn)xml解析器示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-08-08
以下是對C++中的虛函數(shù)進行了詳細(xì)的分析介紹，需要的朋友可以過來參考下2013-08-08
從下面表中的數(shù)據(jù)來看寫入用時vector和deque很快，因為他們內(nèi)存分配次數(shù)少，關(guān)聯(lián)容器和list都是一個一個分配的，一個一個分配也會造成內(nèi)存碎片，內(nèi)存利用率低2013-09-09
這篇文章主要介紹了C++11新特性-std::tuple的使用方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-10-10