二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点,并且二叉树的子树有左右之分,其次序不能任意颠倒。
1.每个节点最多有两个子节点,分别称作左子节点和右子节点。 2.每个节点的左子节点的值比它小,右子节点的值比它大。 3.每个节点的左子树每个节点的值都比它小,右子树每个节点的值都比它大。
前面两点我理解,但是第三点是怎么做到的? 接下来介绍下二叉树是如何 “生长” 起来的
image.png
如上图所示,当加入一个新节点时,从根节点开始对它进行比较。如果它比根节点小,则放入根节点的左子树,如果比根节点大,则放入根节点的右子树。然后再进行下一级节点的比较,直到遇到最后一级节点,才将新节点加入为该节点的左或右子节点。
以第四幅图的节点 25 为例,它第一次会与根节点 10 比较,结果就是 25 应该放入 10 的右子树,这就排除了它放入左子树的可能,即 25 不可能放到 4 的下面。然后 25 再和节点 33 比较,结果是它比较小,所以应该放入 33 的左子树。因为 33 没有左子节点,那么 25 就直接作为 33 的左子节点。
通过这种生长方式,我们无论何时都能得到满足前面三个要素的二叉树。
满二叉树 在一棵二叉树中,如果所有分支结点都有左子结点和右子结点,并且叶子结点都集中在二叉树的最下层,这样的树叫做满二叉树
完全二叉树 若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶子结点都是依次排列在该层最左边的位置上,则称为完全二叉树
image.png
截屏2021-05-28 14.54.06.png
如图Java创建一个满二叉树
1.新建一个TreeNode类
public class TreeNode { private String value;//节点的权 private TreeNode leftNode;//左子节点 private TreeNode rightNode;//右子节点 public String getValue() { return value; } public void setValue(String value) { this.value = value; } public TreeNode getLeftNode() { return leftNode; } public void setLeftNode(TreeNode leftNode) { this.leftNode = leftNode; } public TreeNode getRightNode() { return rightNode; } public void setRightNode(TreeNode rightNode) { this.rightNode = rightNode; } public TreeNode(String value) { this.value = value; } @Override public String toString() { return "Node [value=" + value + "]"; } }
2.新建一个BinaryTree类 并添加一个insertNode方法
public class BinaryTree { private TreeNode rootNode;//根节点 public TreeNode getRootNode() { return rootNode; } @Override public String toString() { return "BinaryTree [rootNode=" + rootNode + "]"; } /** * 功能描述: 插入结点 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午2:42 */ public void insertNode(TreeNode treeNode) { if (rootNode == null) { rootNode = treeNode; rootNode.setLeftNode(null); rootNode.setRightNode(null); } else { TreeNode currentNode = rootNode; TreeNode parentNode; // 有孩子继续循环,一直循环到最后一个节点 和插入的节点比较 大的放到右节点,小于放到左节点 while (true) { parentNode = currentNode; // 往右放 if (Integer.valueOf(treeNode.getValue()) > Integer.valueOf(currentNode.getValue())) { currentNode = currentNode.getRightNode(); if (currentNode == null) { parentNode.setRightNode(treeNode); return; } } else { // 往左放 currentNode = currentNode.getLeftNode(); if (currentNode == null) { parentNode.setLeftNode(treeNode); return; } } } } } }
public static void testInsertNode() { BinaryTree tree = new BinaryTree(); TreeNode node1 = new TreeNode("6"); TreeNode node2 = new TreeNode("5"); TreeNode node3 = new TreeNode("10"); TreeNode node4 = new TreeNode("4"); TreeNode node5 = new TreeNode("6"); TreeNode node6 = new TreeNode("7"); TreeNode node7 = new TreeNode("11"); tree.insertNode(node1); tree.insertNode(node2); tree.insertNode(node3); tree.insertNode(node4); tree.insertNode(node5); tree.insertNode(node6); tree.insertNode(node7); System.out.println("根节点:" + tree.getRootNode()); System.out.println("根节点的左子节点:" + tree.getRootNode().getLeftNode()); System.out.println("根节点的右子节点:" + tree.getRootNode().getRightNode()); System.out.println("根节点的左子节点的左子节点:" + tree.getRootNode().getLeftNode().getLeftNode()); System.out.println("根节点的左子节点的右子节点:" + tree.getRootNode().getLeftNode().getRightNode()); System.out.println("根节点的右子节点的左子节点:" + tree.getRootNode().getRightNode().getLeftNode()); System.out.println("根节点的右子节点的右子节点:" + tree.getRootNode().getRightNode().getRightNode()); }
根节点:Node [value=6] 根节点的左子节点:Node [value=5] 根节点的右子节点:Node [value=10] 根节点的左子节点的左子节点:Node [value=4] 根节点的左子节点的右子节点:Node [value=6] 根节点的右子节点的左子节点:Node [value=7] 根节点的右子节点的右子节点:Node [value=11]
先序遍历 操作: 如果二叉树为空树,什么也不做;否则: (1)、访问根节点。 (2)、先序遍历左子树。 (3)、先序遍历右子树。
/** * * 功能描述: 先序遍历 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午3:05 */ public void beforeOrder(TreeNode treeNode) { if (treeNode != null) { System.out.print(" " + treeNode.getValue() + " "); beforeOrder(treeNode.getLeftNode()); beforeOrder(treeNode.getRightNode()); } }
结果
先序遍历 6 5 4 6 10 7 11
中序遍历 操作: 如果二叉树为空树,什么也不做;否则: (1)、中序遍历左子树。 (2)、访问根节点。 (3)、中序遍历右子树。
/** * * 功能描述: 中序遍历 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午3:06 */ public void inOrder(TreeNode treeNode) { if (treeNode != null) { inOrder(treeNode.getLeftNode()); System.out.print(" " + treeNode.getValue() + " "); inOrder(treeNode.getRightNode()); } }
结果
中序遍历 4 5 6 6 7 10 11
后序遍历 操作: 如果二叉树为空树,什么也不做;否则: (1)、后序遍历左子树。 (2)、后序遍历右子树。 (3)、访问根节点。
/** * * 功能描述: 后序遍历 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午3:09 */ public void afterOrder(TreeNode treeNode) { if (treeNode != null) { afterOrder(treeNode.getLeftNode()); afterOrder(treeNode.getRightNode()); System.out.print(" " + treeNode.getValue() + " "); } }
结果
后序遍历 4 6 5 7 11 10 6
public static void testOrder() { BinaryTree tree = new BinaryTree(); TreeNode node1 = new TreeNode("6"); TreeNode node2 = new TreeNode("5"); TreeNode node3 = new TreeNode("10"); TreeNode node4 = new TreeNode("4"); TreeNode node5 = new TreeNode("6"); TreeNode node6 = new TreeNode("7"); TreeNode node7 = new TreeNode("11"); tree.insertNode(node1); tree.insertNode(node2); tree.insertNode(node3); tree.insertNode(node4); tree.insertNode(node5); tree.insertNode(node6); tree.insertNode(node7); System.out.println("先序遍历"); tree.beforeOrder(tree.getRootNode()); System.out.println(); System.out.println("中序遍历"); tree.inOrder(tree.getRootNode()); System.out.println(); System.out.println("后序遍历"); tree.afterOrder(tree.getRootNode()); }
先序遍历 6 5 4 6 10 7 11 中序遍历 4 5 6 6 7 10 11 后序遍历 4 6 5 7 11 10 6
/** * * 功能描述: 二叉树深度 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午3:40 */ public int maxBinaryTreeDepth(TreeNode root){ if(root == null) return 0; int left = maxBinaryTreeDepth(root.getLeftNode()); int right = maxBinaryTreeDepth(root.getRightNode()); return (left>right)?(left+1):(right+1); }
/** * * 功能描述: 二叉树中节点的个数 * * @param: * @return: * @auther: Destiny * @date: 2021/5/28 下午3:45 */ public int sumNode(TreeNode root){ if(root == null) return 0; int left = sumNode(root.getLeftNode()); int right = sumNode(root.getRightNode()); return 1+left+right; }
本文是一份对数据分析的生命周期、不断扩展的工具和技术组合,以及如何根据你的...
大数据的出现、云计算技术的日渐成熟和深度学习算法的重大突破,推动着算法时代...
一、前言 在Web项目开发中,经常会遇到一些只能输入固定内容的文本框。例如,只...
在当今这个数字优先的世界中,企业基础设施正在不断发展和变化,因此基础设施和...
直播主题 Tair(Redis)行业场景深度剖析-生活出行的计算与应用 直播时间 5月20日 ...
阿里云智慧校园解决方案让教育教学全场景数据贯通 用人工智能使师生减负增效 促...
【51CTO.com快译】有 统计 表明:目前,全球共有52.2亿人正在使用着移动设备,其...
1. 接口描述 接口请求域名: cvm.tencentcloudapi.com 。 本接口 (AssociateInst...
数字化转型的工作在很大程度上取决于数据分析。但是要做出根本性的改变,组织必...
描述 给你一个金字型塔的数列,第一行一个0,第二行两个1……第六行六个5,现在...