合并两棵二叉树代码,C代码库,德仔网

代码语言
代码分类
【C】合并两棵二叉树
作者:n.comoon / 发布于2012/6/12/ 722
合并两棵二叉树
<div>/*
* This is a small program to create indexs for two binary trees and combine them to a new
* index tree and output the new tree,the second tree only has the left child tree then
* if the first tree has no left child tree,insert the second tree into the first tree as 
* its left child and if the first tree has the left child tree,then insert the first tree 
* into the second tree as its left child.
*n.comoon
*
* Apr.13th.2012
*/
#include<stdio.h></div>
<div></div>
<div>typedef struct binary_tree
{
char ch;
struct binary_tree * left;
struct binary_tree * right;
int left_tag;
int right_tag;
}binary_tree;</div>
<div></div>
<div>/*
* a global value to save the previous node in recurssion
*/
binary_tree * pre_tree;</div>
<div></div>
<div>binary_tree * create_tree()
{
char ch;
binary_tree * tmp_tree;
printf("please input the data for the node!\n");
scanf("%c",&ch);
getchar();
if(ch=='#')
{
tmp_tree=NULL;
}
else
{
tmp_tree=(binary_tree *)malloc(sizeof(binary_tree));
tmp_tree->ch=ch;
tmp_tree->left_tag=0;
tmp_tree->right_tag=0;
tmp_tree->left=create_tree();
tmp_tree->right=create_tree();
}
return tmp_tree;
}
<div></div>
<div>void print_tree(binary_tree * my_tree,int spaces)
{
/*
* print the tree which is before creating index
*/
int i;
if(my_tree==NULL)
{
return;
}
print_tree(my_tree->right,spaces+1);
for(i=0;i<spaces;i++)
{
printf(" ");
}
printf("%c\n",my_tree->ch);
print_tree(my_tree->left,spaces+1);
}
<div></div>
<div>void print_newtree(binary_tree * my_tree,int spaces)
{
/*
* print the tree which is after creating index
*/
int i;
if(my_tree->right_tag!=1)
{
print_newtree(my_tree->right,spaces+1);
}
for(i=0;i<spaces;i++)
{
printf(" ");
}
printf("%c\n",my_tree->ch);
if(my_tree->left_tag!=1)
{
print_newtree(my_tree->left,spaces+1);
}
}
<div></div>
<div>void inorder_theard(binary_tree * my_tree)
{
/*
* create the index for a binary tree with inorder travel
*/
if(my_tree!=NULL)
{
if(my_tree->left_tag==0)
{
inorder_theard(my_tree->left);
}
if(my_tree->left==NULL)
{
my_tree->left_tag=1;
my_tree->left=pre_tree;
}
if(pre_tree->right==NULL)
{
pre_tree->right_tag=1;
pre_tree->right=my_tree;
}
pre_tree=my_tree;
if(my_tree->right_tag==0)
{
inorder_theard(my_tree->right);
}
}
}
<div></div>
<div>binary_tree * insert_tree(binary_tree * first_tree,binary_tree * second_tree)
{
binary_tree * tmp_tree;
if(first_tree->left_tag==1)
{
/*
 * if the first tree has no left child
 */
first_tree->left_tag=0;
first_tree->left=second_tree;
second_tree->right=first_tree;
tmp_tree=second_tree;
while(tmp_tree->left_tag!=1)
{
tmp_tree=tmp_tree->left;
}
tmp_tree->left=first_tree;
return first_tree;
}
else
{
/*
 * if the first tree has the left child
 */
second_tree->right_tag=0;
second_tree->right=first_tree;
tmp_tree=first_tree;
while(tmp_tree->left_tag!=1)
{
tmp_tree=tmp_tree->left;
}
tmp_tree->left=second_tree;
tmp_tree=first_tree;
while(tmp_tree->right_tag!=1)
{
tmp_tree=tmp_tree->right;
}
tmp_tree->right=second_tree;
return second_tree;
}
}
<div></div>
<div>int main()
{
binary_tree * first_tree, * second_tree, * new_tree;
printf("creating the first tree!\n");
first_tree=create_tree();
printf("the first tree you input is as following!\n");
print_tree(first_tree,1);
printf("creating the second tree!(the second tree can only have left child tree)\n");
second_tree=create_tree();
if(second_tree->right!=NULL)
{
printf("the second tree input error!\n");
exit(1);
}
printf("the second tree you input is as folowing!\n");
print_tree(second_tree,1);</div>
<div>/*
 * create the index for the first binary tree
 */
pre_tree=first_tree;
inorder_theard(first_tree);
/*
 * fill in the descender of the last node with the first node
 */
pre_tree->right_tag=1;
pre_tree->right=first_tree;</div>
<div>/*
 * create the index for the second binary tree
 */
pre_tree=second_tree;
inorder_theard(second_tree);
/*
 * fill in the descender of the last node with the first node
 */
pre_tree->right_tag=1;
pre_tree->right=second_tree;</div>
<div>new_tree=insert_tree(first_tree,second_tree);
printf("the new tree is as following!\n");
print_newtree(new_tree,1);
return 0;
}
试试其它关键字
　两棵二叉树　
同语言下
可能有用的
n.comoon贡献的其它代码(1)
.合并两棵二叉树