精华内容
下载资源
问答
  • 1、判断一个节点是否在一棵二叉树中。 先判断节点,递归判断左子树,递归判断右子树。2、判断一颗二叉树是否是另一颗树的子树。比如tree2是tree1的子树。  先判断根,根相同再判断左右子树如果所有的都相同,...

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

           先判断根节点,递归判断左子树,递归判断右子树。

    2、判断一颗二叉树是是否是另一颗树的子树。比如tree2是tree1的子树。

    这里写图片描述

           先判断根,根相同再判断左右子树如果所有的都相同,则此树是另一个树的子树。 如果只有根相同,则向下继续找和跟相同的结点。

    代码:

    #include<iostream>
    
    using namespace std;
    
    struct Node
    {
        int _data;
        Node* _leftchild;
        Node* _rightchild;
    
        Node(int x)
            :_data(x)
            , _leftchild(NULL)
            , _rightchild(NULL)
        {}
    };
    
    class BinaryTree
    {
    public:
        BinaryTree(const int a[], int size, int invalide)
        {
            int index = 0;
            _root = _CreateBinaryTree(a, size, index, invalide);
        }
    
        Node* _CreateBinaryTree(const int a[], int size, int &index, int invalide)
        {
            Node* root = NULL;
            if (index < size && a[index] != invalide)
            {
                root = new Node(a[index]);
                root->_leftchild = _CreateBinaryTree(a, size, ++index, invalide);
                root->_rightchild = _CreateBinaryTree(a, size, ++index, invalide);
            }
            return root;
        }
    
        //判断一个节点是否在一棵二叉树中。(注意多测几个节点,看是否都能找到)
        bool IsInTree(Node* node)
        {
            return _IsInTree(_root, node);
        }
    
        bool _IsInTree(Node* root, Node* node)
        {
            if (root == NULL)
                return false;
            if (root == node)
                return true;
            if (_IsInTree(root->_leftchild, node) || _IsInTree(root->_rightchild, node))
                return true;
            return false;
        }
    
        //判断一颗二叉树是是否是另一颗树的子树。比如tree2是tree1的子树。
        bool IsChildTree(Node* pRoot)
        {
            return _IsChildTree(_root, pRoot);
        }
    
        bool __IsChildTree(Node* root, Node* pRoot)
        {
            if (root == NULL)
                return false;
            if (pRoot == NULL)
                return true;
            if (root->_data != pRoot->_data)
                return false;
            return __IsChildTree(root->_leftchild, pRoot) && __IsChildTree(root->_rightchild, pRoot->_rightchild);
        }
    
        bool _IsChildTree(Node* root, Node* pRoot)
        {
            bool ret = false;
            if (root != NULL&&pRoot != NULL)
            {
                if (root->_data == pRoot->_data)
                    ret = __IsChildTree(root, pRoot);
                if (!ret)
                    ret = _IsChildTree(root->_leftchild, pRoot);
                if (!ret)
                    ret = _IsChildTree(root->_rightchild, pRoot);
            }
            return ret;
        }
    
    private:
        Node* _root;
    };
    int main()
    {
        system("pause");
        return 0;
    }
    展开全文
  • 给定一个二叉树和一个值\ sumsum,判断是否有从根节点到叶子节点节点值之和等于\ sumsum的路径, 例如: 给出如下的二叉树,sum=22 返回true,因为存在一条路径5→4→11→2的节点值之和为 22 class Solution ...

    题目描述

    给定一个二叉树和一个值\ sum sum,判断是否有从根节点到叶子节点的节点值之和等于\ sum sum 的路径,
    例如:
    给出如下的二叉树,sum=22 

     返回true,因为存在一条路径 5→4→11→2的节点值之和为 22

    class Solution {
    public:
        /**
         * 
         * @param root TreeNode类 
         * @param sum int整型 
         * @return bool布尔型
         */
        bool hasPathSum(TreeNode* root, int sum) {
            // write code here
            if(root == nullptr) return false;
            else if(root->val == sum && root->left == nullptr && root->right==nullptr){
                return true;
            }
            return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
        }
    };

     

    展开全文
  • 输入两棵二叉树A和B,判断B是不是A的子结构思路: 1、在树A中找到和B根节点值一样的节点R 2、再判断树A中以R节点为根节点的子树是不是包含和树B一样的结构。代码实现//步骤1,找一样的节点 bool HasSubTree...

    树的子结构

    问题分析
    输入两棵二叉树A和B,判断B是不是A的子结构

    这里写图片描述

    思路:
    1、在树A中找到和B根节点值一样的节点R
    2、再判断树A中以R节点为根节点的子树是不是包含和树B一样的结构。

    代码实现

    //步骤1,找一样的节点
    bool HasSubTree(TreeNode* pRoot1, TreeNode * pRoot2)
    {
        bool res = false;
        if (pRoot1 != NULL && pRoot2 != NULL)
        {
            if (pRoot1->val == pRoot2->val)
                res = DoesTree1HaveTree2(pRoot1, pRoot2);
    
            //以该节点为根节点的结构不是子树结构
            if (!res)
                res = HasSubTree(pRoot1->left, pRoot2);
            if (!res)
                res = HasSubTree(pRoot1->right, pRoot2);
        }
        return res;
    }
    //步骤2:在A中找到与B根节点一样的点R,判断是否有一样的结构
    //递归的思路来考虑,如果两个根节点相等的话,则判断他们得左右子树是否相等,
    //直到到达其中一个数的叶节点
    bool DoesTree1HaveTree2(TreeNode* pRoot1, TreeNode * pRoot2)
    {
        if (pRoot2 == NULL)//如果B结构到达叶子节点,说明匹配
            return true;
        if (pRoot1 == NULL)//如果A中到达叶子结点,但是B没有到达叶子节点,说明不匹配
            return false;
        if (pRoot1->val != pRoot2->val)
            return false;
        return DoesTree1HaveTree2(pRoot1->left, pRoot2->left)
            && DoesTree1HaveTree2(pRoot1->right, pRoot2->right);
    }

    变形,判断两个树的结构是否相等

    分析:其实这个问题与上一个问题类似,但是相对容易一些。
    只是判断两个数的结构是否相等,不考虑到树的节点内容。

    bool StructureCmp(Node *pRoot1,Node *pRoot2)
    {
        //两个根节点都为空,返回真
        if(pRoot1 == NULL && pRoot2 == NULL)
            return true;
        if(pRoot1 == NULL || pRoot2 == NULL)
            return false;
        bool left = StructureCmp(pRoot1->left,pRoot2->left);
        bool right = StructureCmp(pRoot2->right,pRoot2->right);
        return (left&&right);
    }

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

    思路:递归的方法,判断根节,然后 找左子树,找右子树

    bool IsInTree(Node* pRoot,Node* find)
    {
        if(pRoot == NULL || find == NULL)
            return false;
        if(pRoot == find)
            return true;
        //不是根节点,找左找右
        if(IsInTree(pRoot->left,find))
            return true;
        return IsInTree(pRoot->right,find);
    }
    展开全文
  • 判断一个结点是否二叉树

    千次阅读 2018-05-11 00:19:12
    要找一个结点判断是否二叉树里面的结点,只需要将二叉树遍历一遍,用每一个节点与该结点进行比较即可。 //查看一个是否二叉树里的数据,是的话返回指针,不是的话返回NULL pBTNode find(pBTNode pRoot,...

    二叉树是否为完全二叉树
    二叉树的基本操作(点击查看)
    要找一个结点判断是否是二叉树里面的结点,只需要将二叉树遍历一遍,用每一个节点与该结点进行比较即可。

    //查看一个是否是二叉树里的数据,是的话返回指针,不是的话返回NULL
    pBTNode find(pBTNode pRoot,BTDataType data)
    {
        pBTNode pNode = NULL;
        if(NULL == pRoot)
            return NULL;
        if(pRoot->_data == data)
            return pRoot;
        if(pNode = find(pRoot->_pLeft,data))
            return pNode;
        return find(pRoot->_pRight,data);
    }
    
    //判断是否是二叉树的结点
    int IsNodeBinTree(pBTNode pRoot,pBTNode pNode)
    {
        if(NULL != find(pRoot,pNode->_data))
        {
            printf("该结点二叉树里面的结点!!!\n");
            return 1;
        }
        else
        {
            printf("该结点不是二叉树里面的结点!!!\n");
            return 0;
        }
    }
    展开全文
  • 思路: 递归:找左找右递归。bool IsNodeInTree(BinaryTreeNode* pRoot,BinaryTreeNode* pNode) { if(pRoot == NULL || pNode ==NULL) return false; if(pRoot == pNode) return true; if
  • 判断一个节点是否在一棵二叉树
  • bool judge_bro(BiTree T,char x,char y) //判断两个节点是不是兄弟节点 { if(T==NULL) return false; //如果一个节点的左右孩子都不为空,且两个孩子一个等于x,一个等于y //则两节点是兄弟节点,返回true ...
  • step2 判断是否为完全二叉树 1、当一个结点 有右节点 但 没有左节点 不是完全二叉树 2、当一个结点 有左节点 但 没有右节点 之后的节点都没有子节点 (是完全二叉树) 之后的节点存在子节点 (不是完全二叉树) ...
  • 关于二叉树的递归遍历就不写了,这里介绍一下非递归方式 二叉树的非递归遍历 二叉树结构如下: public static class Node { public intvalue; public Node left; public Node right; public Node(int ...
  • 判断二叉树是不是二叉树 方法1:我们算出树高,算出树的节点个数,因为它有个等比数列求和! 方法2:如果满足下图要求,就是满二叉树! 我们在每一层出队列的时候,都可以达到满二叉树的这一行应该有的节点个数...
  • 输入一棵二叉树,判断二叉树是否是平衡二叉树。 平衡二叉树: 如果一棵树是空树或者它的任意节点的左右两个子树的高度差的绝对值不超过1,那么这棵树为平衡二叉树。 2.解法一 最简单的想法就是,我们可以求出每个...
  • 判断是否完全二叉树python

    千次阅读 2019-06-25 19:52:15
    #File Name : 是否为完全二叉树.py class Node(object): def __init__(self,val=None): self.val = val self.left = None self.right = None def isCBT(head): if not head: retur...
  • 完全二叉树看起来就是一个“满二叉树右下角缺了一块” 需要引入一个标志位来区分两个阶段 针对一个完全二叉树,进行层序遍历,会出现两种阶段 1)任何一个节点都一定有左子树和右子树。 当遇到某个节点只有左子树...
  • 判断是否为完全二叉树(两种方法)

    千次阅读 多人点赞 2020-11-07 11:59:11
    完全二叉树也就是没有满的满二叉树,它的节点在每一层一定是连续分布的。如果出现哪一层中两个非空节点间隔一个空节点,那一定不是完全二叉树。如下图所示: 假设这棵完全二叉树有K层,因此我们可以总结一下完全...
  • 二叉树的定义 struct Node ...使用dfs判断是否为完全二叉树 void dfs(int root,int index) { if(root==-1) return ; if(index>maxIndex) { maxIndex=index; } dfs(node[root].lchild,index*2); d
  • 下面是一个二叉树,查找某个值是否存在。 代码: public class TestTree { static class Node { public char val; public Node left; public Node right; public Node(char val) { this....
  • 判断一个节点是否在一颗二叉树中:
  • 1完全二叉树 完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 如下就是完全二叉树 1 2 3 4...
  • 平衡二叉树 思路 平衡二叉树 任意结点的左右子树高度之差的绝对值不大于1的树 空树为平衡二叉树 示例 1: 给定二叉树 [3,9,20,null,null,15,7] 3 / \ 9 20 / \ 15 7 返回 true 。 示例 2: 给定二叉树 [1...
  • 已知二叉树节点数求二叉树形态

    千次阅读 2017-12-21 22:21:35
    前言10月底参加百度测试开发面试,三面的时候确实个人能力欠缺,特此记录一道二叉树相关题目,希望自己能够勤能补拙,努力达到自己想要的高度。正文先考虑只有一个节点的情形,设此时的形态有f(1)种,那么很明显f(1)...
  • 判断二叉树是否为完全二叉树 完全二叉树看起来就像是满二叉树右下角缺了一口。 思路: 需要引入一个标志位来区分两个阶段 1.先对该树进行层序遍历,会出现两种阶段 a):任何一个节点都有两颗子树 当遇到一个结点...
  • 判断一颗二叉树是否是完全二叉树

    千次阅读 2019-05-23 22:56:03
    判断一颗二叉树是否是完全二叉树 方法一,采取标记的方法 非完全二叉树的三种情况 思路分析: 通过层序遍历来遍历树中的每一个非空结点 遍历到的每一个结点都分为四种情况 1.既有左孩子也有右孩子 操作:将左...
  • 二叉树-查找指定节点

    2020-12-20 17:05:43
    二叉树-查找指定节点 接上一篇博客 要求: 请编写前序查找,中序查找和后序查找的方法。 并分别使用三种查找方式,查找 heroNO = 5 的节点 代码示例: package com.wxit.tree; /** * @Author wj **/ public ...
  • 1.判断一个节点是否在一颗二叉树中 首先判断节点是不是节点,是根节点的话就返回表示节点在树中,否则递归根节点的左右子树,继续向下寻找bool _IsNode(Node* node,Node* root) { if (root == NULL) return ...
  • 除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树。一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是(2^k) -1 ,则...
  • 牛客链接 1. 题目考点 搜索二叉树定义 搜素二叉树的判定(性质) 二叉树的中序遍历 完全二叉树定义 完全二叉树的判定(性质) ...搜索二叉树的判定:中序遍历搜索二叉树是一个升序序列 public boolean inOrder(TreeNo
  • 判断是否二叉树

    2019-07-04 19:41:11
    利用二叉树的中序遍历的递增性判断 /** * BST树的节点类型 * @param <T> */ class BSTNode <T extends Comparable<T>>{ private T data; // 数据域 private BSTNode<T> left; // 左...
  • 判断一个节点是否在一棵二叉树中 struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } }; 判断一棵树是不是另一颗树的子树。

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 100,636
精华内容 40,254
关键字:

判断节点是否属于二叉树