将二叉搜索树转为一个排好序的双向链表

╰半橙微兮° 2022-12-27 01:15 88阅读 0赞

这道题在面试中比较常见，原因有几个

1.要涉及到二叉树的中序遍历。

2.考察了二叉排序树的特点。

3.考察了双向链表。

4.大量考察了指针的使用，以及递归思想。

大致的解题思想如下：

1.进行中序遍历

2.完成上一个节点和当前节点的 二叉树和链表的左右指针关系的转化。

2.1 原先指向左子节点的指针 调整为链表中指向前一个节点的指针

2.2 原先指向右子节点的指针 调整为链表中指向后一个节点的指针

我们的调整策略是两个点两个点之间进行调整 一次只会调整两个节点 不会调整到三个

具体看下代码：

BinaryTree.h如下代码所示：

#pragma once
    struct BinaryTreeNode
    {
    	int m_value;
    	struct BinaryTreeNode* m_left;
    	struct BinaryTreeNode* m_right;
    };
    //二叉树结点的创建
    struct BinaryTreeNode* CreateBinaryNode(int value);
    
    //二叉树结点的连接
    void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild);
    
    //二叉树结点的打印
    void PrintBinaryNode(const struct BinaryTreeNode*node);
    
    //二叉树结点的销毁
    void DestroyBinaryNode(struct BinaryTreeNode*node);
    
    //整个二叉树的销毁
    void DestroyBinary(struct BinaryTreeNode*node);
    
    //转化函数开头
    BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree);
    
    //将二叉排序树转化为双向链表 输出双向链表的尾节点
    void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);
    
    //对双向链表进行双向打印
    void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList);

BinaryTree.cpp

#include"BinaryTree.h"
    #include<cstdio>
    #include<queue>
    #include<stack>
    //二叉树结点的创建
    struct BinaryTreeNode* CreateBinaryNode(int value)
    {
    	struct BinaryTreeNode*pNode = new BinaryTreeNode();
    	pNode->m_value = value;
    	pNode->m_left = nullptr;
    	pNode->m_right = nullptr;
    
    	return pNode;
    }
    
    //二叉树结点的连接
    void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild)
    {
    	if (Parent != NULL)
    	{
    		Parent->m_left = lchild;
    		Parent->m_right = rchild;
    	}
    }
    
    //二叉树结点的打印
    void PrintBinaryNode(const struct BinaryTreeNode*node)
    {
    	if (node != nullptr)
    	{
    		printf("node value is[%d]\n",node->m_value);
    	}
    	else
    	{
    		printf("this node is nullptr\n");
    	}
    }
    
    
    
    
    //二叉树结点的销毁
    void DestroyBinary(struct BinaryTreeNode*node)
    {
    	if (node != nullptr)
    	{
    		struct BinaryTreeNode*pleft = node->m_left;
    		struct BinaryTreeNode*pright = node->m_right;
    
    		delete node;
    		node = nullptr;
    
    		if (pleft != nullptr)
    		{
    			DestroyBinary(pleft);
    		}
    
    		if (pright != nullptr)
    		{
    			DestroyBinary(pright);
    		}
    
    
    	}
    }
    
    
    BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
    {
    	BinaryTreeNode *pLastNodeInList = nullptr;
    	ConvertNode(pRootOfTree, &pLastNodeInList);
    
    	// pLastNodeInList指向双向链表的尾结点，
    	// 我们需要返回头结点
    	BinaryTreeNode *pHeadOfList = pLastNodeInList;
    	while (pHeadOfList != nullptr && pHeadOfList->m_left != nullptr)
    		pHeadOfList = pHeadOfList->m_left;
    
    	return pHeadOfList;
    }
    
    
    /*
    10
    /  \
    6   14
    */
    void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
    {
    	if (pNode == nullptr)
    		return;
    
    	BinaryTreeNode *pCurrent = pNode;
    
    	if (pCurrent->m_left != nullptr)
    		ConvertNode(pCurrent->m_left, pLastNodeInList);
    
    	//处理当前节点和上一个节点之间的双向链表关系
    	pCurrent->m_left = *pLastNodeInList;
    	if (*pLastNodeInList != nullptr)
    		(*pLastNodeInList)->m_right = pCurrent;
    
    	//把指针指向当前节点，进行循环操作
    	*pLastNodeInList = pCurrent;
    
    	if (pCurrent->m_right != nullptr)
    		ConvertNode(pCurrent->m_right, pLastNodeInList);
    }
    
    
    void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
    {
    	BinaryTreeNode* pNode = pHeadOfList;
    
    	printf("The nodes from left to right are:\n");
    	while (pNode != nullptr)
    	{
    		printf("%d\t", pNode->m_value);
    
    		if (pNode->m_right == nullptr)
    			break;
    		pNode = pNode->m_right;
    	}
    
    	printf("\nThe nodes from right to left are:\n");
    	while (pNode != nullptr)
    	{
    		printf("%d\t", pNode->m_value);
    
    		if (pNode->m_left == nullptr)
    			break;
    		pNode = pNode->m_left;
    	}
    
    	printf("\n");
    }

测试代码如下：

#include"BinaryTree.h"
    #include<cstdio>
    
    //手动的创建如下树
    /*
    		10
    	  /    \
    	 6	    14
       /  \    /  \
      4	   8  12  16
    */
    
    
    
    int main(int argc, char*argv[])
    {
    	struct BinaryTreeNode* node1 = CreateBinaryNode(10);
    	struct BinaryTreeNode* node2 = CreateBinaryNode(6);
    	struct BinaryTreeNode* node3 = CreateBinaryNode(14);
    	struct BinaryTreeNode* node4 = CreateBinaryNode(4);
    	struct BinaryTreeNode* node5 = CreateBinaryNode(8);
    	struct BinaryTreeNode* node6 = CreateBinaryNode(12);
    	struct BinaryTreeNode* node7 = CreateBinaryNode(16);
    
    
    	ConnectBinaryNode(node1, node2, node3);
    	ConnectBinaryNode(node2, node4, node5);
    	ConnectBinaryNode(node3, node6, node7);
    
    
    
    	/*BinaryTreeToDoublyListMain(node1);
    	struct BinaryTreeNode*tmp = node1;*/
    	struct BinaryTreeNode*tmp =Convert(node1);
    	//打印这个双向链表 从表头
    	PrintDoubleLinkedList(tmp);
    	//二叉排序树转为为双向链表
    
    
    	return 0;
    }