无锡网站设计公司,引擎优化搜索,推广是干嘛的,企业网站推广制作教程专栏#xff1a;数据结构(Java版) 个人主页#xff1a;手握风云 目录
一、二叉树的遍历
1.1. 前序遍历
1.2. 中序遍历
1.3. 后序遍历
1.4. 完整代码
二、二叉树的基本操作
2.1. 获取树中结点个数
2.1. 获取叶子结点个数
2.3. 获取第k层结点的个数
2.4. 获取二叉树的… 专栏数据结构(Java版) 个人主页手握风云 目录
一、二叉树的遍历
1.1. 前序遍历
1.2. 中序遍历
1.3. 后序遍历
1.4. 完整代码
二、二叉树的基本操作
2.1. 获取树中结点个数
2.1. 获取叶子结点个数
2.3. 获取第k层结点的个数
2.4. 获取二叉树的高度
2.5. 检测值为value的元素是否存在 一、二叉树的遍历 1.1. 前序遍历 前序遍历又叫先根遍历。每一个节点的遍历顺序都是按照“根——左子树——右子树”的顺序来遍历每遇到一个新的结点都看作是一棵新的树。如果遇到空则递归回上一个节点。A的右子树遍历过程也如下所以前序遍历的结果为“ABDCEF”。 1.2. 中序遍历 中序遍历的顺序为“左子树——根——右子树”遇到一个结点先去遍历左子树如果该节点的根为空才能递归回来进行打印。所以中序遍历的结果为“DBAECF”。 1.3. 后序遍历 后序遍历的顺序为“左子树——右子树——根”遍历过程与上面两种都差不多这里不再多说。后序遍历的顺序为“DBEFCA”。 1.4. 完整代码
public class BinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}public TreeNode CreateTree(){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);A.left B;A.right C;B.left D;C.left E;C.right F;return A;}public void PrevOrder(TreeNode root){//前序遍历if(root null){return;}System.out.print(root.val );PrevOrder(root.left);PrevOrder(root.right);}public void InOrder(TreeNode root){//中序遍历if(root null){return;}InOrder(root.left);System.out.print(root.val );InOrder(root.right);}public void PostOrder(TreeNode root){//后序遍历if(root null){return;}PostOrder(root.left);PostOrder(root.right);System.out.print(root.val );}
}
public class Test {public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();BinaryTree.TreeNode root binaryTree.CreateTree();System.out.print(前序遍历);binaryTree.PrevOrder(root);System.out.println();System.out.print(中序遍历);binaryTree.InOrder(root);System.out.println();System.out.print(后序遍历);binaryTree.PostOrder(root);}
}二、二叉树的基本操作
2.1. 获取树中结点个数 我们先回想以下如何获取链表中的结点个数。我们定义一个ListNode cur变量当cur不为空时count递增。同样的我们上面已经实现了二叉树结点的遍历我们也只需要再定义一个计数器只要root不为空countNode就递增。 public void NodeSize(TreeNode root){if(root null){return;}CountSize;NodeSize(root.left);NodeSize(root.right);} 上面的是遍历思路还有一种子问题思路。整棵树的结点个数等于左树的结点数和右树的结点数再加一只要root为空那么我们就可以结束递归。 public int NodeSize2(TreeNode root){if(root null){return 0;}int tmp NodeSize2(root.left)NodeSize2(root.right)1;return tmp;}
2.1. 获取叶子结点个数 叶子结点就是没有左右子树的结点递推公式为左子树叶子结点加右子树结点结束条件为结点的左右子树都为空。 //获取叶子结点个数public int getLeafNodeCount(TreeNode root){if(root null){return 0;}else if(root.left null root.right null){return 1;}else{return getLeafNodeCount(root.left) getLeafNodeCount(root.right);}}public int LeafCount;//遍历问题public void getLeafNodeCount2(TreeNode root){if(root null){return;}if(root.left null root.right null){LeafCount;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}
2.3. 获取第k层结点的个数 比如我们要想获取第3层结点的个数就要求root.left第2层和root.right的第二层相当于左树的第一层和右树的第一层。当k1时已经找到这一层此时也是递归的结束条件。 //获取第k层结点的个数public int getLevelNodeCount(TreeNode root,int k){if(root null){return 0;}if(k 1){return 1;}return getLevelNodeCount(root.right,k-1) getLevelNodeCount(root.left,k-1);}
2.4. 获取二叉树的高度 求二叉树的高度整棵树的高度等于左子树高度的最大值或者右子树高度的最大值加一当root为空的时候高度为0。由于我们不知道是左子树高还是右子树高所以两边都需要遍历。 //获取二叉树的高度public int getHeight(TreeNode root){if(root null){return 0;}int leftH getHeight(root.left);int rightH getHeight(root.right);return Math.max(leftH,rightH) 1;}
2.5. 检测值为value的元素是否存在 我们先检查根结点是不是然后再遍历左子树和右子树当我们找到了val值直接返回不用再递归下面了。 // 检测值为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;}
public class Solution {public static void main(String[] args) {BinaryTree binaryTree new BinaryTree();BinaryTree.TreeNode root binaryTree.CreatTree();binaryTree.NodeSize(root);System.out.println(结点个数binaryTree.CountSize);System.out.println(结点个数binaryTree.NodeSize2(root));System.out.println(叶子结点个数binaryTree.getLeafNodeCount(root));binaryTree.getLeafNodeCount2(root);System.out.println(叶子结点个数binaryTree.LeafCount);System.out.println(第3层结点个数binaryTree.getLevelNodeCount(root,3));System.out.println(二叉树的高度binaryTree.getHeight(root));}
}
