数据结构与算法|浅入浅出二叉树二叉树|算法|java|数据结构

树的概述树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。形同下图。

文章图片

树有如下基本概念：

根结点
根结点是树的一个组成部分，也叫树根。每一颗树都有且仅有一个根结点。它是同一棵树中除本身外所有结点的祖先，没有父结点。按上图的树结构来看，根节点就是 1。
父结点
也叫双亲结点，一个结点如果有上一级，则称这个上一级是它的父结点，如果没有上一级，则该结点无父结点。按上图的树结构来看，可以说是父节点有 1、2、3、5、6、22。
子结点
一个结点如果有下一级，则称这个下一级是它的子结点，如果没有下一级，则该结点无子结点。按上图的树结构来看，其实除了根结点以外，各个结点都是它们对应父结点的子结点。
路径
从根结点访问其他结点所需要经过的结点。比如从 1 要走到 31，则路径是 1、3、31。
结点的度
一个结点拥有多少个子结点，就认为它的度是多少。比如根结点 1，它的度就是 5。
结点的权
【数据结构与算法|浅入浅出二叉树】结点的权值，图中每个结点都有对应的数字，这些数字就是对应结点的权。
叶子结点
没有子结点的结点，按上图的树结构来看，叶子结点有 21、221、222、223、31、51、52、61。
子树
还是上图，试着把结点 2 单独拿出来看，会发现它和它的子结点也能构成树结构。这颗树在整颗大的树里边，所以称为子树。
层
结点的层次从根开始定义起，根为第一层，根的孩子是二层，依次累计。上图的树结构层次就是 4。
树的高度
树的最大层数，上图的树结构最大层数就是从根结点开始，到最底层的叶子结点，高度是 4。
森林
多个树组成的集合，想象现在有好多颗树，每一颗树结构不一，它们共同构成森林。

二叉树的概述任何子结点的数量都不超过 2，就是一颗二叉树。比如之前举例的图，明显就不是二叉树。二叉树的子结点分左结点和右结点，不能随意颠倒位置。
二叉树也有分类：

满二叉树
所有叶子结点都在最后一层，而且结点总数为 2^n - 1，n 是树的高度。

文章图片
完全二叉树
所有叶子结点都在最后一层或倒数第二层，且最后一层叶子结点在左边延续，倒数第二层的叶子结点在右边连续。即最后一层的叶子结点总是从左往右，倒数第二层总是从右到左。满二叉树也是一颗完全二叉树。

文章图片

链式存储的二叉树顾名思义，用链表的方式去实现二叉树结构。用代码去实现，首先我们要创建一个结点类。

