树A包含树B的问题
有两棵树，要求验证树A包含树Bcat tree.c#include <stdio.h>typedef struct TreeNode{ int data; struct TreeNode * lchild; struct TreeNode * rchild;}TNode;//}TNode,*TNode *;// A Tree B Tree// 1 2// /\ / \// 2 3 4 5// / \ \// 4 5 6// \// 6int a[]={1,2,4,0,6,0,0,5,0,0,3,0,0};int b[]={2,4,0,6,0,0,5,0,0};//int b[]={2,4,0,3,0,0,5,0,0};// bu bao han ce shi BTreeint numA=0;int numB=0;int index=0;int count=0;TNode * CreateA(TNode * T){ int ch; ch=a; numA++; if(ch == 0){ T=NULL; }else{ if(!(T=(TNode *)malloc(sizeof(TNode)))) printf("A in malloc error\n"); T->data = ch; T->lchild = CreateA(T->lchild); T->rchild = CreateA(T->rchild); } return T;}TNode * CreateB(TNode * T){ int ch; ch=b; numB++; if(ch == 0){ T=NULL; }else{ if(!(T=(TNode *)malloc(sizeof(TNode)))) printf("B in malloc error\n"); T->data = ch; T->lchild = CreateB(T->lchild); T->rchild = CreateB(T->rchild); } return T;}void xianxu(TNode * T){ if(T!=NULL){ printf("%d\n",T->data); xianxu(T->lchild); xianxu(T->rchild); }}voidbaohan(TNode * A,TNode * B){ if(A!=NULL && B!=NULL){ if(A->data != B->data){ baohan(A->lchild,B); baohan(A->rchild,B); }else{ index++; baohan(A->lchild,B->lchild); baohan(A->rchild,B->rchild); } }}void NodeCount(TNode * T){ if(T!=NULL){ count++; NodeCount(T->lchild); NodeCount(T->rchild); }}int main(void){ TNode * rootA; TNode * rootB; rootA = CreateA(rootA); rootB = CreateB(rootB); printf("Create End \n"); printf("Tree A: \n"); xianxu(rootA); printf("Tree B: \n"); xianxu(rootB); printf("-----------------\n"); baohan(rootA,rootB); NodeCount(rootB); printf("AB same nodes count:%dTreeB,NodesCount :%d\n",index,count); if(index==count) printf("A baohan B\n"); else printf("A bu baohan B\n"); return 0;}
运行结果
Create End Tree A: 124653Tree B: 2435-----------------AB same nodes count:4TreeB,NodesCount :4Abaohan B
页:
[1]