首页 > 代码库 > 二叉排序树转化成双向链表

二叉排序树转化成双向链表

2024-07-16 01:58:35   219人阅读

题目描述：

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

输入：

输入可能包含多个测试样例。
对于每个测试案例，输入的第一行为一个数n(0<n<1000)，代表测试样例的个数。
接下来的n行，每行为一个二叉搜索树的先序遍历序列，其中左右子树若为空则用0代替。

输出：

对应每个测试案例，
输出将二叉搜索树转换成排序的双向链表后，从链表头至链表尾的遍历结果。

样例输入：
1
2 1 0 0 3 0 0
样例输出：
1 2 3
思路：
1.二叉排序树的特点就是一个结点的左子树比它小，右子树比它大，所以可以根据中序遍历得到一棵排序的序列。
2.若不能创建新结点，那么我们只能去修改原始二叉树的指针。这里我们让指向左子树的指针变为链表中指向前一个结点的指针，而指向右子树的指针变为链表中指向后一个结点的指针。
3.结合上面两点，很容易写出一个递归的算法。如下:

代码：

/*
二叉排序树转双向链表
by Rowandjj
2014/8/6
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _BNODE_
{
	int data;
	struct _BNODE_ *left;
	struct _BNODE_ *right;
}BNode,*pNode,*pTree;
//---------------------------------------
//其实是一个中序遍历的过程，因为中序遍历二叉排序树可以得到有序序列
void ConvertNode(pTree pRoot,pNode *pTail)
{ 
	if(pRoot == NULL)
	{
		return;
	}
	//左
	pNode pCur = pRoot;
	if(pCur->left != NULL)
	{
		ConvertNode(pCur->left,pTail);
	}
	//根 
	//left指针指向前一个，right指针指向后一个
	pCur->left = *pTail;
	if(*pTail != NULL)
	{
		(*pTail)->right = pCur;
	}
	*pTail = pCur;
	//右
	if(pCur->right != NULL)
	{
		ConvertNode(pCur->right,pTail);
	}
	
}
//将二叉排序树转化为双向链表,返回双向链表头指针
pNode Convert(pTree pRoot)
{
	if(pRoot == NULL)
	{
		return NULL;
	}
	pNode pTail = NULL;
	ConvertNode(pRoot,&pTail);
	pNode pHead = pTail;
	//根据双向链表的尾找到其头指针
	while(pHead != NULL && pHead->left != NULL)
	{
		pHead = pHead->left;
	}
	//返回双向链表头指针
	return pHead;
}
//遍历双向链表
void DisplayLinkedList(pNode pHead)
{
	if(pHead == NULL)
	{
		return;
	}
	pNode pTemp = pHead;
	while(pTemp != NULL)
	{
		printf("%d ",pTemp->data);
		pTemp = pTemp->right;
	}
	printf("\n");
}
//销毁双向链表
void DestroyList(pNode *pHead)
{
	if(*pHead == NULL)
	{
		return;
	}
	pNode p = *pHead,q;
	while(p != NULL)
	{
		q = p->right;
		free(p);
		p = q;
	}
	pHead = NULL;
}
//---------------------------------------
//先序构建二叉树
void CreateTree(pTree *pRoot)
{
	int data;
	scanf("%d",&data);
	if(data =http://www.mamicode.com/= 0)>
部分函数并没有使用，可以去掉


联系
我们