[转]http://zhedahht.blog.163.com/blog/static/2541117420072159363370/
题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
8
/ \
6 10
/\ /\
5 7 9 11
输出:
8
/ \
10 6
/\ /\
11 9 7 5
定义二元查找树的结点为:
struct BSTreeNode // a node in the binary search tree (BST)
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};
分析:尽管我们可能一下子不能理解镜像是什么意思,但上面的例子给我们的直观感觉,就是交换结点的左右子树。我们试着在遍历例子中的二元查找树的同时来交换每个结点的左右子树。遍历时首先访问头结点8,我们交换它的左右子树得到:
8
/ \
10 6
/\ /\
9 11 5 7
我们发现两个结点6和10的左右子树仍然是左结点的值小于右结点的值,我们再试着交换他们的左右子树,得到:
8
/ \
10 6
/\ /\
11 9 7 5
刚好就是要求的输出。
上面的分析印证了我们的直觉:在遍历二元查找树时每访问到一个结点,交换它的左右子树。这种思路用递归不难实现,将遍历二元查找树的代码稍作修改就可以了。参考代码如下:
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) recursively
// the head of BST in initial call
///////////////////////////////////////////////////////////////////////
void MirrorRecursively(BSTreeNode *pNode)
{
if(!pNode)
return;
// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// mirror left child sub-tree if not null
if(pNode->m_pLeft)
MirrorRecursively(pNode->m_pLeft);
// mirror right child sub-tree if not null
if(pNode->m_pRight)
MirrorRecursively(pNode->m_pRight);
}
由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。首先我们把树的头结点放入栈中。在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。如果它有左子树,把它的左子树压入栈中;如果它有右子树,把它的右子树压入栈中。这样在下次循环中就能交换它儿子结点的左右子树了。参考代码如下:
///////////////////////////////////////////////////////////////////////
// Mirror a BST (swap the left right child of each node) Iteratively
// Input: pTreeHead: the head of BST
///////////////////////////////////////////////////////////////////////
void MirrorIteratively(BSTreeNode *pTreeHead)
{
if(!pTreeHead)
return;
std::stack<BSTreeNode *> stackTreeNode;
stackTreeNode.push(pTreeHead);
while(stackTreeNode.size())
{
BSTreeNode *pNode = stackTreeNode.top();
stackTreeNode.pop();
// swap the right and left child sub-tree
BSTreeNode *pTemp = pNode->m_pLeft;
pNode->m_pLeft = pNode->m_pRight;
pNode->m_pRight = pTemp;
// push left child sub-tree into stack if not null
if(pNode->m_pLeft)
stackTreeNode.push(pNode->m_pLeft);
// push right child sub-tree into stack if not null
if(pNode->m_pRight)
stackTreeNode.push(pNode->m_pRight);
}
}
分享到:
相关推荐
二元查找树转变成排序的双向链表 题目: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4...
微软面试题第一题 直接就可以运行 不过二元查找树 不知道怎么自动生成 所以硬生生地一个个敲出来的 为了学习二元树的就不用下了
主要介绍了C语言实现输入一颗二元查找树并将该树转换为它的镜像,是数据结构中二元查找树的一个比较经典的算法,有不错的借鉴价值,需要的朋友可以参考下
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表 要求不能创建任何新的节点,只调整指针的指向 微软面试题
(1)编写 AVL树判别程序,并判别一个二元查找树是否为 AVL树。二元查找树用其先序遍历结果表示,如:5,2,1,3,7,8。 (2)实现 AVL树的 ADT,包括其上的基本操作:结点的加入和删除;另外包括将一般二元查找树...
在计算机科学中,AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1,所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者...
题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果. 8 / \ 6 10 / \ / \ 5...
这是去年做的一份课程设计,用c++,visual studio6.0做的,希望对大家有用处
首先说明M 路查找树,M 路查找树是二元查找树的一般化,其结构如下图所示的3 路查找树:M 路查找树中的任一结点至多存放M-1个数据,并至多拥有M棵子树;每个结点中的数据按升序排列V1 (k ),每个数据Vi 都存在一棵左...
求下列二元函数的最大值,f(x1,x2)=x1^2+x2^2,x1与x2的取值区间为{0,1,2,...,7}
编写环境 VS2008 支持插入,旋转,平衡等功能。
按层次遍历二元树 问题描述:输入一颗二元树,从上往下按层打印树的每个结点,同一层中按照从左往右的顺序打印。 例如输入: 8 / / 6 10 / / / / 5 7 9 11 输出 8 6 10 5 7 9 11 定义二元树(其实是二元...
故障树分析法在实施过程中会遇到计算量大的问题,二元决策图是解决这个问题的一种新途径。故障树转化为二元决策图涉及的一个关键问题就是对基本事件的排序,但是基本事件排序是一个NP问题。为了解决这个问题提出了一...
我的二元树代码
二元树 及其应用的一个实例,源码
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 首先我们定义的...
遗传算法求二元一次函(包括一元一次)数最大值。里面有两个单独的例程,其中一个是二元一次函数的,另一个则是一元一次函数的,是和初步入门需要完成作业的小伙伴!