博主主頁:?碼農派大星.

關注博主帶你了解更多數據結構知識

1我們先來模擬創建一個二叉樹

public class TestBinaryTreee {static class TreeNode{public char val;public  TreeNode left;public  TreeNode right;public TreeNode(char val) {this.val = val;}}public TreeNode creatTree(){TreeNode A  = new TreeNode('A');TreeNode B  = new TreeNode('B');TreeNode C  = new TreeNode('C');TreeNode D  = new TreeNode('D');TreeNode E  = new TreeNode('E');TreeNode F  = new TreeNode('F');TreeNode G  = new TreeNode('G');TreeNode H  = new TreeNode('H');A.left = B;A.right = C;B.left = D;B.right = E;C.left = F;C.right = G;E.right = H;return A;//就是根節點}
}

2分別實現它的前中后序遍歷

1前序遍歷

// 前序遍歷void preOrder(TreeNode root){if (root == null){return;}System.out.print(root.val+" ");//遞歸遍歷左子樹preOrder(root.left);//第歸遍歷右子樹preOrder(root.right );}

 TestBinaryTreee testBinaryTreee = new TestBinaryTreee();testBinaryTreee.creatTree();TestBinaryTreee.TreeNode root = testBinaryTreee.creatTree();testBinaryTreee.preOrder(root);System.out.println();

2中序遍歷

// 中序遍歷void inOrder(TreeNode root){if (root == null){return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}

 testBinaryTreee.inOrder(root);System.out.println();

3后序遍歷

// 后序遍歷void postOrder(TreeNode root){if (root == null){return;}inOrder(root.left);inOrder(root.right);System.out.print(root.val+" ");}

testBinaryTreee.postOrder(root);System.out.println();

3?獲取樹中節點的個數

 //求有多少個節點
1:public int size(TreeNode root){if (root == null){return 0;}int ret = size(root.left)+size(root.right)+1;return ret;}
2:public static int nodeSize;public void size2(TreeNode root){if (root == null){return ;}nodeSize++;size2(root.left);size2(root.right);}

 System.out.println(testBinaryTreee.size(root));testBinaryTreee.size2(root);System.out.println(TestBinaryTreee.nodeSize);

4獲取葉子節點的個數

//求葉子結點個數
1: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);}
2:public int leafSize;public void getLeafNodeCount2(TreeNode root){if (root == null){return ;}if(root.left == null && root.right ==null){leafSize++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}

 System.out.println(testBinaryTreee.getLeafNodeCount(root));testBinaryTreee.getLeafNodeCount2(root);System.out.println(testBinaryTreee.leafSize);

5 獲取第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);}

System.out.println(testBinaryTreee.getKLevelNodeCount(root, 3));

?

6獲取二叉樹的高度

 //獲取二叉樹高度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;}

int height = testBinaryTreee.getHeight(root);System.out.println(height);

7檢測值為value的元素是否存在

 // 檢測值為val的元素是否存在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;}

TestBinaryTreee.TreeNode retN = testBinaryTreee.find(root, 'E');System.out.println(retN.val);