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
