二叉樹的經典面試題分析（三十七）

????????我們之前學習了二叉樹相關的概念，那么我們今天來分析下二叉樹中的一些經典面試題。

????????1、單度結點的刪除

????????????-- 編寫一個函數用于刪除二叉樹中的所有單度結點；

????????????-- 要求：結點刪除后，其唯一的子結點替代它的位置。

????????示例如下

????????a> 那么在我們的結點中包含指向父結點的指針。定義功能：delOld1(node)，刪除 node 為根結點的二叉樹中的單度結點；

????????實現思路如下

????????我們來看看具體代碼怎么寫

#include?<iostream>
#include?"BTree.h"

using?namespace?std;
using?namespace?DTLib;

template?<?typename?T?>
BTreeNode<T>*?createTree()
{
????static?BTreeNode<int>?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?<?typename?T?>
void?printInOrder(BTreeNode<T>*?node)
{
????if(?node?!=?NULL?)
????{
????????printInOrder(node->left);

????????cout?<<?node->value?<<?"?";

????????printInOrder(node->right);
????}
}

template?<?typename?T?>
void?printDualList(BTreeNode<T>*?node)
{
????BTreeNode<T>*?g?=?node;

????cout?<<?"head?->?tail:?"?<<?endl;

????while(?node?!=?NULL?)
????{
????????cout?<<?node->value?<<?"?";

????????g?=?node;

????????node?=?node->right;
????}

????cout?<<?endl;

????cout?<<?"tail?->?head:?"?<<?endl;

????while(?g?!=?NULL?)
????{
????????cout?<<?g->value?<<?"?";

????????g?=?g->left;
????}

????cout?<<?endl;
}

template<?typename?T?>
BTreeNode<T>*?delOld1(BTreeNode<T>*?node)
{
????BTreeNode<T>*?ret?=?NULL;

????if(?node?!=?NULL?)
????{
????????if(?((node->left?!=?NULL)?&&?(node->right?==?NULL))?||
????????????((node->left?==?NULL)?&&?(node->right?!=?NULL))?)
????????{
????????????BTreeNode<T>*?parent?=?dynamic_cast<BTreeNode<T>*>(node->parent);
????????????BTreeNode<T>*?node_child?=?(node->left?!=?NULL)???node->left?:?node->right;

????????????if(?parent?!=?NULL?)
????????????{
????????????????BTreeNode<T>*&?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<int>*?ns?=?createTree<int>();

????printInOrder(ns);

????cout?<<?endl;

????ns?=?delOld1(ns);

????printInOrder(ns);

????cout?<<?endl;

????int?a[]?=?{6,?7,?8};

????for(int?i=0;?i<3;?i++)
????{
????????TreeNode<int>*?n?=?ns?+?a[i];

????????while(?n?!=?NULL?)
????????{
????????????cout?<<?n->value?<<?"?";

????????????n?=?n->parent;
????????}

????????cout?<<?endl;
????}

????return?0;
}

????????我們在其中構建的是上圖中的二叉樹，來運行看看結果

????????我們看到運行的結果和我們想象的是一致的，前序遍歷完后的結果為 6 0 7 2 8。

????????b> 結點中只包含左右孩子指針。定義功能：delOld2(node)? // node 為結點指針的引用；刪除 node 為根結點的二叉樹中的單度結點；

????????實現思路如下圖所示

????????我們來看看具體的源碼編寫

template<?typename?T?>
void?delOld2(BTreeNode<T>*&?node)
{
????if(?node?!=?NULL?)
????{
????????if(?((node->left?!=?NULL)?&&?(node->right?==?NULL))?||
????????????((node->left?==?NULL)?&&?(node->right?!=?NULL))?)
????????{
????????????BTreeNode<T>*?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<int>*?ns?=?createTree<int>();

????printInOrder(ns);

????cout?<<?endl;

????delOld2(ns);

????printInOrder(ns);

????cout?<<?endl;

????return?0;
}

????????我們來看看運行結果

????????結果還是和之前的是一樣的，證明我們寫的是正確的。

????????2、中序線索化二叉樹

????????????-- 編寫一個函數用于中序線索化二叉樹

????????????-- 要求：不允許使用其他數據結構

????????示例如下

????????a> 在中序遍歷的同時進行線索化

????????????思路：使用輔助指針，在中序遍歷時指向當前結點的前驅結點；訪問當前結點時，連接與前驅結點的先后次序；

????????示例如下

????????定義功能：inOrderThread(node, pre) ，node 為根結點，也是中序訪問的結點；pre 為中序遍歷時的前驅結點指針。

????????實現思路如下

????????我們來看看具體源碼是怎么寫的

template?<?typename?T?>
void?inOrderThread(BTreeNode<T>*?node,?BTreeNode<T>*&?pre)
{
????if(?node?!=?NULL?)
????{
????????inOrderThread(node->left,?pre);

????????node->left?=?pre;

????????if(?pre?!=?NULL?)
????????{
????????????pre->right?=?node;
????????}

????????pre?=?node;

????????inOrderThread(node->right,?pre);


????}
}

template?<?typename?T?>
BTreeNode<T>*?inOrderThread1(BTreeNode<T>*?node)
{
????BTreeNode<T>*?pre?=?NULL;

????inOrderThread(node,?pre);

????while(?(node?!=?NULL)?&&?(node->left?!=?NULL)?)
????{
????????node?=?node->left;
????}

????return?node;
}

??????? 測試代碼如下

int?main()
{
????BTreeNode<int>*?ns?=?createTree<int>();

????printInOrder(ns);

????cout?<<?endl;

????ns?=?inOrderThread1(ns);

????printDualList(ns);

????return?0;
}

????????運行結果如下

????????b> 中序遍歷的結案次序正好是結點的水平次序

????????思路：使用輔助指針，指向轉換后雙向鏈表的頭結點和尾結點；跟結點與左右子樹轉換的雙向鏈表連接，成為完整的雙向鏈表。

????????示例如下

????????定義功能：inOrderThread(node, head, tail)； node 為根結點，也是中序訪問的結點；head 為轉換成功后指向雙向鏈表的首結點；tail 為轉換成功后指向雙向鏈表的尾結點。

????????實現思路如下

????????具體源碼實現

template?<?typename?T?>
void?inOrderThread(BTreeNode<T>*?node,?BTreeNode<T>*&?head,?BTreeNode<T>*&?tail)
{
????if(?node?!=?NULL?)
????{
????????BTreeNode<T>*?h?=?NULL;
????????BTreeNode<T>*?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?<?typename?T?>
BTreeNode<T>*?inOrderThread2(BTreeNode<T>*?node)
{
????BTreeNode<T>*?head?=?NULL;
????BTreeNode<T>*?tail?=?NULL;

????inOrderThread(node,?head,?tail);

????return?head;
}

????????測試代碼

int?main()
{
????BTreeNode<int>*?ns?=?createTree<int>();

????printInOrder(ns);

????cout?<<?endl;

????ns?=?inOrderThread2(ns);

????printDualList(ns);

????return?0;
}

????????運行結果如下

????????我們看到兩中算法的遍歷結果是一樣的。關于二叉樹的面試題分析，我們就到這了，后面繼續學習相關的數據結構。