二叉搜索树与双向链表
题目:输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。
思路：采用中序遍历将二叉树从小到大遍历每一个结点，通过改变指针来实现双向链表。
#include
#include "stdafx.h"
#include
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: %dn", 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("%dt", 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);
}
查看评论 回复