剑指offer之面试题27二叉搜索树与双向链表

古城微笑少年丶 2022-07-24 04:02 116阅读 0赞

**问题描述**：

输入一颗二叉搜索树，将该二叉搜索树转换为一个排序的双向链表。

要求不能创建任何新的结点，只能调整树中结点指针的指向。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    struct Node{
    	int value;
    	struct Node *left;
    	struct Node *right;
    };
    
    typedef struct Node node;
    void doConvertNode(node *root,node **pLastNodeInList){ 
    	if(root==NULL)return;
    	node *currentNode = root;
    	if(currentNode->left!=NULL){
    		doConvertNode(currentNode->left,pLastNodeInList);
    	}
    	currentNode->left=*pLastNodeInList;
    	if(*pLastNodeInList!=NULL){
    		(*pLastNodeInList)->right=currentNode;
    	}
    	*pLastNodeInList=currentNode;
    	if(currentNode!=NULL){
    		doConvertNode(currentNode->right,pLastNodeInList);
    	}
    }
    
    
    node *convert(node *root){
    	if(root==NULL)return root;
    	node *pLastNodeInList = NULL;
    	doConvertNode(root,&pLastNodeInList);
    	node *head = pLastNodeInList;
    	while(head->left!=NULL){
    		head=head->left;
    	}
    	return head;
    }
    int main(int argc, char *argv[])
    {
    	node *root = (node *)malloc(sizeof(node));root->value=4;
    	node *rootleft=(node *)malloc(sizeof(node));rootleft->value=2;
    	node *rootright=(node *)malloc(sizeof(node));rootright->value=6;
    	node *leftleft=(node *)malloc(sizeof(node));leftleft->value=1;
    	node *leftright=(node *)malloc(sizeof(node));leftright->value=3;
    	node *rightleft=(node *)malloc(sizeof(node));rightleft->value=5;
    	root->left=rootleft;root->right=rootright;
    	rootleft->left=leftleft;rootleft->right=leftright;
    	rootright->left=rightleft;
    	leftleft->left=NULL;leftleft->right=NULL;
    	leftright->left=NULL;leftright->right=NULL;
    	rightleft->left=NULL;rightleft->right=NULL;
    	rootright->right=NULL;
    	
    	node *head=convert(root);
    
    	while(head->right!=NULL){
    		printf("%d\t",head->value);
    		head=head->right;
    	}
    	printf("%d\n",head->value);
    	while(head->left!=NULL){
    		printf("%d\t",head->value);
    		head=head->left;
    	}
    	printf("%d\n",head->value);
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51383498  
作者：WSYW126