6-03 3,617 views
对于二叉搜索树，可以将其转换为双向链表，其中，节点的左子树指针在链表中指向前一个节点，右子树指针在链表中指向后一个节点。
思路：
采用递归思想，对于二叉搜索树，将左、右子树分别转换为双向链表，左子树转换所得链表的头结点即整个树的头结点，左子树转换所得链表的尾节点与根节点相邻；右子树转换所得链表的尾节点即整个树的尾节点，右子树转换所得链表的头结点与根节点相邻。
代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 |
#include <stdlib.h> #include <stdio.h> typedef struct TNode { int value; TNode* lchild; TNode* rchild; }TNode,*BTree; //二叉树转换为双向链表 TNode* TreeToList(BTree tree,TNode* &lastNode) { TNode* head; //若树为空，返回空 if (tree == NULL) { lastNode = NULL; return NULL; } //若无左子树，则该根节点为链表的头结点 if (tree->lchild==NULL) { head = tree; } //若有左子树，递归调用转换函数将左子树转换为双向链表 //左子树转换所得链表的头结点是整个树的头结点 //左子树链表的尾结点与根节点相邻 else { head = TreeToList(tree->lchild,lastNode); tree->lchild = lastNode; lastNode->rchild = tree; } //若无右子树，则该根节点为链表的尾结点 if (tree->rchild==NULL) { lastNode = tree; } //若有右子树，递归调用转换函数将左子树转换为双向链表 //右子树转换所得链表的尾结点是整个树的尾结点 //右子树链表的头结点与根节点相邻 else { tree->rchild = TreeToList(tree->rchild,lastNode); tree->rchild->lchild = tree; } return head; } int main() { BTree tree = (BTree)malloc(sizeof(TNode)); tree->value = 4; tree->lchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->value = 2; tree->lchild->lchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->lchild->value = 1; tree->lchild->lchild->lchild = NULL; tree->lchild->lchild->rchild = NULL; tree->lchild->rchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->rchild->value = 3; tree->lchild->rchild->lchild = NULL; tree->lchild->rchild->rchild = NULL; tree->rchild = (TNode*)malloc(sizeof(TNode)); tree->rchild->value = 6; tree->rchild->lchild = (TNode*)malloc(sizeof(TNode)); tree->rchild->lchild->value = 5; tree->rchild->lchild->lchild = NULL; tree->rchild->lchild->rchild = NULL; tree->rchild->rchild = NULL; TNode* lastNode; TNode* listHead = TreeToList(tree,lastNode); TNode* node = listHead; while(node) { printf("%d ",node->value); node = node->rchild; } printf("\n"); return 0; } |
