题目描述:将二叉排序树转换成一个排序的双向链表,要求:不能创建任何新的节点,只能通过调整指针的指向来实现;
解题思路:我们知道二叉排序树的递归定义是:
- 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
- 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
- 它的左、右子树也分别为二叉排序树;
二叉排序树的一个很重要的特性就是:二叉树中序遍历的结果是一个递增的序列。由这个特性可以知道该题需要通过中序遍历的思想来解决。
如上图所示,我们通过中序递归遍历过程中的一个状态来解析转换的过程,当中序遍历root指向10时,要满足转换成双向有序链表的请求,结点10左指针必须指向它中序遍历的前一个结点8,而前一个结点8的右指针必须指向结点10,代码如下:
root->left = last;
last->right = root;
last = root;
这样才能把这两个结点双向连接起来,所以总体的思路就是这样,下面是具体的代码:
//结点的结构
template<typename Type>
struct BiNode{
Type data;
BiNode *left;
BiNode *right;
};
//二叉排序树转换成双向链表
template <typename Type>
void Convert(BiNode<Type> *root, BiNode<Type> *& last)
{
if(root == NULL)
return;
Convert(root->left, last);
root->left = last;
if(last != NULL)
last->right = root;
last = root;
Convert(root->right, last);
}
template <typename Type>
BiNode<Type> * Convert2BinLink( BiNode<Type> *root )
{
if(root == NULL)
return NULL;
BiNode<Type> * last = NULL;
//二叉排序树转换成排序双向链表
Convert(root, last);
//取得双向链表的头指针
while(root->left != NULL)
root = root->left;
return root;
}
Jun 29, 2013 23:15 @dorm
分享到:
相关推荐
二叉排序树变成双向循环链表,二叉排序树变成双向循环链表,二叉排序树变成双向循环链表
数据结构课程设计 用顺序和二叉链表作存储结构实现二叉排序树
使用C语言编写,将二叉树转换成双向链表源代码,记录学习,分享给有需要的人。
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 包含二叉树的建立,测试输出。。可直接运行。。
二叉树转换为双向链表 通过随机创建二叉排序树测试二叉树转换为双向链表是否正确 http://blog.csdn.net/ssuchange/article/details/17383625
首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树;或者是具有下列性质的二元树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有...
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点,只能调整树中节点指针的指向。 为了让您更好地理解问题,以下面的二叉搜索树为例: 我们希望将这个二叉搜索树转化为...
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点,只能调整树中结点指针的指向。 普通的二叉树也可以转换成双向链表,只不过不是排序的 思路: 1. 与中序遍历相同 2. 采用...
36. 二叉搜索树与双向链表题目描述输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。解题思路private TreeNode pre = null;
输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。然后是中序递归遍历,先递归左子树,然后递归到最左的结点,然后赋值为head,tail表示上一个结点。
题目:输入一棵二叉搜索树,将该二叉搜索树转换成一个排序的双向链表。 要求不能创建任何新的结点,只能调整树中结点指针的指向。 ''' class BinaryTreeNode(): def __init__(self, value, left = None, right = ...
微软面试题,输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。适合新手入门结构清晰易懂
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
8.3.1 二叉排序树和二叉平衡树 8.3.2 B-树和B+树 8.4 哈希表及其查找 8.4.1 哈希表与哈希函数 8.4.2 构造哈希函数的常用方法 8.4.3 解决冲突的主要方法 8.5 哈希表算法实现C语言源程序 习题八 第9章 排序 ...
稀疏数组、单向队列、环形队列、单向链表、双向链表、环形链表、约瑟夫问题、栈、前缀、中缀、后缀表达式、中缀表达式转换为后缀表达式、递归与回溯、迷宫问题、八皇后问题、算法的时间复杂度、冒泡排序、选择排序、...
平衡二叉排序树的概念,建立(A),判断失去平衡的类型,平衡化(A),计算ASL(C) 了解B_树,B+树的概念和特点 知道键树(数字查找树) 哈希表的概念、特点、构造哈希表(A),计算ASL和装填因子α(C) 了解各种...
27. 二叉搜索树转换为双向链表 28. 打印字符串中所有字符的排列 29. 数组中出现次数超过一半的数字 30. 找出最小的K个数 31. 连续子数组的最大和 32. 从1到整数n中1出现的次数 33. 把数组中的数排成一个...
09-004动态查找表:二叉排序树的插入和删除操作 09-005查找的性能分析、平衡二叉树、B-树的定义 09-006B-树的查找过程、B+树的定义与查找 09-007键树的结构特点、哈希表的定义、哈希表的构造方法 09-008哈希表的查找...
将二叉搜索树转换成一个排序的双向链表 二叉搜索树中的第k小的结点 9.25 丑数 不用加减法写加法 一个数的次方(今天头很炸,去跑步) 9.26 表示数值的字符串 字符流中第一个只出现一次的字符(今天面了流利说,面试...
\数据结构flash演示\版本1\9-3-4二叉排序树删除.swf \数据结构flash演示\版本1\9-3-5二叉排序树删除.swf \数据结构flash演示\版本1\9-3-6二叉排序树删除.swf \数据结构flash演示\版本1\9-3-7二叉排序树ASL.swf \...