精华内容
下载资源
问答
  • 根据这个我们可以在频繁序列集中找到最大频繁序列,可能找到很多条,这样我们把找到的频繁最高频繁序列标识出来,作为推荐学习路径,其中还没学到标成蓝色。关于推荐学习节点,在推荐学习路径下两个节点...

    今天大概设计了一下知识图谱的展示方式,基本就是上图的样子。按说这应该是一整张图的一部分,根据用户的最近学习来定位,并且把最近学习的课程(关键字?标签?这不重要)节点标红,这之间的序列路径标红。根据这个我们可以在频繁序列集中找到最大频繁序列,可能找到很多条,这样我们把找到的频繁度最高的频繁序列标识出来,作为推荐学习路径,其中还没学到的标成蓝色。关于推荐学习节点,在推荐的学习路径上的下两个节点作为推荐学习节点,当然也要考虑不在推荐路径上的节点,我的想法是在找到的所有父频繁序列上,推荐频繁度高于某阈值的路径的下一节点。另外可视化上,把频繁度高的路径加粗,来表现一定的重要程度。

    以上图为例,根据找到的全部的最大频繁序列叠加,可能会生成类似这样的有向图,其中粗细代表了叠加次数,越粗代表叠加的次数越多。图中Java,高等数学,数据结构这三个节点是最近学习过的节点,构成了两个路径。Java-》数据结构这个路径,属于“Java-》数据结构-》数据库-》计算机网络”这个频繁序列,高等数学-》数据结构也属于“Java-》数据结构-》数据库-》计算机网络”这个频繁序列,那么这个频繁序列就作为最推荐的学习路径,接下来的两个节点,数据库和计算机网络就是推荐节点了。数据结构也属于“数据结构-》智能软件”,高等数学也属于“高等数学-》线性代数”,那么智能软件和线性代数也属于推荐候选集。但是后一个频繁序列更为频繁,因此推荐线性代数。这样既解决了主干路径的问题,也没有遗漏重要的旁支,目前看来可能是一个比较好的思路,等实现出来再看效果调整是否需要多推荐几个旁支。

    另外今天我把这个图上线到了项目中作为demo,因为项目时间来不太及了,可能就要先这么展示着了。




    话说把这个图放上去还费了一点事,rails的图片统一放在assets/images下,通过路由来找,一开始不知道,怎么也设不好路径。

    展开全文
  • 节点:A B C D E F G H根节点:A父节点:见图子节点:见图叶子节点 (没有子节点的节点):H E F G节点的权:即为节点的路径(从root节点找到节点的路线):层:见图子树:见图树的高度(最大层数):本图为5层森林 :...

    目录

    1 树的介绍

    1.1 二叉树的概念

    2 二叉树的前序、中序、后序遍历

    2.1 前序遍历

    2.1.1 非递归写法

    2.1.2 递归写法

    2.2 中序遍历

    2.2.1 非递归写法

    2.2.2 递归写法

    2.3 后序遍历

    2.3.1 非递归写法

    2.3.2 递归写法

    3 二叉树的前序、中序、后序查找

    4 二叉树删除节点


    1 树的介绍

    树的常用术语(结合示意图理解):
    节点:A B C D E F G H
    根节点:A
    父节点:见图
    子节点:见图
    叶子节点 (没有子节点的节点):H E F G
    节点的权:即为节点的值
    路径(从root节点找到该节点的路线):
    层:见图
    子树:见图
    树的高度(最大层数):本图为5层
    森林 :多颗子树构成森林。

    1.1 二叉树的概念

    二叉树定义:树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。
    二叉树的子节点分为左节点和右节点。

    满二叉树定义:如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则称为满二叉树。
    完全二叉树定义:如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,则称为完全二叉树。

    2 二叉树的前序、中序、后序遍历

    前序遍历: 先输出父节点,再遍历左子树和右子树
    中序遍历: 先遍历左子树,再输出父节点,再遍历右子树
    后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点


    小结: 看输出父节点的顺序,就确定是前序,中序还是后序

    分析二叉树的前序,中序,后序的遍历步骤:
    1.创建一颗二叉树
    2.前序遍历
        2.1先输出当前节点(初始的时候是root节点)
        2.2如果左子节点不为空,则递归继续前序遍历
        2.3如果右子节点不为空,则递归继续前序遍历
    3.中序遍历
        3.1如果当前节点的左子节点不为空,则递归中序遍历,
        3.2 输出当前节点
        3.3如果当前节点的右子节点不为空,则递归中序遍历
    4.后序遍历
        4.1如果当前节点的左子节点不为空,则递归后序遍历,
        4.2如果当前节点的右子节点不为空,则递归后序遍历
        4.3输出当前节点

    利用下面的图展示二叉树的前序中序后序遍历的代码。

    代码实现:

    public class BinaryTreeDemo {
    
    	public static void main(String[] args) {
    		//先需要创建一颗二叉树
    		BinaryTree binaryTree = new BinaryTree();
    		//创建需要的结点
    		HeroNode root = new HeroNode(1, "宋江");
    		HeroNode node2 = new HeroNode(2, "吴用");
    		HeroNode node3 = new HeroNode(3, "卢俊义");
    		HeroNode node4 = new HeroNode(4, "林冲");
    		HeroNode node5 = new HeroNode(5, "关胜");
    		
    		//说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		node3.setLeft(node5);
    		binaryTree.setRoot(root);
    		
    		//测试
    		System.out.println("前序遍历"); // 1,2,3,5,4
    		binaryTree.preOrder();
    		
    		//测试 
    		System.out.println("中序遍历");
    		binaryTree.infixOrder(); // 2,1,5,3,4
    		
    		System.out.println("后序遍历");
    		binaryTree.postOrder(); // 2,5,4,3,1
    
    	}
    
    }
    
    //定义BinaryTree 二叉树
    class BinaryTree {
    	private HeroNode root;
    
    	public void setRoot(HeroNode root) {
    		this.root = root;
    	}
    
    	//前序遍历
    	public void preOrder() {
    		if(this.root != null) {
    			this.root.preOrder();
    		}else {
    			System.out.println("二叉树为空,无法遍历");
    		}
    	}
    	
    	//中序遍历
    	public void infixOrder() {
    		if(this.root != null) {
    			this.root.infixOrder();
    		}else {
    			System.out.println("二叉树为空,无法遍历");
    		}
    	}
    	//后序遍历
    	public void postOrder() {
    		if(this.root != null) {
    			this.root.postOrder();
    		}else {
    			System.out.println("二叉树为空,无法遍历");
    		}
    	}
    }
    
    //先创建HeroNode 结点
    class HeroNode {
    	private int no;
    	private String name;
    	private HeroNode left; //默认null
    	private HeroNode right; //默认null
    	public HeroNode(int no, String name) {
    		this.no = no;
    		this.name = name;
    	}
    	public int getNo() {
    		return no;
    	}
    	public void setNo(int no) {
    		this.no = no;
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public HeroNode getLeft() {
    		return left;
    	}
    	public void setLeft(HeroNode left) {
    		this.left = left;
    	}
    	public HeroNode getRight() {
    		return right;
    	}
    	public void setRight(HeroNode right) {
    		this.right = right;
    	}
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + "]";
    	}
    		
    	//编写前序遍历的方法
    	public void preOrder() {
    		System.out.println(this); //先输出父结点
    		//递归向左子树前序遍历
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		//递归向右子树前序遍历
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    	//中序遍历
    	public void infixOrder() {
    		
    		//递归向左子树中序遍历
    		if(this.left != null) {
    			this.left.infixOrder();
    		}
    		//输出父结点
    		System.out.println(this);
    		//递归向右子树中序遍历
    		if(this.right != null) {
    			this.right.infixOrder();
    		}
    	}
    	//后序遍历
    	public void postOrder() {
    		if(this.left != null) {
    			this.left.postOrder();
    		}
    		if(this.right != null) {
    			this.right.postOrder();
    		}
    		System.out.println(this);
    	}	
    }

    2.1 前序遍历

    2.1.1 非递归写法

    代码实现:

    public static void preOrder(TreeNode tree) {
         if (tree == null)
             return;
         Stack<TreeNode> q1 = new Stack<>();
         q1.push(tree);//压栈
         while (!q1.empty()) {
             TreeNode t1 = q1.pop();//出栈
             System.out.println(t1.val);
             if (t1.right != null) {
                q1.push(t1.right);
            }
            if (t1.left != null) {
                q1.push(t1.left);
            }
        }
    }

    2.1.2 递归写法

    代码实现:

    public static void preOrder(TreeNode tree) {
        if (tree == null)
            return;
        System.out.printf(tree.val + "");
        preOrder(tree.left);
        preOrder(tree.right);
    }

    2.2 中序遍历

    2.2.1 非递归写法

    代码实现:

    public static void inOrderTraversal(TreeNode tree) {
        Stack<TreeNode> stack = new Stack<>();
        while (tree != null || !stack.isEmpty()) {
            while (tree != null) {
                stack.push(tree);
                tree = tree.left;
            }
            if (!stack.isEmpty()) {
                tree = stack.pop();
                System.out.println(tree.val);
                tree = tree.right;
            }
        }
    }

    2.2.2 递归写法

    代码实现:

    public static void inOrderTraversal(TreeNode node) {
        if (node == null)
            return;
        inOrderTraversal(node.left);
        System.out.println(node.val);
        inOrderTraversal(node.right);
    }

    2.3 后序遍历

    2.3.1 非递归写法

    代码实现:

    public static void postOrder(TreeNode tree) {
         if (tree == null)
             return;
         Stack<TreeNode> s1 = new Stack<>();
         Stack<TreeNode> s2 = new Stack<>();
         s1.push(tree);
         while (!s1.isEmpty()) {
             tree = s1.pop();
             s2.push(tree);
            if (tree.left != null) {
                s1.push(tree.left);
            }
            if (tree.right != null) {
                s1.push(tree.right);
            }
        }
        while (!s2.isEmpty()) {
            System.out.print(s2.pop().val + " ");
        }
    }

    public static void postOrder(TreeNode tree) {
         if (tree == null)
             return;
         Stack<TreeNode> stack = new Stack<>();
         stack.push(tree);
         TreeNode c;
         while (!stack.isEmpty()) {
             c = stack.peek();
             if (c.left != null && tree != c.left && tree != c.right) {
                stack.push(c.left);
            } else if (c.right != null && tree != c.right) {
                stack.push(c.right);
            } else {
                System.out.print(stack.pop().val + " ");
                tree = c;
            }
        }
    }
    

    2.3.2 递归写法

    代码实现:

    public static void postOrder(TreeNode tree) {
        if (tree == null)
            return;
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.println(tree.val);
    }

    3 二叉树的前序、中序、后序查找

    使用前序,中序,后序的方式来查询指定的节点
    前序查找思路:

    1. 先判断当前节点是否等于要查找的
    2. 如果是相等,则返回当前节点
    3. 如果不等,则判断当前节点的左子节点是否为空,如果不为空,则递归前序查找
    4. 如果左递归前序查找,找到节点,则返回,否继续判断,当前的节点的右子节点是否为空,如果不空,则继续向右递归前序查找,找到就返回,否则返回null

    中序查找思路:

    1. 判断当前节点的左子节点是否为空,如果不为空,则递归中序查找
    2. 如果找到,则返回,如果没有找到,就和当前节点比较,如果是则返回当前节点,否则继续进行右递归的中序查找
    3. 如果右递归中序查找,找到就返回,否则返回null

    后序查找思路:

    1. 判断当前节点的左子节点是否为空,如果不为空,则递归后序查找
    2. 如果找到,就返回,如果没有找到,就判断当前节点的右子节点是否为空,如果不为空,则右递归进行后序查找,如果找到,就返回
    3. 如果找不到就和当前结点进行比较,如果是则返回,否则返回null

    代码实现:

    public class BinaryTreeDemo {
    
    	public static void main(String[] args) {
    		//先需要创建一颗二叉树
    		BinaryTree binaryTree = new BinaryTree();
    		//创建需要的结点
    		HeroNode root = new HeroNode(1, "宋江");
    		HeroNode node2 = new HeroNode(2, "吴用");
    		HeroNode node3 = new HeroNode(3, "卢俊义");
    		HeroNode node4 = new HeroNode(4, "林冲");
    		HeroNode node5 = new HeroNode(5, "关胜");
    		
    		//说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		node3.setLeft(node5);
    		binaryTree.setRoot(root);		
    		//前序遍历查找
    		System.out.println("前序遍历方式~~~");
    		HeroNode resNode = binaryTree.preOrderSearch(5);
    		if (resNode != null) {
    			System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    		} else {
    			System.out.printf("没有找到 no = %d 的英雄", 5);
    		}
    		
    		//中序遍历查找
    		System.out.println("中序遍历方式~~~");
    		HeroNode resNode = binaryTree.infixOrderSearch(5);
    		if (resNode != null) {
    			System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    		} else {
    			System.out.printf("没有找到 no = %d 的英雄", 5);
    		}
    		
    		//后序遍历查找
    		System.out.println("后序遍历方式~~~");
    		HeroNode resNode = binaryTree.postOrderSearch(5);
    		if (resNode != null) {
    			System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
    		} else {
    			System.out.printf("没有找到 no = %d 的英雄", 5);
    		}
    		
    	}
    
    }
    
    //定义BinaryTree 二叉树
    class BinaryTree {
    	private HeroNode root;
    
    	public void setRoot(HeroNode root) {
    		this.root = root;
    	}
    	//前序查找
    	public HeroNode preOrderSearch(int no) {
    		if(root != null) {
    			return root.preOrderSearch(no);
    		} else {
    			return null;
    		}
    	}
    	//中序查找
    	public HeroNode infixOrderSearch(int no) {
    		if(root != null) {
    			return root.infixOrderSearch(no);
    		}else {
    			return null;
    		}
    	}
    	//后序查找
    	public HeroNode postOrderSearch(int no) {
    		if(root != null) {
    			return this.root.postOrderSearch(no);
    		}else {
    			return null;
    		}
    	}
    }
    
    //先创建HeroNode 结点
    class HeroNode {
    	private int no;
    	private String name;
    	private HeroNode left; //默认null
    	private HeroNode right; //默认null
    	public HeroNode(int no, String name) {
    		this.no = no;
    		this.name = name;
    	}
    	public int getNo() {
    		return no;
    	}
    	public void setNo(int no) {
    		this.no = no;
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public HeroNode getLeft() {
    		return left;
    	}
    	public void setLeft(HeroNode left) {
    		this.left = left;
    	}
    	public HeroNode getRight() {
    		return right;
    	}
    	public void setRight(HeroNode right) {
    		this.right = right;
    	}
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + "]";
    	}
    	//前序遍历查找
    	/**
    	 * 
    	 * @param no 查找no
    	 * @return 如果找到就返回该Node ,如果没有找到返回 null
    	 */
    	public HeroNode preOrderSearch(int no) {
    		System.out.println("进入前序查找");
    		//比较当前结点是不是
    		if(this.no == no) {
    			return this;
    		}
    		//1.则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找
    		//2.如果左递归前序查找,找到结点,则返回
    		HeroNode resNode = null;
    		if(this.left != null) {
    			resNode = this.left.preOrderSearch(no);
    		}
    		if(resNode != null) {//说明我们左子树找到
    			return resNode;
    		}
    		//1.左递归前序查找,找到结点,则返回,否继续判断,
    		//2.当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找
    		if(this.right != null) {
    			resNode = this.right.preOrderSearch(no);
    		}
    		return resNode;
    	}
    	
    	//中序遍历查找
    	public HeroNode infixOrderSearch(int no) {
    		//判断当前结点的左子节点是否为空,如果不为空,则递归中序查找
    		HeroNode resNode = null;
    		if(this.left != null) {
    			resNode = this.left.infixOrderSearch(no);
    		}
    		if(resNode != null) {
    			return resNode;
    		}
    		System.out.println("进入中序查找");
    		//如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点
    		if(this.no == no) {
    			return this;
    		}
    		//否则继续进行右递归的中序查找
    		if(this.right != null) {
    			resNode = this.right.infixOrderSearch(no);
    		}
    		return resNode;
    		
    	}
    	
    	//后序遍历查找
    	public HeroNode postOrderSearch(int no) {
    		
    		//判断当前结点的左子节点是否为空,如果不为空,则递归后序查找
    		HeroNode resNode = null;
    		if(this.left != null) {
    			resNode = this.left.postOrderSearch(no);
    		}
    		if(resNode != null) {//说明在左子树找到
    			return resNode;
    		}
    		
    		//如果左子树没有找到,则向右子树递归进行后序遍历查找
    		if(this.right != null) {
    			resNode = this.right.postOrderSearch(no);
    		}
    		if(resNode != null) {
    			return resNode;
    		}
    		System.out.println("进入后序查找");
    		//如果左右子树都没有找到,就比较当前结点是不是
    		if(this.no == no) {
    			return this;
    		}
    		return resNode;
    	}
    	
    }
    

    4 二叉树删除节点

    刷除节点的操作:

    规定(可以规定不同的删除方式):

    1. 如果删除的节点是叶子节点,则删除该节点
    2. 如果删除的节点是非叶子节点,则删除该子树

    思路:

    因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.

    1. 考虑如果树是空树root,如果只有一个root结点,则等价将二叉树置空,否则进行下面的步骤。
    2. 如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left=null;并且就返回(结束递归删除)。
    3. 如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right=null;并且就返回(结束递归删除)。
    4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除。
    5. 如果第4步也没有刷除结点,则应当向右子树进行递归影除。

    代码实现:

    public class BinaryTreeDemo {
    
    	public static void main(String[] args) {
    		//先需要创建一颗二叉树
    		BinaryTree binaryTree = new BinaryTree();
    		//创建需要的结点
    		HeroNode root = new HeroNode(1, "宋江");
    		HeroNode node2 = new HeroNode(2, "吴用");
    		HeroNode node3 = new HeroNode(3, "卢俊义");
    		HeroNode node4 = new HeroNode(4, "林冲");
    		HeroNode node5 = new HeroNode(5, "关胜");
    		
    		//说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
    		root.setLeft(node2);
    		root.setRight(node3);
    		node3.setRight(node4);
    		node3.setLeft(node5);
    		binaryTree.setRoot(root);
    		
    		//测试删除结点		
    		System.out.println("删除前,前序遍历");
    		binaryTree.preOrder(); //  1,2,3,5,4
    		binaryTree.delNode(5);
    		//binaryTree.delNode(3);
    		System.out.println("删除后,前序遍历");
    		binaryTree.preOrder(); // 1,2,3,4
    		
    		
    		
    	}
    
    }
    
    //定义BinaryTree 二叉树
    class BinaryTree {
    	private HeroNode root;
    
    	public void setRoot(HeroNode root) {
    		this.root = root;
    	}
    	
    	//删除结点
    	public void delNode(int no) {
    		if(root != null) {
    			//如果只有一个root结点, 这里立即判断root是不是就是要删除结点
    			if(root.getNo() == no) {
    				root = null;
    			} else {
    				//递归删除
    				root.delNode(no);
    			}
    		}else{
    			System.out.println("空树,不能删除~");
    		}
    	}
    	//前序遍历
    	public void preOrder() {
    		if(this.root != null) {
    			this.root.preOrder();
    		}else {
    			System.out.println("二叉树为空,无法遍历");
    		}
    	}
    }
    
    //先创建HeroNode 结点
    class HeroNode {
    	private int no;
    	private String name;
    	private HeroNode left; //默认null
    	private HeroNode right; //默认null
    	public HeroNode(int no, String name) {
    		this.no = no;
    		this.name = name;
    	}
    	public int getNo() {
    		return no;
    	}
    	public void setNo(int no) {
    		this.no = no;
    	}
    	public String getName() {
    		return name;
    	}
    	public void setName(String name) {
    		this.name = name;
    	}
    	public HeroNode getLeft() {
    		return left;
    	}
    	public void setLeft(HeroNode left) {
    		this.left = left;
    	}
    	public HeroNode getRight() {
    		return right;
    	}
    	public void setRight(HeroNode right) {
    		this.right = right;
    	}
    	@Override
    	public String toString() {
    		return "HeroNode [no=" + no + ", name=" + name + "]";
    	}
    	
    	//递归删除结点
    	//1.如果删除的节点是叶子节点,则删除该节点
    	//2.如果删除的节点是非叶子节点,则删除该子树
    	public void delNode(int no) {
    		
    		//思路
    		/*
    		 * 	1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
    			2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
    			3. 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
    			4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
    			5.  如果第4步也没有删除结点,则应当向右子树进行递归删除.
    
    		 */
    		//2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
    		if(this.left != null && this.left.no == no) {
    			this.left = null;
    			return;
    		}
    		//3.如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
    		if(this.right != null && this.right.no == no) {
    			this.right = null;
    			return;
    		}
    		//4.我们就需要向左子树进行递归删除
    		if(this.left != null) {
    			this.left.delNode(no);
    		}
    		//5.则应当向右子树进行递归删除
    		if(this.right != null) {
    			this.right.delNode(no);
    		}
    	}
    	
    	//编写前序遍历的方法
    	public void preOrder() {
    		System.out.println(this); //先输出父结点
    		//递归向左子树前序遍历
    		if(this.left != null) {
    			this.left.preOrder();
    		}
    		//递归向右子树前序遍历
    		if(this.right != null) {
    			this.right.preOrder();
    		}
    	}
    	
    }

     

    展开全文
  • 也就是节点的层次/深度是从根开始数的,离根节点的路径长度为深度,根节点的深度为0。 而结点的高度是从叶子节点开始数的,离叶子节点的最长路径为高度,叶子节点的高度为0。 树的高度和深度相等,等于所有节点中...

    树的深度和高度区别【数据结构】

    关于树的深度和高度我一直容易混淆,故写这篇博客记录。

    先来看我从PPT里找到的答案

    也就是节点的层次/深度是从根开始数的,离根节点的路径长度为深度,根节点的深度为0。
    而结点的高度是从叶子节点开始数的,离叶子节点的最长路径为高度,叶子节点的高度为0。
    树的高度和深度相等,等于所有节点中最大的深度。

    展开全文
  • 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明: 叶子节点是指没有子节点的节点。 示例: 给定二叉树 [3,9,20,null,null,15,7], 返回它的最大深度 3 。 解题思路:如果root为空,则返回0。采用...

    给定一个二叉树,找出其最大深度。

    二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

    说明: 叶子节点是指没有子节点的节点。

    示例:
    给定二叉树 [3,9,20,null,null,15,7],
    在这里插入图片描述
    返回它的最大深度 3 。

    解题思路:如果root为空,则返回0。采用递归的思想,找到root左子树的最大高度,root右子树的最大高度,比较。若左子树的最大高度大于右子树的最大高度,则树的最大高度是左子树的最大高度+1(根节点),否则为右子树的最大高度+1.

    Java:

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     *     int val;
     *     TreeNode left;
     *     TreeNode right;
     *     TreeNode(int x) { val = x; }
     * }
     */
    class Solution {
        public int maxDepth(TreeNode root) {
            int depth = 0;
            if(root == null) return depth;
            
            int leftDepth = maxDepth(root.left);
            int rightDepth = maxDepth(root.right);
            
            if(leftDepth >= rightDepth)
                return leftDepth + 1;
            else
                return rightDepth + 1;
            
        }
    }
    
    展开全文
  • 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。 说明:叶子节点是指没有子节点的节点。 代码: 思路分析: 1、其实就是需要找到左子树的高度leftHeight 和 右子树的高度rightHeight ,然后取两个...
  • 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 示例 例如,给定一个3叉树: 我们应返回其最大深度,3。 说明: 树的深度不会超过1000。 树的节点总不会超过5000。 思路 递归求高度。 ...
  • 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 例如,给定一个 3叉树 : 方法一:递归方法 时间复杂度:每个节点遍历一次,所以时间复杂度为O(N),其中N为节点数 空间复杂度:最坏情况下,树完全非...
  • 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。 方法一:深度优先遍历DFS: 复杂度分析 时间复杂度:每个节点遍历一次,所以时间复杂度是 O(N),其中 N 为节点数。 空间复杂度:最坏情况下, 树完全非...
  • 路径:从 root 节点找到节点的路线。 层 子树 树的高度:最大层数。 森林:多颗子树构成森林。 三 二叉树的概念 1 树有很多种,二叉树的每个节点最多只能有两个子节点。 2 二叉树的子节点分为左节点和右节点...
  • 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 代码: 思路分析: 1、想法和求二叉树的最大深度一样。即找到左子树高度leftHeight 和 右子树高度...
  • 其中将调度方案转换为以最少的服务器操作数找到对等方之间的最佳供应商-消费者关系分配,然后提出两种基于最大流量的流数据调度算法:结合对等体的上载容量以及对等体之间的路径容量。 作者证明所提出的调度算法的...
  • 你是否已经厌倦了,那只能找到孩子却不能反向寻找双亲结点,那遍历起来想要砸键盘的、...首先就是找到从根节点到任意节点的路径方便了很多; 另外是在非递归遍历的时候,之前的二叉树结构想要回溯就只能借助栈,而现在
  • 路径(从root节点找到节点的路线) 层 子树 树的高度(最大层数) 森林 :多颗子树构成森林 1.2 二叉树的概念 每个节点最多只能有两个子节点的一种形式称为二叉树 二叉树的子节点分为左节点和右节点 3. 满二叉树:...
  • 路径(从root节点找到节点的路线) 树的高度(最大层数) 森林 :多颗子树构成森林 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点分为左节点和右节点。 如果该二叉树的所有叶子...
  • 路径(从root节点找到节点的路线) A到H的路径就是 ABDH 层:一共有4层 子树:DH是A或者B的子树 树的高度(最大层数) 二叉树的概念及知识点 二叉树: 每个节点最多只能有两个子节点的一种形式称为二叉树。 如果该...
  • 7) 路径(从root节点找到节点的路线) 8) 层 9) 子树 10) 树的高度(最大层数) 11) 森林 :多颗子树构成森林 二、二叉树的概念 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点...
  • 树概念二叉树的遍历、查找...路径:从根节点开始找到节点的路线 层:根节点为第一层,以此类推 子树:以子节点为根节点的树是相对于父节点的字树 树的高度:最大层数 森林:多颗子树共同组成 二叉树:每个节点最多有两个子节
  • 什么是树结构

    2021-03-26 15:31:55
    路径(从root节点找到节点的路线) 层(树的层级) 子树(拥有子节点的子节点) 树的高度(最大层数) 森林:多颗子数构成森林 (去掉根节点就会形成森林) 关于树让我们先了解一下数组和链表结构 数组:数组结构...
  • Java基础:41 树结构

    2020-07-20 22:56:43
    路径(从root节点找到节点的路线) 层 子树 树的高度(最大层数) 森林 :多颗子树构成森林 2、二叉树的概念 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 二叉树的子节点分为左节点和右节点。...
  • 二叉树

    2020-11-21 17:45:01
    路径(从 root 节点找到节点的路线) 层 子树 树的高度(最大层数) 森林 :多颗子树构成森林 二.满二叉树与完全二叉树 如果该二叉树的所有叶子节点都在最后一层, 并且结点总数= 2^n -1, n 为层数, 则我们称为满...
  • 题目大意:给你一棵树,让你分配边权,使树的直径最小。...叶子节点的度为1,所以找到度为1的所有的点即可。用数组记录每个节点的度,每加入一个边,两点的度分别加一。 #include&lt;bits/stdc++.h&gt...
  • 7)路径(从root节点找到节点的路线) 8)层 9)子树 10)树的高度(最大层数) 11)森林 :多颗子树构成森林 二叉树的概念 1)树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。 2)二叉树的子节点...
  • 路径:从根节点找到节点的一条路。 树的高度:也就是最大层数。 二叉树概念:每个节点最多只能有两个子节点称为二叉树。 二叉树的节点分为左子节点和右子节点。 三种遍历方式 前序遍历:先输出父节点,然后遍历左...
  • 路径(从root节点找到节点的路线) 层 子树 树的高度(最大层数) 森林 :多颗子树构成森林 树存储方式优势 能提高数据存储,读取的效率, 比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同
  • 7) 路径(从 root 节点找到节点的路线) 8) 层 9) 子树 10) 树的高度(最大层数) 11) 森林 :多颗子树构成森林 二、二叉树 2.1、二叉树简述 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉

空空如也

空空如也

1 2 3 4
收藏数 65
精华内容 26
关键字:

找到路径节点的度最大的路径