public class TreeNode { // 节点的权 private int value; // 左子结点 private TreeNode leftNode; // 右子结点 private TreeNode rightNode; public TreeNode(int value) { this.value = https://www.it610.com/article/value; } // 剩下的都是 set/get 方法了 ... }

其次，和链表有头结点一样，二叉树也需要有根结点辅助操作，作为创建二叉树的基础。

public class BinaryTree {private TreeNode root; public TreeNode getRoot() { return root; }public void setRoot(TreeNode root) { this.root = root; } }

万事具备，向根结点添加左右子结点即可。

public class TestBinaryTree {public static void main(String[] args) { // 创建二叉树 BinaryTree binaryTree = new BinaryTree(); // 创建根结点 TreeNode root = new TreeNode(1); // 设置根结点 binaryTree.setRoot(root); // 创建一个左结点 TreeNode rootL = new TreeNode(2); // 把新创建的结点设置为根结点的左子结点 root.setLeftNode(rootL); // 创建一个右结点 TreeNode rootR = new TreeNode(3); // 把新创建的结点设置为根结点的右子结点 root.setRightNode(rootR); // 为第二层的左结点创建两个子结点 rootL.setLeftNode(new TreeNode(4)); rootL.setRightNode(new TreeNode(5)); // 为第二层的右结点创建两个子结点 rootR.setLeftNode(new TreeNode(6)); rootR.setRightNode(new TreeNode(7)); } }

遍历二叉树二叉树的遍历方式有三种，分别是：前序遍历、中序遍历、后序遍历。

文章图片

以上图为例，记住一点，所谓的前序、中序、后序都是参考当前结点的位置。前序遍历，即是先取当前结点的权，然后是它的左子结点，最后是右子结点。从根结点开始，遍历过程中每一个结点都要遵守这个规矩。
因此上图前序遍历得到的结果是：1、2、4、5、3、6、7；中序遍历得到的结果是：4、2、5、1、6、3、7；后序遍历得到的结果是：4、5、2、6、3、7、1。代码实现用到递归的思想。

public class TestBinaryTree {public static void main(String[] args) { // 之前创建二叉树的代码，这里就省略不写了 ... // 前序遍历树 binaryTree.frontShow(); System.out.println("-----------------"); // 中序遍历树 binaryTree.midShow(); System.out.println("-----------------"); // 后序遍历树 binaryTree.afterShow(); } }

public class BinaryTree {private TreeNode root; public TreeNode getRoot() { return root; }public void setRoot(TreeNode root) { this.root = root; }// 前序遍历 public void frontShow() { if (root != null) { root.frontShow(); } }// 中序遍历 public void midShow() { if (root != null) { root.midShow(); } }// 后序遍历 public void afterShow() { if (root != null) { root.afterShow(); } } }

public class TreeNode {// 节点的权 private int value; // 左子结点 private TreeNode leftNode; // 右子结点 private TreeNode rightNode; public TreeNode(int value) { this.value = https://www.it610.com/article/value; }// set/get 方法 ...// 前序遍历 public void frontShow() { // 先输出当前结点内容 System.out.println(value); // 输出左结点内容 if (leftNode != null) { leftNode.frontShow(); } // 输出右结点内容 if (rightNode != null) { rightNode.frontShow(); } }// 中序遍历 public void midShow() { // 输出左结点内容 if (leftNode != null) { leftNode.midShow(); } // 输出当前结点内容 System.out.println(value); // 输出右结点内容 if (rightNode != null) { rightNode.midShow(); } }// 后序遍历 public void afterShow() { // 输出左结点内容 if (leftNode != null) { leftNode.afterShow(); } // 输出右结点内容 if (rightNode != null) { rightNode.afterShow(); } // 输出当前结点内容 System.out.println(value); } }

二叉树中结点的查找查找结点，实际就是把整颗二叉树遍历一次，依次比对，找出结果并返回。这里以前序查找为例，其余的大同小异。

public class TestBinaryTree {public static void main(String[] args) { // 创建二叉树 ... // 前序查找 TreeNode result = binaryTree.frontSearch(5); System.out.println(result); } }

public class BinaryTree {private TreeNode root; public TreeNode getRoot() { return root; }public void setRoot(TreeNode root) { this.root = root; }/** * 前序查找 * @return 目标结点 */ public TreeNode frontSearch(int value) {return root.frontSearch(value); } }

public class TreeNode {// 节点的权 private int value; // 左子结点 private TreeNode leftNode; // 右子结点 private TreeNode rightNode; public TreeNode(int value) { this.value = https://www.it610.com/article/value; }/** * 前序查找 * @return 目标结点 */ public TreeNode frontSearch(int value) { TreeNode target = null; // 返回本结点 if (this.value == value) { return this; } // 向左子结点方向查找 if (leftNode != null) { target = leftNode.frontSearch(value); } // 如果不为空，证明找到结点，返回 if (target != null) { return target; } // 向右子结点方向查找 if (rightNode != null) { target = rightNode.frontSearch(value); } return target; } }

删除二叉树的结点对于一颗普通的二叉树而言，删除一个结点就等同于把对应的整颗子树一并删掉。之后讲到二叉排序树时，就不是这样操作了。
删除时要区分是根结点还是其他结点。如果是根结点的话，直接置为 null 就好了。但如果不是，则依次比较左右两个子结点，符合就直接置为 null。如果都不符合，那就递归调用左右结点的 delete 方法。

public class TestBinaryTree {public static void main(String[] args) { // 创建一颗子树 ... // 删除一个结点 binaryTree.delete(5); binaryTree.frontShow(); } }

public class BinaryTree {private TreeNode root; .../** * 根据权值删除结点 * @param value 依据权值 */ public void delete(int value) { // 要删除的是根结点 if (root.getValue() == value) { root = null; } else { // 要删除的是其他结点 root.delete(value); } } }

public class TreeNode {// 节点的权 private int value; // 左子结点 private TreeNode leftNode; // 右子结点 private TreeNode rightNode; .../** * 根据权值删除结点 * @param value 依据权值 */ public void delete(int value) { TreeNode parent = this; // 判断左子结点 if (parent.leftNode != null && parent.leftNode.value =https://www.it610.com/article/= value) { parent.leftNode = null; return; } // 判断右子结点 if (parent.rightNode != null && parent.rightNode.value == value) { parent.rightNode = null; return; } parent = leftNode; if (parent != null) { parent.delete(value); } parent = rightNode; if (parent != null) { parent.delete(value); } } }

顺序存储的二叉树

文章图片

二叉树还可以用数组实现，或者说，任意一个数组都可以转化为二叉树。就上图二叉树而言，它对应的数组实现就是 [1,2,3,4,5,6,7]。
并不是每颗二叉树都长得这么规矩，有可能会出现缺胳膊少腿的情况。通常情况下，顺序存储的二叉树只考虑完全二叉树（满二叉树也是完全二叉树），否则没有意义。
顺序存储的二叉树还有其对应的性质公式，常用的有如下三个：

数组中第 n 个元素的左子结点下标为：2*n + 1
数组中第 n 个元素的左子结点下标为：2*n + 2
数组中第 n 个元素的父节点下标为：(n-1)/ 2

顺序存储的二叉树的遍历我们把一个数组当成二叉树作前序遍历，剩下的中序和后序遍历也大同小异了。

public class TestBinaryTree {public static void main(String[] args) {int[] data = https://www.it610.com/article/new int[]{1, 2, 3, 4, 5, 6, 7}; ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(data); // 前序遍历 arrayBinaryTree.frontShow(); } }

public class ArrayBinaryTree {private int[] data; public ArrayBinaryTree(int[] data) { this.data = https://www.it610.com/article/data; }public int[] getData() { return data; }public void setData(int[] data) { this.data = data; }public void frontShow() { frontShow(0); }public void frontShow(int index) { if (data == null || data.length == 0) { return; } // 先遍历当前结点的内容 System.out.println(data[index]); // 遍历左子结点 if (2 * index + 1 < data.length) { frontShow(2 * index + 1); } // 遍历右子结点 if (2 * index + 2 < data.length) { frontShow(2 * index + 2); } } }