二叉搜索树与双向链表

二叉搜索树与双向链表

题目:输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。

思路：采用中序遍历将二叉树从小到大遍历每一个结点，通过改变指针来实现双向链表。

#include<stdio.h>
#include "stdafx.h"
#include<tchar.h>

struct BinaryTreeNode
{
    int              m_nValue;
    BinaryTreeNode*  m_pLeft;
    BinaryTreeNode*  m_pRight;
};
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;
}
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}
void PrintTreeNode(BinaryTreeNode* pNode)
{
    if(pNode != NULL)
    {
        printf("value of this node is: %d\n", pNode->m_nValue);
       
        if(pNode->m_pLeft != NULL)
            printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
        else
            printf("left child is null.\n");
       
        if(pNode->m_pRight != NULL)
            printf("value of its right child is: %d.\n",pNode->m_pRight->m_nValue);
        else
            printf("right child is null.\n");
    }
    else
    {
        printf("this node is null.\n");
    }
    printf("\n");
}
void PrintTree(BinaryTreeNode* pRoot)
{
    PrintTreeNode(pRoot);
   
    if(pRoot != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);
       
        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}
void DestroyTree(BinaryTreeNode* pRoot)
{
    if(pRoot != NULL)
    {
        BinaryTreeNode* pLeft = pRoot->m_pLeft;
        BinaryTreeNode* pRight = pRoot->m_pRight;
       
        delete pRoot;
        pRoot = NULL;
       
        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = NULL;
    ConvertNode(pRootOfTree, &pLastNodeInList);
   
    //pLastNodeInList指向链表的的尾结点，遍历找到头结点返回。
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
        pHeadOfList = pHeadOfList->m_pLeft;
   
    return pHeadOfList;
}

//中序遍历转换过程，
//参数:处理当前结点， 当前链表最后一个结点(初始值为空)
void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
    if(pNode == NULL)
        return;
   
    BinaryTreeNode *pCurrent = pNode;
   
    //递归处理左子树
    if(pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);
   
    //将当前链表的左指针指向已经转换好的链表的最后一个位置   
    pCurrent->m_pLeft = *pLastNodeInList;
   
    //将已经转换好的链表的最后一个结点的右指针指向当前结点
    if(*pLastNodeInList != NULL)
        (*pLastNodeInList)->m_pRight = pCurrent;
   
    //更新链表最后一个结点
    *pLastNodeInList = pCurrent;
   
    //递归处理当前结点的右子树
    if(pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}

//打印双向链表
void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
{
    BinaryTreeNode* pNode = pHeadOfList;
   
    printf("The nodes from left to right are:\n");
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);
       
        if(pNode->m_pRight == NULL)
            break;
        pNode = pNode->m_pRight;
    }
    printf("\n");
}

void DestroyList(BinaryTreeNode* pHeadOfList)
{
    BinaryTreeNode* pNode = pHeadOfList;
    while(pNode != NULL)
    {
        BinaryTreeNode* pNext = pNode->m_pRight;
       
        delete pNode;
        pNode = pNext;
    }
}

//            10
//        /      \
//        6        14
//      /\        /\
//      4  8    12  16

int main()
{
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
    BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
   
    ConnectTreeNodes(pNode10, pNode6, pNode14);
    ConnectTreeNodes(pNode6, pNode4, pNode8);
    ConnectTreeNodes(pNode14, pNode12, pNode16);
   
    PrintTree(pNode10);
   
    BinaryTreeNode* pHeadOfList = Convert(pNode10);
   
    printf("The nodes from left to right are:\n");
    PrintDoubleLinkedList(pHeadOfList);
    printf("\n");
   
    DestroyList(pNode4);
}

本文永久更新链接地址：