原文链接：http://www.cnblogs.com/wn19910213/p/3725525.html

题目：输入两颗二叉树A和B，判断B是不是A的子结构。

分析：需要先找到data一样的root节点，然后遍历左右孩子，看是否和B节点完全相等。

/*
剑指offer面试题18
树是考察数据结构内功的不二之选
一般代码简洁的话就需要用递归。
而且由于树运用的指针比较多，一定要检查安全性
*/
#include <iostream>

using namespace std;

struct BinaryTree{
    int data;
    BinaryTree* lchild;
    BinaryTree* rchild;
};

bool TreeHaveIt(BinaryTree* parents,BinaryTree* children){
    //鲁棒性
    if(children == NULL){
        return true;
    }
    if(parents == NULL){
        return false;
    }
    if(children->data != parents->data){
        return false;
    }

    return TreeHaveIt(parents->lchild,children->lchild) && TreeHaveIt(parents->rchild,children->rchild);
}

bool HasSubTree(BinaryTree* parents,BinaryTree* children){
    bool b = false;
    //边界检测
    if(parents != NULL && children != NULL){
        if(parents->data == children->data){
            b = TreeHaveIt(parents,children);
        }
        if(!b){
            b = HasSubTree(parents->lchild,children);
        }
        if(!b){
            b = HasSubTree(parents->rchild,children);
        }
    }
    return b;
}


BinaryTree* Create(int n){
    if(n == 1){
        BinaryTree* root = new BinaryTree;
        root->data = 8;
        BinaryTree* lchild = new BinaryTree;
        lchild->data = 8;
        BinaryTree* rchild = new BinaryTree;
        rchild->data = 7;
        root->lchild = lchild;
        root->rchild = rchild;

        BinaryTree* lchild1 = new BinaryTree;
        lchild1->data = 9;
        BinaryTree* rchild1 = new BinaryTree;
        rchild1->data = 2;
        lchild->lchild = lchild1;
        lchild->rchild = rchild1;

        BinaryTree* lchild2 = new BinaryTree;
        lchild2->data = 4;
        BinaryTree* rchild2 = new BinaryTree;
        rchild2->data = 7;
        rchild1->lchild = lchild2;
        rchild1->rchild = rchild2;
        return root;
    }
    else{
        BinaryTree* root = new BinaryTree;
        root->data = 8;
        BinaryTree* lchild = new BinaryTree;
        lchild->data = 9;
        BinaryTree* rchild = new BinaryTree;
        rchild->data = 2;
        root->lchild = lchild;
        root->rchild = rchild;
    }
}

void print(BinaryTree* root){
    if(root != NULL){
        cout << root->data << " ";
        print(root->lchild);
        print(root->rchild);
    }
}

int main()
{
    BinaryTree* parents = Create(1);
    BinaryTree* children = Create(2);

    //print(parents);

    bool result = HasSubTree(parents,children);

    cout << result << endl;

    return 0;
}

 

转载于:https://www.cnblogs.com/wn19910213/p/3725525.html