数据结构_二叉树各种算法实现

temp->right=copy(p->right);
return temp;
}
/*判断两棵二叉树是否相似的递归算法*/
int Similar(BTree *t1, BTree *t2)
{
if(t1==NULL&&t2==NULL) return 1;
if(t1&&t2)
{
if(Similar(t1->left,t2->left)&&Similar(t1->right,t2->right))
else return leafcount(root->left)+leafcount(root->right);
}
}
int CountNode (BTree *t) //节点总数
{
int num;
if (t == NULL)
num = 0;
else
num = 1 + CountNode (t->left) + CountNode (t->right);
}
else
{
depth1=Height(bt->left);
depth2=Height(bt->right);
if (depth1>depth2)
{
return (depth1+1);
}
else
{
return (depth2+1);
}
}
}
int Width(BTree *T)//二叉树宽度
{
int static n[10];//向量存放各层结点数
{
return 1;
}
}
return 0;
}
int CompTree(BTree *tree1,BTree *tree2)//二叉树是否相等
{
if (!tree1 && !tree2)
{
return 1;
}
else if (tree1->data == tree2->data &&
CompTree(tree1->left, tree2->left) &&
int static i=1;
int static max=0;//最大宽度
if(T)
{
if(i==1) //若是访问根结点
{
n[i]++; //第1层加1
i++; //到第2层
if(T->left)//若有左孩子则该层加1
n[i]++;
if(T->right)//若有右孩子则该层加1
n[i]++;
}
return max;
}
//层次遍历二叉树,用队列来实现
void TraversalOfLevel(BTree* bt)
{
Queue q;
q.front=q.rear=0;
if (bt!=NULL)
{
printf("%c ",bt->data);
}
q.b[q.front]=bt;
q.rear=q.rear+1;
while (q.front<q.rear)
{
bt=q.b[q.front];
q.front=q.front+1;
iຫໍສະໝຸດ Baidu (bt->left!=NULL)
{
printf("%c ",bt->left->data);
q.b[q.rear]=bt->left;
q.rear=q.rear+1;
}
if (bt->right!=NULL)
printf("此两二叉树相等\n");
else printf("此两二叉树不相等\n");
return 0;
}
运行截图：
{
printf("%c ",bt->right->data);
q.b[q.rear]=bt->right;
q.rear=q.rear+1;
}
}
}
int leafcount(BTree* root)//统计叶子结点个数
{
if(root==NULL) return 0 ;
else
{
if(!root->right&&!root->left) return 1;
return (num);
}
BTree *copy(BTree *p)//复制一棵二叉树
{
BTree *temp;
if(p==NULL)
return NULL;
temp=(BTree *)malloc(sizeof(BTree));
temp->data=p->data;
temp->left=copy(p->left);
int Hgt=Height(btr);
printf("%d \n",Hgt);
printf("二叉树的宽度：\n");
int Wdh=Width(btr);
printf("%d \n",Wdh);
printf("层次遍历二叉树:\n");
TraversalOfLevel(btr);
printf("\n");
二叉树各种算法实现
#include <stdio.h>
#include <malloc.h>
#define MAXSIZE 20
//二叉树结点的结构体表示形式
typedef struct node
{
char data;
struct node* left,*right;
}BTree;
//栈的结构体表示形式
BTree* Create()
{
char ch;
scanf("%c",&ch);
getchar();
if (ch=='#')
{
return NULL;
}
else
{
BTree* btree=(BTree*)malloc(sizeof(BTree));
if (btree==NULL)
{
return NULL;
printf("结点总数为：\n");
int countn=CountNode(btr);
printf("%d \n",countn);
printf("度为1的结点个数为：%d\n",countn-2*leafgs+1);
printf("度为2的结点个数为：%d\n",leafgs-1);
printf("二叉树的高度：\n");
typedef struct stackelem
{
BTree* a[MAXSIZE];
int top;
}Stack;
//队列的结构体的表示形式
typedef struct queueelem
{
BTree* b[MAXSIZE];
int front,rear;
}Queue;
//创建二叉树，利用递归的方法
}
btree->data=ch;
btree->left=Create();
btree->right=Create();
return btree;
}
}
//求二叉树的高度，递归实现
int Height(BTree* bt)
{
int depth1,depth2;
if (NULL==bt)
{
return 0;
}
else
{ //访问子树结点
i++; //下一层结点数
if(T->left)
n[i]++;
if(T->right)
n[i]++;
}
if(max<n[i])max=n[i];//取出最大值
Width(T->left);//遍历左子树
i--; //往上退一层
Width(T->right);//遍历右子树
CompTree(tree1->right, tree2->right))
{
return 1;
}
else
{
return 0;
}
}
int main()
{
BTree* btr=Create();
printf("叶子结点个数为：\n");
int leafgs=leafcount(btr);
printf("%d \n",leafgs);
printf("复制的二叉树为:\n");
BTree * cp=copy(btr);
TraversalOfLevel(cp);
printf("\n");
if(Similar(btr,cp)==1)
printf("此两二叉树相似\n");
else printf("此两二叉树不相似\n");
if(CompTree(btr,cp)==1)