一波C說話二元查找樹算法標題解答實例匯總。本站提示廣大學習愛好者：（一波C說話二元查找樹算法標題解答實例匯總）文章只能為提供參考，不一定能成為您想要的結果。以下是一波C說話二元查找樹算法標題解答實例匯總正文
按條理遍歷二元樹
成績描寫：輸出一顆二元樹，從上往下按層打印樹的每一個結點，統一層中依照從左往右的次序打印。
例如輸出：
8 / / 6 10 / / / / 5 7 9 11
輸入
8 6 10 5 7 9 11
界說二元樹（實際上是二元搜刮樹，但其實不遍歷算法）的結點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思緒：應用隊列的先輩先出，很輕易完成。每次掏出隊列的首元素，然後將其閣下後代放入隊列中。直至隊列為空便可。按這類方法進出隊列，正好是按層遍歷二元樹。
參考代碼：
//函數功效 ： 按條理遍歷二元樹
//函數參數 ： 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;
}
}
}
擴大二：之前評論辯論的都是從上往下、從左往右遍歷二叉樹，那末假如願望自下往上、從閣下往右遍歷二叉樹，該若何修正代碼呢？
思緒：比擬簡略的辦法，起首遍歷二叉樹，將一切結點保留在一個數組中，遍歷的同時記載每層在數組中的起止地位。然後依據起止地位，便可以自下往上的打印二叉樹的結點。
//每層的起止地位
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; //樹的層數
int cur = 0;
int last = 1;
while(cur < vec.size())
{
last = vec.size();
pos.push_back(Pos(cur, last)); //記載以後層的起止地位
while(cur < last) //遍歷以後層的結點，將後代放入數組中
{
if(vec[cur]->left) //先是左然後是右。假如願望自在向左，交流一下次序便可
vec.push_back(vec[cur]->left);
if(vec[cur]->right)
vec.push_back(vec[cur]->right);
cur++;
}
level++; //層數加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;
}
}
輸出一顆二元查找樹，將該樹轉換為它的鏡像
成績描寫：輸出一顆二元查找樹，將該樹轉換為它的鏡像，即在轉換後的二元查找樹中，左子樹的結點都年夜於右子樹的結點。用遞歸和輪回兩種辦法完成樹的鏡像轉換。
例如輸出：
8 / / 6 10 // // 5 7 9 11
輸入：
8 / / 10 6 // // 11 9 7 5
界說二元查找樹的結點為：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
思緒：標題請求用兩種辦法，遞歸和輪回，其本質是一樣的。
解法一：用遞歸。假定以後結點為pNode，只需交流該結點的閣下後代，然後分離遞歸求解左子樹和右子樹便可。代碼極其簡略。
解法二：用輪回，須要一個幫助棧完成，每次取棧頂元故舊換閣下後代，然後將閣下後代分離壓入幫助棧，當棧中元素為空時，停止輪回。其實豈論是遞歸也好，輪回也好，都是應用棧的特征完成。
參考代碼：
//函數功效 ： 輸出一顆二元查找樹，將該樹轉換為它的鏡像
//函數參數 ： 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;
}
斷定整數序列是否是二元查找樹的後序遍歷成果
成績描寫：輸出一個整數數組，斷定該數組是否是某二元查找樹的後序遍歷的成果。假如是前往true，不然前往false。
例如輸出5、7、6、9、11、10、8，因為這一整數序列是以下樹的後序遍歷成果：
8 / / 6 10 / / / / 5 7 9 11
是以前往true。假如輸出7、4、6、5，沒有哪棵樹的後序遍歷的成果是這個序列，是以前往false。
思緒：剖析後序遍歷的特色，序列的最初一個數應當是根結點，殘剩的節點分為兩個持續的子序列，前一子序列的值小於最初一個數，後一子序列的值年夜於最初一個數。然後遞歸求解這兩個子序列。
假如是斷定是前序遍歷也很簡略，只不外根節點變成了第一個數，殘剩的節點也是分為兩個持續的子序列。假如斷定是中序遍歷，更便利，只需掃描一遍，檢討序列是否是排好序的，假如沒有排好序，就不是中序遍歷的成果。
把二元查找樹改變成排序的雙向鏈表
成績描寫：輸出一棵二元查找樹，將該二元查找樹轉換成一個排序的雙向鏈表。請求不克不及創立任何新的結點，只調劑指針的指向。
10 / / 6 14 / / / / 4 8 12 16
轉換成雙向鏈表
4=6=8=10=12=14=16
思緒：應用遞歸的思惟求解，分離調劑某結點的閣下子樹，調劑完後，將該結點的左指針指向左子樹的最年夜節點，右指針指向右子樹的最末節點。
代碼以下：
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);
}
在二元樹中找出和為某一值的一切途徑（樹）
成績描寫：輸出一個整數和一棵二元樹。從樹的根結點開端往下拜訪一向到葉結點所經由的一切結點構成一條途徑。打印出和與輸出整數相等的一切途徑。
例如輸出整數22和以下二元樹
10 / / 5 12 / / 4 7
則打印出兩條途徑：10, 12和10, 5, 7。
二元樹節點的數據構造界說為：
struct BinaryTreeNode
{
int data;
BinaryTreeNode *pLeft;
BinaryTreeNode *pRight;
};
思緒：遞歸的思惟。許多樹的標題都是用遞歸處理的，例如把二元查找樹改變成排序的雙向鏈表（樹）。遞歸的終止前提為以後為空結點或以後結點的值年夜於殘剩和。假如以後結點的值等於殘剩和，而且是葉結點，那末打印途徑。不然，將殘剩和減去以後結點的值，遞歸求解。至於途徑的記載，可以應用棧的思惟來完成。
代碼：
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;
};
//函數功效 ： 斷定二叉樹是否是均衡的
//函數參數 ： 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;
}
