二叉树变双向链表

以下为源码,结束时,分别以正序和逆序输出链表:

输出为:

11 12 13 14 15 36
36 15 14 13 12 11

基本想法为先搞定左子树的,连接好指针,再搞定右子树,连接相关指针。

---------------------------

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
using namespace std;

typedef struct tree_node_s {
int data;
struct tree_node_s *lchild;
struct tree_node_s *rchild;
}tree_node_t;

tree_node_t *changeToListUtil(tree_node_t *root) {
if (NULL == root)
return NULL;
if (root->lchild) {
tree_node_t *left = changeToListUtil(root->lchild);
while(left->rchild) {
left = left->rchild;
}
root->lchild = left;
left->rchild = root;
}
if (root->rchild) {
tree_node_t *right = changeToListUtil(root->rchild);
while (right->lchild) {
right = right->lchild;
}
root->rchild = right;
right->lchild = root;
}
return root;
}

tree_node_t *changeToList(tree_node_t *root) {
if (NULL == root)
return NULL;
root = changeToListUtil(root);
while (root->lchild)
root = root->lchild;
return root;
}

void printList(tree_node_t *head) {
tree_node_t *tail=NULL;
while (head) {
cout << head->data << ” “;
head = head->rchild;
if(head != NULL) tail = head ;
}
cout << std::endl;
while(tail) {
cout << tail->data <<” “;
tail = tail->lchild;
}
}

tree_node_t *createNode(int data) {
tree_node_t *temp = (tree_node_t*)malloc(sizeof(tree_node_t));
temp->data = data;
temp->lchild = NULL;
temp->rchild = NULL;
return temp;
}

int main(int argc, char *argv[]) {
tree_node_t *root     = createNode(14);
root->lchild          = createNode(12);
root->rchild          = createNode(15);
root->lchild->lchild  = createNode(11);
root->lchild->rchild  = createNode(13);
root->rchild->rchild  = createNode(36);

tree_node_t *head = changeToList(root);
printList(head);
return 0;
}



本文地址: http://www.bagualu.net/wordpress/archives/3612 转载请注明




发表评论

电子邮件地址不会被公开。 必填项已用*标注