二叉树转换成双向链表

喝酒伤身，健康第一。

将一棵二叉树转换成双向链表。

递归解决思路：

1. 先将左子树转换成一个双向链表list1
2. 再将右子树转换成一个双向链表list2
3. 最后将list1+根节点+list2合成一个链表

code

// function:binary tree to double directed linklist
template<typename T>
std::pair<btnode<T>*,btnode<T>*> binarytree<T>::_BinaryTreeToDoubleDirectedLinkedList(btnode<T>* p)
{
	std::pair<btnode<T>*,btnode<T>*> right,left ;
	if(p == NULL)
	{
		left = std::make_pair(p,p); 
		return left;
	}
	else
	{
		if(p->Lchild)
		{
			left = this->_BinaryTreeToDoubleDirectedLinkedList(p->Lchild);
			left.second->Rchild = p;
			p->Lchild = left.second;
		}
		if(p->Rchild)
		{
			right = this->_BinaryTreeToDoubleDirectedLinkedList(p->Rchild);
			right.first->Lchild = p;
			p->Rchild = right.first;
		}
		if(p->Lchild && p->Rchild)
		{
			return std::make_pair(left.first,right.second);
		}
		else if(! p->Lchild && p->Rchild)
		{
			return std::make_pair(p,right.second);
		}
		else if(p->Lchild && ! p->Rchild)
		{
			return std::make_pair(left.second,p);
		}
		else return std::make_pair(p,p);
	}
}

binary-tree.h

#include <iostream>
#include <utility>
#include <string>
#include <cmath>
using namespace std;



template<typename T>
class btnode
{
public:
	T key;
	btnode * Lchild;
	btnode * Rchild; 

	// function:make function
	btnode( );
};


template<typename T>
btnode<T>::btnode()
{
	key = -1;
	Lchild = NULL;
	Rchild = NULL;
};


template<typename T>
class binarytree
{
public:

	// var:R id the root of the tree
	btnode<T> * R;
	
	// function:make function
	binarytree();

	// function:make tree 
	void _maketree(T * data,size_t s);

	// function:insert key into tree
	void _insert(btnode<T> * *bt,T d);

	// function:visit node p
	void _visit(btnode<T> * p);

	// fucntion:preorder visit tree
	void _preOrderTraver(btnode<T> * p);

	// fucntion:inorder visit tree
	void _inOrderTraver(btnode<T> * p);

	// fucntion:postorder visit tree
	void _postOrderTraver(btnode<T> * p);

	// function:whether is balanced binary tree
	std::pair<size_t,bool> _IsBalancedBinaryTree(btnode<T> *p);

	// function:binary tree to double directed linklist
	std::pair<btnode<T>*,btnode<T>*> _BinaryTreeToDoubleDirectedLinkedList(btnode<T>*p);

	// function:show the linkedlist
	void  binarytree<T>::ShowLinklist(btnode<T>* p);

};


// function:make function
template<typename T>
binarytree<T>::binarytree()
{
	this->R = NULL;
};


// function:make tree
// input:an array of data and its length
// output: a binary tree
template<typename T>
void binarytree<T>::_maketree(T * data,size_t s)
{
	for(size_t i= 0;i<s;i++)
	{
		this->_insert(&(this->R),data[i]);
	}
};

// function:insert key into tree
template<typename T>
void binarytree<T>::_insert(btnode<T> * *bt,T d)
{
	if((*bt) == NULL)
	{
		(*bt) = new btnode<T>;
		(*bt) -> key = d;
	}		
	else
	{
		btnode<T> * p = *bt ;
		if(d < p->key)
		{
			this->_insert(&(p->Lchild),d);
		}
		else if(d>p->key)
		{
			this->_insert(&(p->Rchild),d);
		}
		else
		{
			cout<<d<<" has been inserted"<<endl;
		}
	}
};


// function:visit node p
template<typename T>
void binarytree<T>::_visit(btnode<T> * p)
{
	if(p != NULL)
	{
		cout<<"key="<<p->key<<endl;
	}
	else
	{
		cout<<"node point null"<<endl;
	}
};

// fucntion:preorder visit tree
template<typename T>
void binarytree<T>::_preOrderTraver(btnode<T> * p)
{
	if(p != NULL )
	{
		this->_visit(p);
		this->_preOrderTraver(p->Lchild);
		this->_preOrderTraver(p->Rchild);	
	}
};

