二叉树的基础实现

基础实现"/>

二叉树的基础实现

普通二叉树的实现

package bintree;
public class MyBinTree {// 二叉树的节点类定义private static class TreeNode {// 当前节点的值int val;// 左子树的树根TreeNode left;// 右子树的树根TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode build() {TreeNode node1 = new TreeNode(1);TreeNode node2 = new TreeNode(2);TreeNode node3 = new TreeNode(3);TreeNode node4 = new TreeNode(4);TreeNode node5 = new TreeNode(5);TreeNode node6 = new TreeNode(6);TreeNode node7 = new TreeNode(7);node1.left = node2;node1.right = node4;node2.left = node3;node4.left = node5;node4.right = node6;node6.right = node7;return node1;}// 传入一颗以root问根的二叉树，就能按照前序遍历的方式进行遍历，输出每个节点的值public void preOrder(TreeNode root) {// 1.base caseif (root == null) {return;}// 先输出当前根节点的值System.out.print(root.val + " ");// 继续去访问左子树并打印preOrder(root.left);// 继续访问右子树的所有节点preOrder(root.right);}//传入一颗以root为根的二叉树，就能按照中序遍历的方式进行遍历输出public void inOrder(TreeNode root) {// 1.base caseif (root == null) {return;}// 先访问左子树，按照中序遍历的方式inOrder(root.left);// 中序位置，遍历当前的树根并输出System.out.print(root.val + " ");// 继续访问右子树inOrder(root.right);}//传入一颗以root为根的二叉树，就能按照后序遍历的方式进行遍历输出public void postOrder(TreeNode root) {if (root == null) {return;}// 先访问左子树postOrder(root.left);// 再访问右子树postOrder(root.right);// 最后访问根节点System.out.print(root.val + " ");}// 传入一颗以root为根的二叉树，就能求出当前二叉树的节点个数并返回public int getNodes(TreeNode root) {
//        // 1.base case
//        if (root == null) {
//            return 0;
//        }
//        // 整棵树的节点个数 = 当前树根(1) + 左子树的节点个数 + 右子树的节点个数
//        return 1 + getNodes(root.left) + getNodes(root.right);return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);}// TODO 借助队列打印一下层序遍历的每个节点值public void levelOrder(TreeNode root) {}//传入一颗以root为根的二叉树，就能求出该二叉树的叶子节点个数并返回public int getLeafNodes(TreeNode root) {if (root == null) {return 0;}if (root.left == null && root.right == null) {return 1;}return getLeafNodes(root.left) + getLeafNodes(root.right);}//传入一颗以root为根的二叉树，就能求出其高度并返回public int height(TreeNode root) {// 1.base caseif (root == null) {return 0;}// 此时树不为空，高度 = 左右子树的高度最大值 + 1(当时树根这一层)return 1 + Math.max(height(root.left),height(root.right));}//  传入一颗以root为根的二叉树，就能求出第k层的节点个数并返回public int getKLevelNodes(TreeNode root,int k) {// 1.base caseif (root == null || k == 0) {return 0;}// 2.当前k == 1，无论二叉树结构如何，第一层只可能有1个节点if (k == 1) {return 1;}// 此时二叉树不为空，且k > 1// 要求第k层节点个数 = 左子树的k -1层节点数 + 右子树的k - 1层节点数return getKLevelNodes(root.left,k - 1) + getKLevelNodes(root.right,k - 1);}//在当前以root为根的二叉树中，查找值val是否存在public boolean contains(TreeNode root,int val) {// 1.base caseif (root == null) {return false;}// 当前树根节点就是待查找的值if (root.val == val) {return true;}return contains(root.left,val) || contains(root.right,val);}public static void main(String[] args) {MyBinTree tree = new MyBinTree();TreeNode root = tree.build();System.out.println(tree.contains(root,5));System.out.println(tree.contains(root,10));System.out.println("该二叉树的第三层节点个数为 : ");System.out.println(tree.getKLevelNodes(root,4));System.out.println("二叉树的高度为 : ");System.out.println(tree.height(root));System.out.println("二叉树的节点个数为 : ");int num = tree.getNodes(root);System.out.println(num);System.out.println("二叉树的叶子节点个数为 : ");System.out.println(tree.getLeafNodes(root));System.out.println("前序遍历结果为 : ");tree.preOrder(root);System.out.println();System.out.println("中序遍历结果为 : ");tree.inOrder(root);System.out.println();System.out.println("后序遍历的结果为 : ");tree.postOrder(root);}
}