现在的位置: 首页 > 综合 > 正文

将二叉树转换成双向链表

2017年12月07日 ⁄ 综合 ⁄ 共 475字 ⁄ 字号 评论关闭

思路:采用中序遍历的方法,visit函数需要完成的功能为:

1、当前节点的左子节点指向上一次访问的节点;

2、将上一次访问节点的右子节点指向当前节点;

3、最后更新上一次访问节点为当前节点。

在第二步时需要判断上一次访问节点是不是为NULL,如果是,则第二步改为链表的头结点指向当前节点。

程序如下:

struct BSTnode
{
	int data;
	BSTnode * left;
	BSTnode * right;
}*pList,*pHead;


void visit(BSTnode * pCurrent)
{
	pCurrent->left = pList;//*当前节点的左子节点指向上一次访问的节点;*//
	if (pList != NULL)
		pList->right = pCurrent;//将上一次访问节点的右子节点指向当前节点//
	else 
		pHead = pCurrent;
	pList = pCurrent;
}

void inorder(BSTnode* root)
{
	
	if (root != NULL)
	{
		inorder(root->left);
		visit(root);
		inorder(root->right);
	}
}

抱歉!评论已关闭.