我們之前學(xué)習(xí)了二叉樹相關(guān)的概念，那么我們今天來分析下二叉樹中的一些經(jīng)典面試題。
成都創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供
武安網(wǎng)站建設(shè)、武安做網(wǎng)站、武安網(wǎng)站設(shè)計(jì)、武安網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(shè)計(jì)與制作、武安企業(yè)網(wǎng)站模板建站服務(wù)，十載
武安做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。
1、單度結(jié)點(diǎn)的刪除
-- 編寫一個(gè)函數(shù)用于刪除二叉樹中的所有單度結(jié)點(diǎn)；
?-- 要求：結(jié)點(diǎn)刪除后，其唯一的子結(jié)點(diǎn)替代它的位置。
示例如下
a> 那么在我們的結(jié)點(diǎn)中包含指向父結(jié)點(diǎn)的指針。定義功能：delOld1(node)，刪除 node 為根結(jié)點(diǎn)的二叉樹中的單度結(jié)點(diǎn)；
實(shí)現(xiàn)思路如下
我們來看看具體代碼怎么寫
#include?
#include?"BTree.h"
using?namespace?std;
using?namespace?DTLib;
template?
BTreeNode*?createTree()
{
????static?BTreeNode?ns[9];
????for(int?i=0;?i<9;?i++)
????{
????????ns[i].value?=?i;
????????ns[i].parent?=?NULL;
????????ns[i].left?=?NULL;
????????ns[i].right?=?NULL;
????}
????ns[0].left?=?&ns[1];
????ns[0].right?=?&ns[2];
????ns[1].parent?=?&ns[0];
????ns[2].parent?=?&ns[0];
????ns[1].left?=?&ns[3];
????ns[1].right?=?NULL;
????ns[3].parent?=?&ns[1];
????ns[2].left?=?&ns[4];
????ns[2].right?=?&ns[5];
????ns[4].parent?=?&ns[2];
????ns[5].parent?=?&ns[2];
????ns[3].left?=?NULL;
????ns[3].right?=?&ns[6];
????ns[6].parent?=?&ns[3];
????ns[4].left?=?&ns[7];
????ns[4].right?=?NULL;
????ns[7].parent?=?&ns[4];
????ns[5].left?=?&ns[8];
????ns[5].right?=?NULL;
????ns[8].parent?=?&ns[5];
????return?ns;
}
template?
void?printInOrder(BTreeNode*?node)
{
????if(?node?!=?NULL?)
????{
????????printInOrder(node->left);
????????cout?<value?<right);
????}
}
template?
void?printDualList(BTreeNode*?node)
{
????BTreeNode*?g?=?node;
????cout?<?tail:?"?<value?<right;
????}
????cout?<?head:?"?<value?<left;
????}
????cout?<
BTreeNode*?delOld1(BTreeNode*?node)
{
????BTreeNode*?ret?=?NULL;
????if(?node?!=?NULL?)
????{
????????if(?((node->left?!=?NULL)?&&?(node->right?==?NULL))?||
????????????((node->left?==?NULL)?&&?(node->right?!=?NULL))?)
????????{
????????????BTreeNode*?parent?=?dynamic_cast*>(node->parent);
????????????BTreeNode*?node_child?=?(node->left?!=?NULL)???node->left?:?node->right;
????????????if(?parent?!=?NULL?)
????????????{
????????????????BTreeNode*&?parent_child?=?(parent->left?==?node)???parent->left?:?parent->right;
????????????????parent_child?=?node_child;
????????????????node_child->parent?=?parent;
????????????}
????????????else
????????????{
????????????????node_child->parent?=?NULL;
????????????}
????????????if(?node->flag()?)
????????????{
????????????????delete?node;
????????????}
????????????ret?=?delOld1(node_child);
????????}
????????else
????????{
????????????delOld1(node->left);
????????????delOld1(node->right);
????????????ret?=?node;
????????}
????}
????return?ret;
}
int?main()
{
????BTreeNode*?ns?=?createTree();
????printInOrder(ns);
????cout?<*?n?=?ns?+?a[i];
????????while(?n?!=?NULL?)
????????{
????????????cout?<value?<parent;
????????}
????????cout?<我們在其中構(gòu)建的是上圖中的二叉樹，來運(yùn)行看看結(jié)果
我們看到運(yùn)行的結(jié)果和我們想象的是一致的，前序遍歷完后的結(jié)果為 6 0 7 2 8。
b> 結(jié)點(diǎn)中只包含左右孩子指針。定義功能：delOld2(node)? // node 為結(jié)點(diǎn)指針的引用；刪除 node 為根結(jié)點(diǎn)的二叉樹中的單度結(jié)點(diǎn)；
實(shí)現(xiàn)思路如下圖所示
我們來看看具體的源碼編寫
template
void?delOld2(BTreeNode*&?node)
{
????if(?node?!=?NULL?)
????{
????????if(?((node->left?!=?NULL)?&&?(node->right?==?NULL))?||
????????????((node->left?==?NULL)?&&?(node->right?!=?NULL))?)
????????{
????????????BTreeNode*?node_child?=?(node->left?!=?NULL)???node->left?:?node->right;
????????????if(?node->flag()?)
????????????{
????????????????delete?node;
????????????}
????????????node?=?node_child;
????????????delOld2(node);
????????}
????????else
????????{
????????????delOld2(node->left);
????????????delOld2(node->right);
????????}
????}
}
測試代碼如下
int?main()
{
????BTreeNode*?ns?=?createTree();
????printInOrder(ns);
????cout?<我們來看看運(yùn)行結(jié)果
結(jié)果還是和之前的是一樣的，證明我們寫的是正確的。
2、中序線索化二叉樹
-- 編寫一個(gè)函數(shù)用于中序線索化二叉樹
?-- 要求：不允許使用其他數(shù)據(jù)結(jié)構(gòu)
示例如下
a> 在中序遍歷的同時(shí)進(jìn)行線索化
?思路：使用輔助指針，在中序遍歷時(shí)指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；訪問當(dāng)前結(jié)點(diǎn)時(shí)，連接與前驅(qū)結(jié)點(diǎn)的先后次序；
示例如下
定義功能：inOrderThread(node, pre) ，node 為根結(jié)點(diǎn)，也是中序訪問的結(jié)點(diǎn)；pre 為中序遍歷時(shí)的前驅(qū)結(jié)點(diǎn)指針。
實(shí)現(xiàn)思路如下
我們來看看具體源碼是怎么寫的
template?
void?inOrderThread(BTreeNode*?node,?BTreeNode*&?pre)
{
????if(?node?!=?NULL?)
????{
????????inOrderThread(node->left,?pre);
????????node->left?=?pre;
????????if(?pre?!=?NULL?)
????????{
????????????pre->right?=?node;
????????}
????????pre?=?node;
????????inOrderThread(node->right,?pre);
????}
}
template?
BTreeNode*?inOrderThread1(BTreeNode*?node)
{
????BTreeNode*?pre?=?NULL;
????inOrderThread(node,?pre);
????while(?(node?!=?NULL)?&&?(node->left?!=?NULL)?)
????{
????????node?=?node->left;
????}
????return?node;
}
測試代碼如下
int?main()
{
????BTreeNode*?ns?=?createTree();
????printInOrder(ns);
????cout?<運(yùn)行結(jié)果如下
b> 中序遍歷的結(jié)案次序正好是結(jié)點(diǎn)的水平次序
思路：使用輔助指針，指向轉(zhuǎn)換后雙向鏈表的頭結(jié)點(diǎn)和尾結(jié)點(diǎn)；跟結(jié)點(diǎn)與左右子樹轉(zhuǎn)換的雙向鏈表連接，成為完整的雙向鏈表。
示例如下
定義功能：inOrderThread(node, head, tail)； node 為根結(jié)點(diǎn)，也是中序訪問的結(jié)點(diǎn)；head 為轉(zhuǎn)換成功后指向雙向鏈表的首結(jié)點(diǎn)；tail 為轉(zhuǎn)換成功后指向雙向鏈表的尾結(jié)點(diǎn)。
實(shí)現(xiàn)思路如下
具體源碼實(shí)現(xiàn)
template?
void?inOrderThread(BTreeNode*?node,?BTreeNode*&?head,?BTreeNode*&?tail)
{
????if(?node?!=?NULL?)
????{
????????BTreeNode*?h?=?NULL;
????????BTreeNode*?t?=?NULL;
????????inOrderThread(node->left,?h,?t);
????????node->left?=?t;
????????if(?t?!=?NULL?)
????????{
????????????t->right?=?node;
????????}
????????head?=?(h?!=?NULL)???h?:?node;
????????h?=?NULL;
????????t?=?NULL;
????????inOrderThread(node->right,?h,?t);
????????node->right?=?h;
????????if(?h?!=?NULL?)
????????{
????????????h->left?=?node;
????????}
????????tail?=?(t?!=?NULL)???t?:?node;
????}
}
template?
BTreeNode*?inOrderThread2(BTreeNode*?node)
{
????BTreeNode*?head?=?NULL;
????BTreeNode*?tail?=?NULL;
????inOrderThread(node,?head,?tail);
????return?head;
}
測試代碼
int?main()
{
????BTreeNode*?ns?=?createTree();
????printInOrder(ns);
????cout?<運(yùn)行結(jié)果如下
我們看到兩中算法的遍歷結(jié)果是一樣的。關(guān)于二叉樹的面試題分析，我們就到這了，后面繼續(xù)學(xué)習(xí)相關(guān)的數(shù)據(jù)結(jié)構(gòu)。
新聞名稱：二叉樹的經(jīng)典面試題分析（三十七）-創(chuàng)新互聯(lián)
本文路徑：http://weahome.cn/article/dedsco.html
重慶分公司
重慶分公司
