我们之前学习了二叉树相关的概念，那么我们今天来分析下二叉树中的一些经典面试题。
创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：成都网站建设、做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的左权网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！
1、单度结点的删除
-- 编写一个函数用于删除二叉树中的所有单度结点；
-- 要求：结点删除后，其唯一的子结点替代它的位置。
示例如下
a> 那么在我们的结点中包含指向父结点的指针。定义功能：delOld1(node)，删除 node 为根结点的二叉树中的单度结点；
实现思路如下
我们来看看具体代码怎么写
#include
#include "BTree.h"
using namespace std;
using namespace DTLib;
template < typename T >
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 < typename T >
void printInOrder(BTreeNode* node)
{
if( node != NULL )
{
printInOrder(node->left);
cout << node->value << " ";
printInOrder(node->right);
}
}
template < typename T >
void printDualList(BTreeNode* node)
{
BTreeNode* 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* 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 << endl;
ns = delOld1(ns);
printInOrder(ns);
cout << endl;
int a[] = {6, 7, 8};
for(int i=0; i<3; i++)
{
TreeNode* 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*& 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 << endl;
delOld2(ns);
printInOrder(ns);
cout << endl;
return 0;
} 我们来看看运行结果
结果还是和之前的是一样的，证明我们写的是正确的。
2、中序线索化二叉树
-- 编写一个函数用于中序线索化二叉树
-- 要求：不允许使用其他数据结构
示例如下
a> 在中序遍历的同时进行线索化
思路：使用辅助指针，在中序遍历时指向当前结点的前驱结点；访问当前结点时，连接与前驱结点的先后次序；
示例如下
定义功能：inOrderThread(node, pre) ，node 为根结点，也是中序访问的结点；pre 为中序遍历时的前驱结点指针。
实现思路如下
我们来看看具体源码是怎么写的
template < typename T >
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 < typename T >
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 << endl;
ns = inOrderThread1(ns);
printDualList(ns);
return 0;
} 运行结果如下
b> 中序遍历的结案次序正好是结点的水平次序
思路：使用辅助指针，指向转换后双向链表的头结点和尾结点；跟结点与左右子树转换的双向链表连接，成为完整的双向链表。
示例如下
定义功能：inOrderThread(node, head, tail)； node 为根结点，也是中序访问的结点；head 为转换成功后指向双向链表的首结点；tail 为转换成功后指向双向链表的尾结点。
实现思路如下
具体源码实现
template < typename T >
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 < typename T >
BTreeNode* inOrderThread2(BTreeNode* node)
{
BTreeNode* head = NULL;
BTreeNode* tail = NULL;
inOrderThread(node, head, tail);
return head;
}
测试代码
int main()
{
BTreeNode* ns = createTree();
printInOrder(ns);
cout << endl;
ns = inOrderThread2(ns);
printDualList(ns);
return 0;
} 运行结果如下
我们看到两中算法的遍历结果是一样的。关于二叉树的面试题分析，我们就到这了，后面继续学习相关的数据结构。
名称栏目：二叉树的经典面试题分析（三十七）
文章出自：
http://chengdu.cdxwcx.cn/article/gccpei.html
