二元查找树转有序双向链表

[cpp] view plaincopyprint?// 二元查找树转有序的双向链表.cpp : Defines the entry point for the console application.
//
//题目：把二元查找树转变成排序的双向链表
//要求：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
//要求不能创建任何新的结点，只调整指针的指向。
/* 将下面这个二元查找树转化成
            10
            / \
           6   14
          /\   /\
         4 8 12 16

    4=6=8=10=12=14=16 这个双向链表

*/

/*
什么是二元查找树？
二元查找树：它首先要是一棵二元树，在这基础上它或者是一棵空树；
或者是具有下列性质的二元树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二元查找树
如何构造一个二元查找树？
和一般二叉树构造方式类似，只是需要满足上述条件
元素插入时利用递归，找到合适的插入位置
定义树节点结构
struct BSTreeNode
{
    int value；
    BTreeNode *left;
    BTreeNode *right;
}
思路：通过观察可以发现，二元查找树的中序遍历结果就是一个有序的数列，
这样只需要对树进行一次中序遍历，同时调整指针成为一个双向链表即可
*/
#include "stdafx.h"
#include <iostream>
using namespace std;
struct BSTreeNode
{
    int value;
    BSTreeNode *left;
    BSTreeNode *right;
};
BSTreeNode *pHead=NULL; //指向双向链表头结点
BSTreeNode *pIndex=NULL;//保存当前访问节点的前一个节点
//比如当前访问节点6，那么pIndex指向的是4
void AddBSTreeNode(BSTreeNode **pRoot,int value)
{
    if(NULL==*pRoot)
    {
        BSTreeNode *tmpNode=new BSTreeNode;
        tmpNode->value=value;
        tmpNode->left=NULL;
        tmpNode->right=NULL;
        *pRoot=tmpNode;
    }
    else if((*pRoot)->value<value)
    {
        AddBSTreeNode(&(*pRoot)->right,value);
    }
    else if((*pRoot)->value>value)
    {
        AddBSTreeNode(&(*pRoot)->left,value);
    }
}
//中序遍历，同时调整节点指针
void InOrderAdjust(BSTreeNode* pBSTree)
{
    if(NULL==pBSTree)
        return;
    //递归访问左子
    if(NULL!=pBSTree->left)
        InOrderAdjust(pBSTree->left);
    //调整节点指针

    pBSTree->left=pIndex;//将当前访问节点的左指针指向前一个节点
    if(NULL==pIndex)//如果前一个节点是空，说明是第一次访问
        pHead=pBSTree;//此时的节点应作为双向链表的表头节点
    else
        pIndex->right=pBSTree;//将前一个节点右指针指向当前节点，这样便构成了一个双向链表
    pIndex=pBSTree;
    //递归访问右子
    if(NULL!=pBSTree->right)
        InOrderAdjust(pBSTree->right);
}
//输出结果验证
void Print(BSTreeNode *pHead)
{
    if(pHead==NULL)
        return;
    BSTreeNode *pTmp;
    cout<<"顺序遍历："<<endl;
    while(pHead!=NULL)
    {
        pTmp=pHead;
        cout<<pHead->value<<" ";
        pHead=pHead->right;
    }
    cout<<endl;
    cout<<"逆序遍历："<<endl;
    while(pTmp!=NULL)
    {
        cout<<pTmp->value<<" ";
        pTmp=pTmp->left;
    }
    cout<<endl;
}
int _tmain(int argc, _TCHAR* argv[])
{
    BSTreeNode *pRoot=NULL;
    AddBSTreeNode(&pRoot,10);
    AddBSTreeNode(&pRoot,6);
    AddBSTreeNode(&pRoot,14);
    AddBSTreeNode(&pRoot,4);
    AddBSTreeNode(&pRoot,8);
    AddBSTreeNode(&pRoot,12);
    AddBSTreeNode(&pRoot,16);
    InOrderAdjust(pRoot);
    Print(pHead);
    system("pause");
    return 0;
}

// 二元查找树转有序的双向链表.cpp : Defines the entry point for the console application.
//
//题目：把二元查找树转变成排序的双向链表
//要求：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
//要求不能创建任何新的结点，只调整指针的指向。
/* 将下面这个二元查找树转化成
   10
   / \
     6   14
    /\   /\
   4 8 12 16

    4=6=8=10=12=14=16 这个双向链表

*/

/*
什么是二元查找树？
二元查找树：它首先要是一棵二元树，在这基础上它或者是一棵空树；
或者是具有下列性质的二元树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二元查找树
如何构造一个二元查找树？
和一般二叉树构造方式类似，只是需要满足上述条件
元素插入时利用递归，找到合适的插入位置
定义树节点结构
struct BSTreeNode
{
int value；
BTreeNode *left;
BTreeNode *right;
}
思路：通过观察可以发现，二元查找树的中序遍历结果就是一个有序的数列，
这样只需要对树进行一次中序遍历，同时调整指针成为一个双向链表即可
*/
#include "stdafx.h&qu

补充：软件开发 , C++ ,