搜索二叉树与双向链表的相互转换

一、将一颗搜索二叉树转换成有序的双向链表

1、问题描述

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

2、解题思路

首先，让我们来回顾一下搜索二叉树的结构一些相关特点： （1）在二叉搜索树中，每个结点都有两个分别指向其左、右子树的指针； （2）左子树结点的值总是小于父结点的值，右子树结点的值总是大于父结点的值。 该结构特点可以类比到双向链表中： 在双向链表中，每个结点也有两个指针，它们分别指向前一个结点和后一个结点。

所以这两种数据结构的结点是一致，二叉搜索树之所以为二叉搜索树，双向链表之所以为双向链表，只是因为两个指针的指向不同而已，通过改变其指针的指向来实现是完全可能的。

如下图所示： 具体实现步骤： 原先指向左子结点的指针调整为链表中指向前一个结点的指针，原先指向右子结点的指针调整为链表中指向下一个结点的指针。 具体转换过程：按照中序遍历的方法遍历二叉搜索树，可以将该二叉树分为三个部分：根节点、左子树和右子树，当遍历结点值为4的节点时，将它分为以2为节点的左子树和以6为节点的右子树，并将4的左指针指向值为3的结点，值为3的节点的右指针指向值为4的结点，因为采用的是中序遍历，所以当遍历到根节点的时候，它的左子树已经遍历结束了，所以要对所有的子树采用递归的执行上述操作

代码实现部分：

/* //二叉树结点结构 struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: TreeNode* Convert(struct TreeNode* pRootOfTree) { TreeNode* pNode = NULL; _BST2List(pRootOfTree,&pNode); TreeNode* pHead = pNode; while (pHead!=NULL&&pHead->left!=NULL) pHead = pHead->left; return pHead; } void _BST2List(TreeNode* pRoot, TreeNode**pRev) { if (NULL == pRoot) return; TreeNode*pCur=pRoot; if(pCur->left!=NULL)//递归左子树 _BST2List(pCur->left,pRev); pCur->left=*pRev; if(*pRev!=NULL) (*pRev)->right=pCur; *pRev=pCur; if(pCur->right!=NULL) _BST2List(pCur->right,pRev); } };

二、将一条有序的单链表转换成搜索二叉树

1、问题描述

给定一个升序排列的有序单链表，将其转换为一棵平衡的二叉搜索树。

2、算法思路

1、首先遍历链表，统计节点个数 2、首先我们通过下标找出中间的那个数作为根节点，假设下表为x 3、那么下标0~x-1的数肯定比x小，x+1~n-1的数比x大，将其分成三段 4、新建根节点root的值为下标X的数值，然后root的左孩子的值就是等于下标0~x-1的中间的下标的值，而右孩子就是x+1~n中间的下标的值，去到这一步大家都知道其实就是重复着2跟3，不停的递归下去，只要设置好递归的退出就能轻易转化好这个BST

3、具体代码实现

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode *sortedListToBST(ListNode *head) { int size = 0; ListNode *pCur = head; while (pCur) //遍历节点统计链表长度 { size++; pCur = pCur->next; } pCur = head; ListNode *list = head; return buildTree(list,size); } TreeNode *buildTree(ListNode *&list,int size) { if (size == 0) return NULL; TreeNode *head = new TreeNode(0); head->left = buildTree(list,size / 2); //递归建立左子树 head->val = list->val; list = list->next; head->right = buildTree(list,size - size / 2 - 1); //递归建立右子树 return head; } };