二元查找树转化成排序的双向链表——要求不创建新的节点

码完第一次编译运行居然就成功了。。。高兴~

问题描述:

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。例如:

10

/    \

6     14

/ \      /  \

4   8  12  16

转换成双向链表

4=6=8=10=12=14=16

算法:

如果没有“不能创建任何新的结点”的限制,只需进行一次中序遍历,对每个节点的data值构造一个新节点即可。

由于条件限制,现在我们只能用现有的节点,调整他们的指针指向,把查找树转化为双向链表。算法完成后,原来的查找树也不存在了。

与中序遍历相似,我们采用递归:将节点t的左右子树转化为的链表链接到t的左右两边。

值得注意的是,t的左右子树的链表返回值是不同的,t->left应返回链表的尾节点(最大的),t->right应返回链表的头节点(最小的),这就需要我们设置一个单数flag来区分目前所处理的节点是一个左孩子还是右孩子。

代码实现:

#include<iostream>
using namespace std;

//节点结构体
struct BSTreeNode
{
	int data;
	BSTreeNode* left;
	BSTreeNode* right;
};

//父节点的左右子树的返回指针一头一尾,由flag来区分
BSTreeNode* Transform(BSTreeNode* t,int flag)
{
	if (t->left)//转左子树
	{
		t->left = Transform(t->left, 0);
		t->left->right = t;
	}
	if (t->right)//转右子树
	{
		t->right = Transform(t->right, 1);
		t->right->left = t;
	}
	if (flag == 0)//这是父节点的左子树,返回最右节点
	{
		while (t->right)
			t = t->right;
		return t;
	}
	if (flag == 1)//这是父节点的右子树,返回最左节点
	{
		while (t->left)
			t = t->left;
		return t;
	}
}

void main()
{
	BSTreeNode* n4 = new BSTreeNode;
	BSTreeNode* n6 = new BSTreeNode;
	BSTreeNode* n8 = new BSTreeNode;
	BSTreeNode* n10 = new BSTreeNode;
	BSTreeNode* n12 = new BSTreeNode;
	BSTreeNode* n14 = new BSTreeNode;
	BSTreeNode* n16 = new BSTreeNode;
	//构造二叉树
	n4->data = 4;
	n4->left = n4->right = NULL;
	n8->data = 8;
	n8->left = n8->right = NULL;
	n12->data = 12;
	n12->left = n12->right = NULL;
	n16->data = 16;
	n16->left = n16->right = NULL;
	n6->data = 6;
	n6->left = n4;
	n6->right = n8;
	n14->data = 14;
	n14->left = n12;
	n14->right = n16;
	n10->data = 10;
	n10->left = n6;
	n10->right = n14;

	BSTreeNode* head=Transform(n10,1);//返回最左节点
	while (head->right)//向右输出检验
	{
		cout << head->data << ' ' ;
		head = head->right;
	}
	cout << head->data;//最右节点的data
	cout << endl;
	while (head->left)//向左输出检验
	{
		cout << head->data << ' ';
		head = head->left;
	}
	cout << head->data;//最左节点的data
	cout << endl;
	system("pause");
}

输出:

4 6 8 10 12 14 16

16 14 12 10 8 6 4

时间: 10-01

二元查找树转化成排序的双向链表——要求不创建新的节点的相关文章

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

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

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

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

Java实现: 把二元查找树转变成排序的双向链表(树)

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

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

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表. 要求不能创建任何新的结点,只调整指针的指向. 如下图.    10 /\ 6    14 /\     /\ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16. 这是一种二叉树的中序遍历. typedef struct BSTreeNode { int data; struct BSTreeNode *m_pLeft; struct BSTreeNode *m_pRight; }BSTreeNode,*pBSTr

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

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

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

中序遍历 void ConvertNode(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList){ if(pNode == NULL) return; BSTreeNode *pCurrent = pNode; // Convert the left sub-tree if (pCurrent->m_pLeft != NULL) ConvertNode(pCurrent->m_pLeft, pLastNodeInList); // Put t

[1]输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.          10        /     \       6     14      / \     /  \     4  8 12  16转换成双向链表4=6=8=10=12=14=16 解: 二元查找树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值: (2)若右子树不空,则右子树

二元查找树转换成一个排序的双向链表

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向. 最直观的一种思路就是每次从二分查找树中找到最小的数,加到链表中 </pre><pre name="code" class="cpp">// BST2list.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include<iostream> using namesp

二元查找树变双向链表

声明:取自 ”july“的“微软100题“,加上一些个人理解,欢迎拍砖. 原文地址:http://blog.csdn.net/v_july_v/article/details/6126406 学习微软100题笔记: 1.二元查找树变双向链表: #include <stdio.h> #include <iostream> struct BSTreeNode {     int m_nValue;      BSTreeNode *m_pLeft;      BSTreeNode *m