题目:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点,只调整指针的指向。
10
/\
614
/ \/ \
4812 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树节点的数据结构如下:
struct BSTreeNode
{
int m_nValue;
// value of node
BSTreeNode *m_pLeft;
// left child of node
BSTreeNode *m_pRight;
// right child of node
};
解答 下面是具体函数的实现(java 敲多了 格式有点偏java)
BSTreeNode* LeftMax(BSTreeNode *Node){//获得当前节点左边树中最大值
if(Node->m_pRight != NULL){
return LeftMax(Node->m_pRight);
}else{
return Node;
}
}BSTreeNode* RightMin(BSTreeNode *Node){//获得当前节点右边树中最小值
if(Node->m_pLeft != NULL){
return RightMin(Node->m_pLeft);
}else{
return Node;
}
}void Deal(BSTreeNode *Node){//具体的处理函数
if(Node->m_pLeft != NULL){
Deal(Node->m_pLeft);
Node->m_pLeft = LeftMax(Node->m_pLeft);
//当前节点的左孩子指向 左边树下的最大的那个节点
Node->m_pLeft->m_pRight = Node;
// 左边树下的最大的那个节点 的右孩子指向 当前节点
} if(Node->m_pRight != NULL){
Deal(Node->m_pRight);
Node->m_pRight = RightMin(Node->m_pRight);
//当前节点的右孩子指向 右边树下的最小的那个节点
Node->m_pRight->m_pLeft = Node;
// 右边树下的最小的那个节点 的左孩子指向 当前节点
}
}
整个代码下载地址:http://download.csdn.net/detail/u010862116/8700639
【C++|把二元查找树转变成排序的双向链表】
推荐阅读
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- C语言学习(bit)|16.C语言进阶——深度剖析数据在内存中的存储
- 个人日记|K8s中Pod生命周期和重启策略
- 数据结构和算法|LeetCode 的正确使用方式
- 先序遍历 中序遍历 后序遍历 层序遍历
- 学习分享|【C语言函数基础】
- C++|C++浇水装置问题
- 数据结构|C++技巧(用class类实现链表)
- 数据结构|贪吃蛇代码--c语言版 visual c++6.0打开
- C++|从零开始学C++之基本知识