网站开发报价 知乎,常熟网站建设哪家好,建设银行企业网站进不去,网络媒体整合营销#x1f435;本篇文章将对二叉树的一些基础操作进行梳理和讲解 一、操作简述
int size(Node root); // 获取树中节点的个数int getLeafNodeCount(Node root); // 获取叶子节点的个数int getKLevelNodeCount(Node root,int k); // 获取第K层节点的个数int getHeight(Node r… 本篇文章将对二叉树的一些基础操作进行梳理和讲解 一、操作简述
int size(Node root); // 获取树中节点的个数int getLeafNodeCount(Node root); // 获取叶子节点的个数int getKLevelNodeCount(Node root,int k); // 获取第K层节点的个数int getHeight(Node root); // 获取二叉树的高度TreeNode find(Node root, int val); // 检测值为value的元素是否存在void levelOrder(Node root); //层序遍历boolean isCompleteTree(Node root) // 判断一棵树是不是完全二叉树接下来会对下面这棵树进行上述操作: public class BinaryTree {static class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;}}
} 二、代码实现
1.获取树中结点的个数
思路定义一个nodeSize, 按照二叉树前序遍历的方式遍历这颗二叉树, 每遍历一个结点, nodeSize就1 public int nodeSize; //nodeSize不能写到方法内部,否则每次递归nodeSize都会被初始化为0,最终导致结果错误public int size(TreeNode root) {if (root null) {return 0;}nodeSize;size(root.left);size(root.right);return nodeSize;}2. 获取树中叶子结点的个数
思路叶子结点也就是没有左右孩子的结点该方法的实现和上一个方法思路大体一致定义一个leafNode在遍历这颗二叉树的过程中如果该节点没有左右孩子则leafNode 1 public static int leafNode;public int getLeafNodeCount(TreeNode root) { //计算叶子结点个数if (root null) {return 0;}if (root.left null root.right null) {leafNode;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafNode;}3. 计算k层结点的个数 思路假如要计算第3层结点的个数k 3整个树的第3层也就是这个树的左子树B的第2层右子树C的第2层也就是B的左子树的第一层 B的右子树的第一层 和C的左子树的第一层 C的右子树的第一层通过前序遍历的方式每遍历到一层k就减1当k 1时就返回1 public int getKLevelNodeCount(TreeNode root,int k) {//计算第k层结点的个数if (root null) {return 0;}if (k 1) {return 1;}k--;return getKLevelNodeCount(root.left, k) getKLevelNodeCount(root.right, k);}4. 获取树的高度 思路整个树的高度也就是左子树的高度和右子树的高度的最大值1再通过递归的方式求左子树和右子树的高度 public int getHeight(TreeNode root) {if (root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.max(leftHeight, rightHeight) 1;}5. 检测值为val的元素的结点是否存在
思路遍历这棵二叉树找到值为val的结点后逐层返回直接看代码 public TreeNode find(TreeNode root, char val) {if (root null) {return null;}if (root.val val) {return root;}TreeNode leftNode find(root.left, val);//必须用一个变量来接收,否则上述返回的root没有意义,最终返回的还是nullif (leftNode ! null) { //leftNode不为空说明找到了将其返回return leftNode;}TreeNode rightNode find(root.right, val);if (rightNode ! null) {return rightNode;}return null; //没有找到val结点就返回null}6. 层序遍历二叉树
思路定义一个队列先将这个树的根结点入队之后通过循环如果队列不为空则让队头结点出队判断该结点的左和右是否为空不为空的入队如此循环知道队列为空整个二叉树遍历完毕 public void levelOrder(TreeNode root) {if (root null) {return;}QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur queue.poll();System.out.print(cur.val );if(cur.left ! null) {queue.offer(cur.left);}if (cur.right ! null) {queue.offer(cur.right);}}}7. 判断一棵树是不是完全二叉树
以这棵树为例 一开始和层序遍历的思路一样定义一个队列将树的根结点存入队列中接下来设置一个循环当队列不为空的情况下将队头元素出队如果出队结点不为空则直接将其左右孩子入队不用判断其左右孩子是否为空如果出队结点为空则结束该循环
完成上述操作后再设置一个循环循环条件仍然是队列不为空每次循环都将队头元素出队然后进行判断如果该结点不为空则该树不是完全二叉树
根据上述操作对上面这棵树进行实操 将根结点入队之后进入循环将队头元素出队A结点不为空所以将其左右孩子入队之后再将队头元素出队B结点不为空所以再将其左右孩子入队 再将C出队C结点不为空再将其左右孩子入队再将D结点出队D结点不为空再将其左右孩子入队之后再将队头元素出队此时出队的元素为空此循环结束 进入第二个循环只要队列不为空就出队队头元素然后对其进行判断只要出队元素不为空则其不是完全二叉树上述队列全部为null所以该树是完全二叉树
如果是下面这棵树在第一次循环后会是如下情况 在第二个循环由于D结点不为null所以该树不是完全二叉树
代码如下 public boolean isCompleteTree(TreeNode root) {if (root null) {return false;}QueueTreeNode queue new LinkedList();queue.offer(root);while(!queue.isEmpty()) {TreeNode cur queue.poll();if (cur null) {break;}queue.offer(cur.left);queue.offer(cur.right);}while(!queue.isEmpty()) {TreeNode cur queue.poll();if (cur ! null) {return false;}}return true;}本篇文章到此结束