// fucntion:inorder visit tree
template<typename T>
void binarytree<T>::_inOrderTraver(btnode<T> * p)
{
	if(p != NULL )
	{	
		this->_inOrderTraver(p->Lchild);
		this->_visit(p);
		this->_inOrderTraver(p->Rchild);	
	}
};

// fucntion:postorder visit tree
template<typename T>
void binarytree<T>::_postOrderTraver(btnode<T> * p)
{
	if(p != NULL )
	{	
		this->_postOrderTraver(p->Lchild);
		this->_postOrderTraver(p->Rchild);
		this->_visit(p);			
	}
};

// function:whether is balanced binary tree
template<typename T>
std::pair<size_t,bool> binarytree<T>::_IsBalancedBinaryTree(btnode<T> *p)
{
	if( p == NULL )
		return std::make_pair(0,true);
	else 
	{
		std::pair<size_t,bool> r = this -> _IsBalancedBinaryTree(p->Rchild);
		std::pair<size_t,bool> l = this -> _IsBalancedBinaryTree(p->Lchild);
		int h = (int)(r.first) - (int)(l.first);
		h = abs(h);
		if(h>1)
			return std::make_pair(max(r.first,l.first)+1,false);
		else return std::make_pair(max(r.first,l.first)+1,r.second && l.second);
	}

};


// function:binary tree to double directed linklist
template<typename T>
std::pair<btnode<T>*,btnode<T>*> binarytree<T>::_BinaryTreeToDoubleDirectedLinkedList(btnode<T>* p)
{
	std::pair<btnode<T>*,btnode<T>*> right,left ;
	if(p == NULL)
	{
		left = std::make_pair(p,p); 
		return left;
	}
	else
	{
		if(p->Lchild)
		{
			left = this->_BinaryTreeToDoubleDirectedLinkedList(p->Lchild);
			left.second->Rchild = p;
			p->Lchild = left.second;
		}
		if(p->Rchild)
		{
			right = this->_BinaryTreeToDoubleDirectedLinkedList(p->Rchild);
			right.first->Lchild = p;
			p->Rchild = right.first;
		}
		if(p->Lchild && p->Rchild)
		{
			return std::make_pair(left.first,right.second);
		}
		else if(! p->Lchild && p->Rchild)
		{
			return std::make_pair(p,right.second);
		}
		else if(p->Lchild && ! p->Rchild)
		{
			return std::make_pair(left.second,p);
		}
		else return std::make_pair(p,p);
	}
}


// function:show the linkedlist
template<typename T>
void  binarytree<T>::ShowLinklist(btnode<T>* p)
{
	cout<<"list data follows"<<endl;
	while(p)
	{
		cout<<p->key<<endl;
		p = p->Rchild;
	}
}

test.cpp

#include <iostream>
#include "b-tree.h"
using namespace std;

// function:input data
std::pair<int*,size_t> Inputdata();

int main()
{
	// tree has the root : tree::R
	binarytree<int> * T = new binarytree<int>;
	//int size = 10;
	//int * data = new int[size];
	//for(int i=0;i<size;i++)
	//{
	//	data[i] = rand()%20;
	//}
	int data[9] = {4,7,3,2,8,6,5,9,10};
	std::pair<int*,size_t> d = Inputdata();
	T->_maketree(d.first,d.second);
	cout<<"preorder traversal"<<endl;
	T->_preOrderTraver(T->R);
	cout<<"inorder traversal"<<endl;
	T->_inOrderTraver(T->R);
	cout<<"postorder traversal"<<endl;
	T->_postOrderTraver(T->R);
	std::pair<size_t,bool> r=T->_IsBalancedBinaryTree(T->R);
	cout<<"whether it is balanced binary tree,result is "<<r.second<<endl;

	T->ShowLinklist(T->_BinaryTreeToDoubleDirectedLinkedList(T->R).first);
	
	

	
	system("pause");
	return 0;
}

// function:input data
std::pair<int*,size_t> Inputdata()
{
	size_t s = 0;
	cout<<"please input the number(>=0) of data,size = "<<endl;
	cin>>s;
	std::pair<int*,size_t> r;
	int * p = NULL;
	if(s == 0)
	{
		r = std::make_pair(p,0);
		return r;
	}
	else
	{
		p = new int[s];
		cout<<"please input data"<<endl;
		for(size_t i = 0; i<s; i++)
		{
			cin>>p[i];
		}
		cout<<"ok,data input over"<<endl;
		r = std::make_pair(p,s);
		return r;
	}
}

面试题之剑指offer 二叉树转换成双向链表

原文：http://blog.csdn.net/cqs_experiment/article/details/18899497