判断一个节点是否在一棵二叉树中&判断一颗二叉树是是否是另一颗树的子树

判断一个节点是否在一棵二叉树中

//给一个数找是否在二叉树中，找到返回所在节点 Node<T>* find(const T& data) { return _find(_root, data); } //判断一个节点是否在一棵二叉树中 bool IsNodeintree(const Node<T>* node) { return _IsNodeintree(_root,node); } Node<T>* _find(Node<T>* root, const T& data) { if (root == NULL) return NULL; if (root->_val == data) return root; Node<T>* ret=NULL; if (ret =_find(root->_left, data)) return ret; return _find(root->_right,data); } bool _IsNodeintree(Node<T>* root, const Node<T>* node) { if (root == NULL || node == NULL) return false; if (root == node) return true; if (_IsNodeintree(root->_left, node) || _IsNodeintree(root->_right, node)) return true; return false; }

判断一颗二叉树是是否是另一颗树的子树

template<class T> bool HasSubTree(Node<T>* root1, Node<T>* root2) { bool ret = false; if (root1 == NULL || root2 == NULL) return false; //找到相同的根节点，判断其子树是否相同 if (root1->_val == root2->_val) { ret = IfTree1hasTree2(root1, root2); } if (!ret) ret = HasSubTree(root1->_left, root2); if (!ret) ret = HasSubTree(root1->_right, root2); return ret; } template<class T> bool IfTree1hasTree2(Node<T>* root1, Node<T>* root2) { //第一棵树中结点遍历完第二棵树还有及结点，肯定不是 if (root1 == NULL) return false; //第二棵树遍历完且与第一棵树的结点相同 if (root2 == NULL) return true; if (root1->_val != root2->_val) return false; return IfTree1hasTree2(root1->_left,root2->_left) && IfTree1hasTree2(root1->_right,root2->_right); }