算法-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,*pBSTreeNode;

pBSTreeNode linkList = NULL;//全局变量,当前链表的指针

pBSTreeNode  pFormer = NULL;//以前的

void BinTreeToLinkList(pBSTreeNode BT){

if(BT!=NULL){

BinTreeToLinkList(BT->m_pLeft);

if(linkList==NULL){

linkList=BT;

pFormer=BT;

}else{

pFormer->m_pRight=BT;

BT->m_pLeft=pFormer;

pFormer=BT;

}

BinTreeToLinkList(BT->m_pRight);

}

}

如何进行验证呢,首先创建一个二叉树。

void  addBSTreeNode(pBSTreeNode *pNode,int  data){

if (*pNode == NULL) {

*pNode =  (pBSTreeNode)malloc(sizeof(BSTreeNode));

(*pNode)->data = data;

(*pNode)->m_pLeft = NULL;

(*pNode)->m_pRight = NULL;

}

else if((*pNode)->data<data){

addBSTreeNode(&(*pNode)->m_pRight,  data);

}

else if((*pNode)->data>data){

addBSTreeNode(&(*pNode)->m_pLeft,  data);

}

}

//创建

void  createTree(){

BSTreeNode *pRoot = NULL;

    addBSTreeNode(&pRoot,10);

addBSTreeNode(&pRoot,6);

addBSTreeNode(&pRoot,14);

addBSTreeNode(&pRoot,4);

addBSTreeNode(&pRoot,8);

addBSTreeNode(&pRoot,12);

addBSTreeNode(&pRoot,16);

BinTreeToLinkList(pRoot);

}

时间: 04-08

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

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.把二元查找树转变成排序的双向链表

转载请注明出处: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

微软算法100题09 判断整数序列是不是二元查找树的后序遍历结果

9. 判断整数序列是不是二元查找树的后序遍历结果题目:输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果.如果是返回true,否则返回false.例如输入5.7.6.9.11.10.8,由于这一整数序列是如下树的后序遍历结果:8/ \6 10/ \ / \5 7 9 11因此返回true.如果输入7.4.6.5,没有哪棵树的后序遍历的结果是这个序列,因此返回false. 思路:如果一个数组为BST的后序遍历结果 则最后一个元素必然为该BST的根节点 因为BST的特性是左子树必然全部小

算法5-1:平衡查找树之二三树

平衡查找树的目标是实现查找.插入.删除操作在最坏情况下的复杂度均为logN. 本节将介绍二三查找树. 二三树中有两种节点: 二节点对应一个键,有两个子节点 三节点对应两个键,有三个子节点 二三查找树非常平衡,每个空节点到根节点的距离都是一样的 . 查找操作 在二三树中查找一个键的时候有以下规则: 如果是二节点,二节点对应1个值,如果要查找的值比该节点对应的值小,就往左侧深入,反之亦成 如果是三节点,三节点对应2个值,如果比两个值都小,就往左侧深入,如果介于两个值之间,就往中间深入,如果比两个值都

二元查找树的翻转(镜像)的两种思路

问题描述: 输入一颗二元查找树,将该树转换为它的镜像, 即在转换后的二元查找树中,左子树的结点都大于右子树的结点. 算法: 测试用例: 10 /             \ 5               11 /        \ 3            7 /     \         /   \ 2       4     6      9 /                       / 1                       8 算法: 有两种思路: ①递归.对树翻转,只