剑指offer之二叉搜索树和双向链表
1 问题
比如我们搜索二叉树如下,我们需要变成双向链表
2 分析
我们知道这个变成双向链接的时候是按照树的中序遍历打印的,我们只需要在中序遍历打印的时候操作该节点,我们可以用临时变量保存这个节点,同时我们也需要单独增加一个链表节点变量,我们需要保证这个节点的左边指向是该链表节点,然后该链表节点的右指向是这个节点,然后我们再把这个节点赋值给这个链表节点,就这样一直移动下去即可。
3 代码实现
我这里以下面的搜索二叉树进行操作的
4
2 6
1 3 5 7
#include <stdio.h>
#include <stdlib.h>
typedef struct Tree
{
int value;
struct Tree* left;
struct Tree* right;
} Tree;
/*
* 把搜索二叉树转成双向链表,我们按照中序遍历
*/
void convertNode(Tree* node, Tree** lastNodeList)
{
if (node == NULL)
return;
Tree* pCurrent = node;
if (pCurrent->left != NULL)
{
convertNode(pCurrent->left, lastNodeList);
}
//这里就要进行我们每个节点的前后正确的指向了
pCurrent->left = *lastNodeList;
if (*lastNodeList != NULL)
{
(*lastNodeList)->right = pCurrent;
}
*lastNodeList = pCurrent;
if (pCurrent->right != NULL)
{
convertNode(pCurrent->right, lastNodeList);
}
}
/*
* 把翻转好的双向链表尾巴节点移动到链表头
*/
Tree* convert(Tree* node, Tree* lastNodeList)
{
if (node == NULL || lastNodeList == NULL)
{
printf("node is NULL or lastNodeList is NULL\n");
return NULL;
}
Tree* last = NULL;
convertNode(node, &lastNodeList);
//因为这个时候lastNodeList已经到了双向链表尾巴,我们需要移动到链表头
Tree* headNodeList = lastNodeList;
while (headNodeList != NULL && headNodeList->left != NULL)
{
headNodeList = headNodeList -> left;
}
return headNodeList;
}
/*
* 双向链表从左到右打印
*/
void printRightList(Tree* headNodeList)
{
if (headNodeList == NULL)
{
printf("headNodeList is NULL\n");
return;
}
printf("we will print list from left to right\n");
Tree* pCurrent = headNodeList;
while (pCurrent != NULL)
{
printf("value is %d\n", pCurrent->value);
pCurrent = pCurrent->right;
}
}
/*
* 双向链表从右到左打印
*/
void printLeftList(Tree* headNodeList)
{
if (headNodeList == NULL)
{
printf("headNodeList is NULL\n");
return;
}
printf("we will print list from right to left\n");
Tree* pCurrent = headNodeList;
//先把链表头结点移动为链表的尾巴
while (pCurrent->right != NULL)
{
//printf("value is %d\n", pCurrent->value);
pCurrent = pCurrent->right;
}
//pCurrent = pCurrent->left;
while (pCurrent != NULL)
{
printf("value is %d\n", pCurrent->value);
pCurrent = pCurrent->left;
}
}
int main(void)
{
Tree *node1 , *node2 , *node3, *node4, *node5, *node6, *node7;
node1 = (Tree *)malloc(sizeof(Tree));
node2 = (Tree *)malloc(sizeof(Tree));
node3 = (Tree *)malloc(sizeof(Tree));
node4 = (Tree *)malloc(sizeof(Tree));
node5 = (Tree *)malloc(sizeof(Tree));
node6 = (Tree *)malloc(sizeof(Tree));
node7 = (Tree *)malloc(sizeof(Tree));
node1->value = 4;
node2->value = 2;
node3->value = 6;
node4->value = 1;
node5->value = 3;
node6->value = 5;
node7->value = 7;
node1->left = node2;
node1->right = node3;
node2->left = node4;
node2->right = node5;
node3->left = node6;
node3->right = node7;
node4->left = NULL;
node4->right = NULL;
node5->left = NULL;
node5->right = NULL;
node6->left = NULL;
node6->right = NULL;
node7->left = NULL;
node7->right = NULL;
Tree* list = (Tree *)malloc(sizeof(Tree));
if (!list)
{
printf("malloc list fail\n");
return -1;
}
Tree* firstNodeList = NULL;
//convertNode(node1, &list);
firstNodeList = convert(node1, list);
if (firstNodeList == NULL)
{
printf("firstNodeList is NULL\n");
return -1;
}
printRightList(firstNodeList);
printLeftList(firstNodeList);
return 0;
}
4 运行结果
we will print list from left to right
value is 0
value is 1
value is 2
value is 3
value is 4
value is 5
value is 6
value is 7
we will print list from right to left
value is 7
value is 6
value is 5
value is 4
value is 3
value is 2
value is 1
value is 0
赞 (0)