首页 > 代码库 > 二元查找树转化成排序的双向链表——要求不创建新的节点
二元查找树转化成排序的双向链表——要求不创建新的节点
码完第一次编译运行居然就成功了。。。高兴~
问题描述:
输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点,只调整指针的指向。例如:
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 = http://www.mamicode.com/4;>输出:
4 6 8 10 12 14 16
16 14 12 10 8 6 4
二元查找树转化成排序的双向链表——要求不创建新的节点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。