Java实现二叉树（下）

1.前言

http://t.csdnimg.cn/lO4S7

在前文我们已经简单的讲解了二叉树的基本概念，本文将讲解具体的实现

2.基本功能的实现

2.1获取树中节点个数

    public int size(TreeNode root){if(root==null){return 0;}int ret=size(root.left)+size(root.right)+1;return ret;}public static int nodeSize;public void size2(TreeNode root){if(root==null){return;}nodeSize++;size2(root.left);size2(root.right);}

2.2获取叶子节点的个数

   /*** 求叶子节点个数* @param root* @return*/public int getLeafNodeCount(TreeNode root){if(root==null){return 0;}if(root.left==null&&root.right==null){return 1;}return getLeafNodeCount(root.left)+getLeafNodeCount(root.right);}public int leftSize;public void getLeafNodeCount2(TreeNode root){if(root==null){return;}if(root.left==null&&root.right==null){leftSize++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}

2.3获取第K层节点的个数

 /*第k层有几个节点*/public int getKLevelNodeCount(TreeNode root,int k){if(root==null){return 0;}if(k==1){return 1;}return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right,k-1);}

2.4获取二叉树的高度

 public int getHeight(TreeNode root){if(root==null){return 0;}int leftHeight=getHeight(root.left);int rightHeight=getHeight(root.right);return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}

2.5检测值为value的元素是否存在

 /**** @param root* @param val* @return*/public TreeNode find(TreeNode root,char val){if(root==null){return null;}if(root.val==val){return root;}TreeNode ret=find(root.left,val);if(ret!=null){return ret;}ret=find(root.right,val);if(ret!=null){return ret;}return null;}

2.6判断一棵树是不是完全二叉树

  public boolean isSameTree(TreeNode p,TreeNode q){if(p!=null&&q==null||p==null&&q!=null){return false;}if(p==null&&q==null){return true;}if(p.val!=q.val){return false;}return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);}

3.二叉树的应用 

在知晓了二叉树相关功能的底层实现之后，我们应用二叉树知识来解答

3.1二叉树遍历

二叉树遍历_牛客题霸_牛客网

 

根据题目我们可以知道这其实是两个题目，一是创建二叉树，二是中序遍历结果

所以我们分成两部来完成

先定义二叉树的结构

 class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val = val;}}

当不为'#'的时候，我们就创建节点

 public static int i = 0;public static TreeNode createTree(String str) {TreeNode root = null;if (str.charAt(i) != '#') {root = new TreeNode(str.charAt(i));i++;root.left = createTree(str);root.right = createTree(str);} else {i++;}return root;}

最后，我们进行中序遍历——根左子树-根节点-根右子树的顺序来递归即可 

    public static void inorder(TreeNode root){if(root==null){return;}inorder(root.left);System.out.print(root.val+" ");inorder(root.right);}

3.2二叉树的层序遍历

. - 力扣（LeetCode）

这题主要是对二叉树的层序遍历，对于层序遍历是如何遍历的，我们在上文已经讲过——从上而下，自左向右依次遍历.

 在了解到概念之后，我们就可以进行解答了

我们要对知识进行灵活的应用，这种从上而下，自左向右的逻辑与前面所讲到的栈和队列知识中队列先进先出逻辑类似，所以我们可以用创建队列来解答

1.是否为空，若为空，则返回空列表

2.若不为空，则进入循环判断（当队列为空则跳出循环），创建一个列表来打印每层的结果

3.将每层结果存入ret,最后返回ret即可

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> ret=new ArrayList<>();if(root==null){return ret;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);while(!queue.isEmpty()){int size=queue.size();List<Integer> list=new ArrayList<>();//每层while(size>0){TreeNode cur=queue.poll();list.add(cur.val);if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}size--;}ret.add(list);}return ret;}
}

---

对二叉树的基础知识讲解就到这里，如果上述内容对您有帮助，希望给个三连谢谢！