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

中序遍历

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 the current node into the double-linked list
pCurrent->m_pLeft = pLastNodeInList;
if(pLastNodeInList != NULL)
pLastNodeInList->m_pRight = pCurrent;

pLastNodeInList = pCurrent;

// Convert the right sub-tree
if (pCurrent->m_pRight != NULL)
ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

///////////////////////////////////////////////////////////////////////
// Covert a binary search tree into a sorted double-linked list
// Input: pHeadOfTree - the head of tree
// Output: the head of sorted double-linked list
///////////////////////////////////////////////////////////////////////
BSTreeNode* Convert_Solution1(BSTreeNode* pHeadOfTree)
{
BSTreeNode *pLastNodeInList = NULL;
ConvertNode(pHeadOfTree, pLastNodeInList);

// Get the head of the double-linked list
BSTreeNode *pHeadOfList = pLastNodeInList;
while(pHeadOfList && pHeadOfList->m_pLeft)
pHeadOfList = pHeadOfList->m_pLeft;

return pHeadOfList;
}

时间: 09-16

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

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

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

码完第一次编译运行居然就成功了...高兴~ 问题描述: 输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表.要求不能创建任何新的结点,只调整指针的指向.例如: 10 /    \ 6     14 / \      /  \ 4   8  12  16 转换成双向链表 4=6=8=10=12=14=16 算法: 如果没有"不能创建任何新的结点"的限制,只需进行一次中序遍历,对每个节点的data值构造一个新节点即可. 由于条件限制,现在我们只能用现有的节点,调整他们的指针指向,把

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.二叉树的节点有左右孩子指针,而双向

[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

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

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