用C语言将二叉树转换为双向链表

树是一种重要的数据结构，尤其是二叉树。二叉树的用处比较广泛，用得最多的树就是二叉树。 二叉树的每个结点最多有两个子结点，左边的一般称为左孩子，右边的称为右孩子。根节点两边 的称为左子树和右子树。二叉树一般由递归的方法定义，所以处理二叉树的方法基本上都由递归

来处理。要学好树，必然的一定要对递归有一定的了解。

下面是我用C语言写的一个二叉树转换为双向链表的代码

#include <stdio.h> #include <stdlib.h> typedef struct tree { int data; struct tree *l,*r; }NODE; NODE * create_node(int data) //创建树的新结点 { NODE *p = malloc(sizeof(NODE)); p->data = data; p->l = p->r =NULL; return p; } NODE* create_tree(int i) //创建一个简易的二叉树，这里用递归 { NODE *root = create_node(i); if(2*i < 10) root->l = create_tree(2*i); if(2*i+1 < 10) root->r = create_tree(2*i+1); return root; } //将二叉树变换成为双向链表 NODE* tree_list(NODE *root,NODE** pHead,NODE **pTail)//pHead为总链表的头指针，pTail为总链表的尾指针 { NODE *pHeadLeft,*pTailLeft,*pHeadRight,*pTailRight;//树根左边的链表的头和尾以及右边链表的头和尾 if( NULL == root ) { *pHead = NULL; *pTail = NULL; return NULL; } if( NULL == root->l ) { *pHead = root; } else { tree_list(root->l,&pHeadLeft,&pTailLeft); //这里必须传指针的地址，不然链表的指针pHeadLeft和pTailLeft的值不会改变 *pHead = pHeadLeft; //将总链表头指向左子树的链表头 root->l = pTailLeft; //根节点的l指针指向左子树的链表尾 pTailLeft ->r = root; //左子树的链表尾的r指针指向根节点 } if( NULL == root->r) { *pTail = root; } else { //与左子树的相同，注意各个指针的指向 tree_list(root->r,&pHeadRight,&pTailRight); *pTail = pTailRight; root->r = pHeadRight; pHeadRight->l = root; } return *pHead; } void show_tree(NODE *root) //中序遍历二叉树 { if(NULL == root) return; show_tree(root->l); printf("%d-",root->data); show_tree(root->r); } void show_list(NODE *pHead) //遍历双向链表 { NODE *p = pHead; while(p) { printf("%d-",p->data); p = p->r; } return ; } int main(int argc, char *argv[]) { NODE *p = create_tree(1); //创建一个二叉树 show_tree(p); //中序遍历 puts(""); NODE *l=NULL,*r=NULL; NODE* q = tree_list(p,&l,&r); //将二叉树转换为双向链表 show_list(q); //遍历链表 return 0; }

运行结果为 8-4-9-2-5-1-6-3-7- 8-4-9-2-5-1-6-3-7-

根据得到的结果可以看到，这种方法转换出来的链表遍历顺序与二叉树的中序遍历得到的结果一样 当然将二叉树转换为链表还有很多种方法，可以用 栈和队列来处理。