🎈四.二叉树的相关操作
1.前序遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
//前序遍历publicvoidpreOrder(TreeNoderoot) { if (root==null) { return; } System.out.print(root.val+" "); preOrder(root.left); preOrder(root.right); }
2.中序遍历
中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
//中序遍历publicvoidinOrder(TreeNoderoot) { if (root==null) { return; } inOrder(root.left); System.out.print(root.val+" "); inOrder(root.right); }
3.后序遍历
后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。
//后序遍历publicvoidpostOrder(TreeNoderoot) { if (root==null) { return; } postOrder(root.left); postOrder(root.right); System.out.print(root.val+" "); }
4.获取书中节点的个数
// 获取树中节点的个数publicintsize(TreeNoderoot) { if (root==null) { return0; } intleftSize=size(root.left); intrightSize=size(root.right); returnleftSize+rightSize+1;//个数=左树的节点树+右树的节点树+1 }
5.获取叶子节点数
// 获取叶子节点的个数publicintgetLeafNodeCount(TreeNoderoot) { if (root==null) { return0; } if (root.left==null&&root.right==null) { return1;//如果左右两边都为空，那么一定是叶子节点 } intleftSize=getLeafNodeCount(root.left); intrightSize=getLeafNodeCount(root.right); returnleftSize+rightSize; }
6.获取第k层的节点数\
// 获取第K层节点的个数publicintgetKLevelNodeCount(TreeNoderoot, intk) { if (root==null) { return0; } if (k==1) { return1; } intleftSize=getKLevelNodeCount(root.left, k-1); intrightSize=getKLevelNodeCount(root.right, k-1); returnleftSize+rightSize; }
7.获取二叉树的高度
// 获取二叉树的高度publicintgetHeight(TreeNoderoot) { if (root==null) { return0; } intleftHeight=getHeight(root.left); intrightHeight=getHeight(root.right); returnleftHeight>rightHeight?leftHeight+1 : rightHeight+1; }
8.查找value值是否存在树中
// 检测值为value的元素是否存在publicTreeNodefind(TreeNoderoot, intval) { if (root==null) { returnnull; } if (val==root.val) { returnroot; } TreeNodeleftTree=find(root.left, val); if (leftTree!=null) { returnleftTree; } TreeNoderightTree=find(root.right, val); if (rightTree!=null) { returnrightTree; } returnnull; }
