行业知识
数据结构-树的遍历和基本操作(Java实现)
一. 二叉树的遍历
二叉���的遍历分为以下三种:
前序遍历: 访问顺序为 根节点---->左子树---->右子树
中序遍历: 访问顺序为 左子树---->根节点---->右子树
后序遍历: 访问顺序为 左子树---->右子树---->根节点
接下来针对这3种遍历方式进行详细介绍:
(1) 前序遍历
上图前序遍历顺序为 1 2 3 4 5 6
(2) 中序遍历
上图中序遍历顺序为3 2 1 5 4 6
(3) 后序遍历
上图后序遍历顺序为 3 2 5 6 4 1
(4) 层序遍历原理
除了前序遍历,中序遍历,后序遍历外,还可以对二叉树进行层序遍历. 设二叉树的根节点所在层数为1, 层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树的根节点,然后从左到右访问第2层上的结点,接着是第三层的结点,以此类推,自上而下,自左至右逐层访问树的结点的过程就是层序遍历.
上图的层序遍历为 1 2 4 3 5 6
二. 二叉树的基本操作
2.1 二叉树的创建
二叉树的存储结构分为: 顺序存储结构和类似于链表的链式存储。二叉树的链式存储是通过一个一个的结点引用起来的,常见的表示方式有二叉和三叉表示方式。在这里我们主要是使用二叉表示法来创建二叉树。
static class TreeNode { //定义好三个属性 public char val; public TreeNode left; //左节点 public TreeNode right; //右节点 public TreeNode(char val) { //提供一个结点的构造方法 new一个新结点的时候是不知道左右子树的,所以不用构造 this.val = val; } } 2.2 二叉树的创建代码实现
以下图二叉树为例创建
//以穷举的方式创建一棵二叉树出来 public TreeNode creatTree() { //要返回树的根节点,所以返回类型是 TreeNode TreeNode A = new TreeNode('A'); //创建一个结点赋值 TreeNode B = new TreeNode('B'); //创建一个结点赋值 TreeNode C = new TreeNode('C'); //创建一个结点赋值 TreeNode D = new TreeNode('D'); //创建一个结点赋值 TreeNode E = new TreeNode('E'); //创建一个结点赋值 TreeNode F = new TreeNode('F'); //创建一个结点赋值 TreeNode G = new TreeNode('G'); //创建一个结点赋值 TreeNode H = new TreeNode('H'); //创建一个结点赋值 A.left = B; A.right = C; B.left = D; B.right = E; C.left = F; C.right = G; E.right = H; return A; //返回根节点 } 2.3 二叉树的基本操作(Java实现)
2.3.1 前序遍历代码实现(递归方式)
由于二叉树是递归定义的,所以二叉树的遍历一般也是采用递归的形式,当然二叉树也可以用非递归方式遍历。这里文章用递归方式介绍。前序遍历即采用先访问根节点,再访问左子树,最后访问右子树的顺序。前序遍历也是按照类似的方式递归遍历,具体操作如下:
① 如果当前节点值为空,返回;
②如果当前节点值不为空,打印当前节点值;递归遍历左子树;递归遍历右子树。
// 前序遍历 void preOrder(TreeNode root) { if (root == null) { return; //空树是不需要遍历的 } System.out.print(root.val + " "); preOrder(root.left); //递归 preOrder(root.right); } 2.3.2 中序遍历代码实现
①如果当前节点值为空,返回;
②递归遍历左子树;打印当前节点的值;递归遍历右子树。
// 中序遍历 void inOrder(TreeNode root) { if (root == null) { return; } inOrder(root.left); System.out.print(root.val + " "); inOrder(root.right); } 2.3.3 后序遍历代码实现
①如果当前节点值为空,返回;
②递归遍历左子树;递归遍历右子树;打印当前节点的值。
// 后序遍历 void postOrder(TreeNode root) { if (root == null) { if (root == null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val + " "); } } 2.3.4 获取树中结点的个数
public static int nodeSize; //默认为0 public int size(TreeNode root){ if(root == null){ return 0; } nodeSize++; size(root.left); //遍历左子树 size(root.right); //遍历右子树 return nodeSize; } 子问题思路:
public int size2(TreeNode root){ if(root == null){ return 0; } //左子树的个数加上右子树的结点个数加上根结点 int tmp = size2(root.left)+size2(root.right)+1; return tmp; } 2.3.5 获取叶子结点的个数
//获取叶子结点个数 public static int leafSize; public void getLeafNodeCount(TreeNode root){ if(root == null){ return; } if(root.left == null && root.right == null){ //如果没有左右子树就说明是叶子节点 leafSize++; } getLeafNodeCount(root.left); //递归遍历左子树 getLeafNodeCount(root.right); //递归遍历右子树 } 子问题思路: root这棵树有多少个叶子结点 = 左子树的叶子结点 + 右子树的叶子结点
public int getLeafNodeCount2(TreeNode root){ if(root == null){ return 0; } if(root.left == null && root.right == null){ return 1; } return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right); } 2.3.6 获取第K层结点的个数
public int getKLevelNodeCount(TreeNode root,int k){ if(root == null){ return 0; } if(k == 1){ return 1; }else{ return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1); } } 2.3.7 获取树的高度
//获取树的高度 //整棵树的高度 = 左子树的高度和右子树的高度的最大值 + 1 public int getHeight(TreeNode root){ if(root == null){ return 0; } int hl = getHeight(root.left); //获取左子树的高度 int hr = getHeight(root.right); //获取右子树的高度 int max = hl>hr?hl:hr; return max+1; } 2.3.8 检测value的值是否存在
//寻找树指定的元素 public TreeNode find(TreeNode root,int val){ if(root ==null){ return null; } if(root.val == val){ //先判断根节点是不是我们要找的数据 return root; } TreeNode leftVal = find(root.left,val); //左子树去找 if(leftVal != null){ //返回值不等于空说明找到了 return leftVal; } TreeNode rightVal = find(root.right,val); //右子树去找 if(rightVal != null){ //返回值不等于空说明找到了 return rightVal; } //左右都走完没找到返回空 return null; }
下一篇:雷电模拟器游戏下载指南