【Java】二叉树：数据海洋中灯塔式结构探秘(下：基本操作) 二叉树的基本遍历。

个人主页：♡喜欢做梦

二叉树的基本遍历

1.获取树中结点个数

方法1

public static int nodeSize=0;
 // 获取树中节点的个数
 public void size(TreeNode root){
 //判断是否有节点
 if(root==null){
 return ;
 }
 nodeSize++;
 //遍历左子树节点
 size(root.left);
 //遍历右子树节点
 size(root.right);
 }

方法2

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

2.获取节点个数 

// 获取叶子节点的个数
 //叶子：度为0的节点
 public static int leafSize=0;
 public void getLeafNodeCount(TreeNode root){
 if(root==null){
 return;
 }
 //叶：度为0，没有左子树和右子树
 if(root.right==null&root.left==null){
 leafSize++;
 }
 //叶子数=右子树的叶子数+左子树的叶子数
 getLeafNodeCount(root.left);
 getLeafNodeCount(root.right);
 }

方法2

public int getLeafNodeCount2(TreeNode root){
 if(root==null){
 return 0;
 }
 if(root.right==null&root.left==null){
 return 1;
 }
 //叶子数=右子树的叶子数+左子树的叶子数
 return getLeafNodeCount2(root.left)+ getLeafNodeCount2(root.right);
 }

3.获取第k层节点个数

// 获取第K层节点的个数
 public int getKLevelNodeCount(TreeNode root,int k){
 if(root==null){
 return 0;
 }
 //当k==1时，表示当前要查找的层次
 if (k==1){
 return 1;
 }
 //递归左右子树，直到k==1，到查找的层次
 //后将左子树的该层次的节点数+右子树的该层次的节点数
 return getKLevelNodeCount(root.left,k-1)+ getKLevelNodeCount(root.right,k-1);
 }

4.获取二叉树的高度 

// 获取二叉树的高度
 //看左子树的高度和右子树的高度
 //取左子树和右子树中的最大高度
 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.判断元素位置

// 检测值为value的元素是否存在,在哪个节点
 public TreeNode find(TreeNode root, char val){
 if(root==null){
 return null;
 }
 if(root.val==val){
 return root;
 }
 TreeNode left=find(root.left,val);
 //如果目标在左子树，直接返回左节点
 if(left!=null){
 return left;
 }
 TreeNode right=find(root.right,val);
 //如果目标在右子树，直接返回右节点
 if(right!=null){
 return right;
 }
 //没有，返回null
 return null;
 }

今天就写到这里，二叉树的基本操作还有层序遍历以及判断完全二叉树，可能后续我会写到。这篇可能写的不是很好，感谢支持? ? ?