二元查找树的翻转(镜像)的两种思路

问题描述:

输入一颗二元查找树,将该树转换为它的镜像,

即在转换后的二元查找树中,左子树的结点都大于右子树的结点。

算法:

测试用例:

10

/             \

5               11

/        \

3            7

/     \         /   \

2       4     6      9

/                       /

1                       8

算法:

有两种思路:

①递归。对树翻转,只需对他的左右子树翻转,再交换左右子树的位置即可。

②非递归。设置一个队列queue,从根节点开始处理:人节点先入列,当队列非空时,循环进行以下处理:从队列中取出一节点,交换他的左右子树的位置,将它的左右子节点入列(若存在的话)。当队列为空时,返回。

代码实现:

①递归

//递归
template<class T>
void ReverseTree(BinaryTreeNode<T>* t)
{
<span style="white-space:pre">	</span>if (!t)
<span style="white-space:pre">		</span>return;
<span style="white-space:pre">	</span>BinaryTreeNode<T>* temp = new BinaryTreeNode<T>;
<span style="white-space:pre">	</span>temp = t->LeftChild;
<span style="white-space:pre">	</span>t->LeftChild = t->RightChild;
<span style="white-space:pre">	</span>t->RightChild = temp;
<span style="white-space:pre">	</span>ReverseTree(t->LeftChild);
<span style="white-space:pre">	</span>ReverseTree(t->RightChild);
<span style="white-space:pre">	</span>return;
}

非递归:

//非递归
template<class T>
void ReverseTree2(BinaryTreeNode<T>* t)
{
	if (!t)
		return;
	Queue<BinaryTreeNode<T>*> q;
	q.Add(t);
	BinaryTreeNode<T>* tt = new BinaryTreeNode < T >;
	while (!q.IsEmpty())
	{
		q.Delete(tt);
		BinaryTreeNode<T>* temp = new BinaryTreeNode < T >;
		temp = tt->LeftChild;
		tt->LeftChild = tt->RightChild;
		tt->RightChild = temp;
		if (tt->LeftChild)
			q.Add(tt->LeftChild);
		if (tt->RightChild)
			q.Add(tt->RightChild);
	}
}

输出测试:

InOrder(n10);
	cout << endl;
	ReverseTree(n10);
	InOrder(n10);
	cout << endl;

	ReverseTree2(n10);
	InOrder(n10);
	cout << endl;

输出结果:

时间: 10-04

二元查找树的翻转(镜像)的两种思路的相关文章

15.输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点, 用递归和循环两种方法完成树的镜像转换

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4260432.html  声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点, 用递归和循环两种方法完成树的镜像转换. 题目分析:

【编程题目】输入一颗二元查找树,将该树转换为它的镜像

第 15 题(树):题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点.用递归和循环两种方法完成树的镜像转换. 例如输入: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 nodeBSTreeNode

11.求二元查找树的镜像

http://zhedahht.blog.163.com/blog/static/2541117420072159363370/ 题目:输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点.用递归和循环两种方法完成树的镜像转换. 例如输入: 8    /  \  6      10 /\       /\5  7    9   11 输出: 8    /  \  10    6 /\      /\11  9  7  5 递归实现 void Swap

输入一颗二元查找树,将该树转换为它的镜像

输入一颗二元查找树,将该树转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点. 例如给定下列的输入: 然后有如下的输出: 解法一:递归 首先交换根节点8的左右子树,10,6的左右子树顺序不变,然后交换根节点6的左右子节点,直到左右子节点为空为止. 代码: BSTreeNode*digui(BSTreeNode*pRoot) { if(pRoot!=NULL) { BSTreeNode * pRight=pRoot->right; BSTreeNode * pLeft=pRo

IT公司100题-15-求二元查找树的镜像

问题描述: 输入一颗二元查找树,将该树转换为它的镜像树,即对每一个节点,互换左右子树. 例如输入: 6/    \4     12/ \   /   \2  5 8   16 输出: 6/     \12     4/   \   / \16  8 5  2 定义二元查找树的结点为: typedef struct BSTree { int data; BSTree* left; BSTree* right; } Node; 分析: 方法1:递归交换左右子树. // 15_1.cc #includ

概念:二元查找树

树如其名,就是为了查找而诞生的. 这是一棵二元树,也就说一个根节点只有两个子树.左子树 < 根节点 < 右子树.当然,左右子树都允许为空.还有一点,这里的小于表示的是所有节点,也就是说根节点会大于你左子树的所有节点,不存在你左子树下其中一个节点大于根节点,不可以.(不然不就没法查找了么) 然后递归下去,左子树作为根节点也符合这个要求,然后本身也是一棵二元查找树,如此下去. 作用:用于快速查找. 大于根,走右边,小于根,走左边,直到找到目标为止,而且如果目标存在,绝对不可能错过目标. 概念:二元

IT公司100题-9-判断整数序列是不是二元查找树的后序遍历结果

问题描述: 输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果. 如果是返回true,否则返回false. 例如输入4, 8, 6, 12, 16, 14, 10,由于这一整数序列是如下树的后序遍历结果: 10/     \6      14/  \    /   \4   8 12    16 因此返回true. 如果输入6, 5, 8, 5, 7 ,则返回false. 分析: 在后续遍历得到的序列中,最后一个元素为树的根结点.根节点元素将数组分为两部分,左边都小于根节点,右边都大

1.把二元查找树转变成排序的双向链表

转载请注明出处:http://www.cnblogs.com/wuzetiandaren/p/4256355.html  声明:现大部分文章为寻找问题时在网上相互转载,此博是为自己做个记录记录,方便自己也方便有类似问题的朋友,本文的思想也许有所借鉴,但源码均为本人实现,如有侵权,请发邮件表明文章和原出处地址,我一定在文章中注明.谢谢. 题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 题目分析: 1.二叉树的节点有左右孩子指针,而双向

【编程题目】把二元查找树转变成排序的双向链表(树)

1.把二元查找树转变成排序的双向链表(树)题目:输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 10 / \ 6 14 / \ / \ 4 8 12 16转换成双向链表4=6=8=10=12=14=16.首先我们定义的二元查找树 节点的数据结构如下:struct BSTreeNode{int m_nValue; // value of nodeBSTreeNode *m_pLeft; // left child of nodeBSTree