Microsoft : 二叉树子结构

1                                  2
     2         3                         4     5
   4   5     6   7
8          4       9               

右边的二叉树是左边的子结构，实现判断函数
bool subStructure(TREE_NODE* pRoot1, TREE_NODE* pRoot2)

消灭零回复！
感觉需要再定义个函数，判断严格以参数中两个node为根的子树开始往下是否能匹配

丢一个我写的

1. 
   
2. struct TREE_NODE
   
3. {
   
4.         int nVal;
   
5.         TREE_NODE* pLft;
   
6.         TREE_NODE* pRgt;
   
7. 
   
8.         TREE_NODE(int n) : nVal(n)
   
9.         {
   
10.                 pLft = NULL;
    
11.                 pRgt = NULL;
    
12.         }
    
13. };
    
14. 
    
15. bool IsSubStruct(TREE_NODE* p1, TREE_NODE* p2)
    
16. {
    
17.         if (NULL == p1 && NULL != p2) return false;
    
18.         if (NULL == p2) return true;
    
19. 
    
20.         if (p1->nVal != p2->nVal) return false;
    
21. 
    
22.         return IsSubStruct(p1->pLft, p2->pLft) && IsSubStruct(p1->pRgt, p2->pRgt);
    
23. }
    
24. 
    
25. bool JudgeSubTree(TREE_NODE* pLarge, TREE_NODE* pSmall)
    
26. {
    
27.         return IsSubStruct(pLarge, pSmall) || IsSubStruct(pLarge->pLft, pSmall)
    
28.                 || IsSubStruct(pLarge->pRgt, pSmall);
    
29. }
    
30. 
    

复制代码

回复 3# wwwyhx
怎么感觉有点乱了，子结构不是不要求根节点一定在当前位置，也可以在内部的吗。。
要判断子结构，如果根相等就该判断两个孩子是否能匹配上，还得往两边递归尝试，不等的话直接往两边递归。判断能否匹配就先判断根，然后匹配两边

回复  wwwyhx
怎么感觉有点乱了，子结构不是不要求根节点一定在当前位置，也可以在内部的吗。。
要判断子结构，如果根相等就该判断两个孩子是否能匹配上，还得往两边递归尝试，不等的话直接往两边递归。判断能否匹配就先判断根，然后匹配两边
darksteel 发表于 2011-5-12 13:43

没错啊，这个代码就是实现你说的逻辑啊？