Java实现二叉树的代码怎么写(java,开发技术)

以此图为例，完整代码如下：

//基础二叉树实现//使用左右孩子表示法importjava.util.*;importjava.util.Deque;publicclassmyBinTree{privatestaticclassTreeNode{charval;TreeNodeleft;TreeNoderight;publicTreeNode(charval){this.val=val;}}publicstaticTreeNodebuild(){TreeNodenodeA=newTreeNode('A');TreeNodenodeB=newTreeNode('B');TreeNodenodeC=newTreeNode('C');TreeNodenodeD=newTreeNode('D');TreeNodenodeE=newTreeNode('E');TreeNodenodeF=newTreeNode('F');TreeNodenodeG=newTreeNode('G');TreeNodenodeH=newTreeNode('H');nodeA.left=nodeB;nodeA.right=nodeC;nodeB.left=nodeD;nodeB.right=nodeE;nodeE.right=nodeH;nodeC.left=nodeF;nodeC.right=nodeG;returnnodeA;}//方法1(递归)//先序遍历:根左右publicstaticvoidpreOrder(TreeNoderoot){if(root==null){return;}System.out.print(root.val+"");preOrder(root.left);preOrder(root.right);}//方法1(递归)//中序遍历publicstaticvoidinOrder(TreeNoderoot){if(root==null){return;}inOrder(root.left);System.out.print(root.val+"");inOrder(root.right);}//方法1(递归)//后序遍历publicstaticvoidpostOrder(TreeNoderoot){if(root==null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+"");}//方法2(迭代)//先序遍历(迭代)publicstaticvoidpreOrderNonRecursion(TreeNoderoot){if(root==null){return;}Deque<TreeNode>stack=newLinkedList<>();stack.push(root);while(!stack.isEmpty()){TreeNodecur=stack.pop();System.out.print(cur.val+"");if(cur.right!=null){stack.push(cur.right);}if(cur.left!=null){stack.push(cur.left);}}}//方法2(迭代)//中序遍历(迭代)publicstaticvoidinorderTraversalNonRecursion(TreeNoderoot){if(root==null){return;}Deque<TreeNode>stack=newLinkedList<>();//当前走到的节点TreeNodecur=root;while(!stack.isEmpty()||cur!=null){//不管三七二十一，先一路向左走到根儿~while(cur!=null){stack.push(cur);cur=cur.left;}//此时cur为空，说明走到了null，此时栈顶就存放了左树为空的节点cur=stack.pop();System.out.print(cur.val+"");//继续访问右子树cur=cur.right;}}//方法2(迭代)//后序遍历(迭代)publicstaticvoidpostOrderNonRecursion(TreeNoderoot){if(root==null){return;}Deque<TreeNode>stack=newLinkedList<>();TreeNodecur=root;TreeNodeprev=null;while(!stack.isEmpty()||cur!=null){while(cur!=null){stack.push(cur);cur=cur.left;}cur=stack.pop();if(cur.right==null||prev==cur.right){System.out.print(cur.val+"");prev=cur;cur=null;}else{stack.push(cur);cur=cur.right;}}}//方法1(递归)//传入一颗二叉树的根节点，就能统计出当前二叉树中一共有多少个节点，返回节点数//此时的访问就不再是输出节点值，而是计数器+1操作publicstaticintgetNodes(TreeNoderoot){if(root==null){return0;}return1+getNodes(root.left)+getNodes(root.right);}//方法2(迭代)//使用层序遍历来统计当前树中的节点个数publicstaticintgetNodesNoRecursion(TreeNoderoot){if(root==null){return0;}intsize=0;Deque<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();size++;if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}}returnsize;}//方法1(递归)//传入一颗二叉树的根节点，就能统计出当前二叉树的叶子结点个数publicstaticintgetLeafNodes(TreeNoderoot){if(root==null){return0;}if(root.left==null&&root.right==null){return1;}returngetLeafNodes(root.left)+getLeafNodes(root.right);}//方法2(迭代)//使用层序遍历来统计叶子结点的个数publicstaticintgetLeafNodesNoRecursion(TreeNoderoot){if(root==null){return0;}intsize=0;Deque<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){TreeNodecur=queue.poll();if(cur.left==null&&cur.right==null){size++;}if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}}returnsize;}//层序遍历publicstaticvoidlevelOrder(TreeNoderoot){if(root==null){return;}//借助队列来实现遍历过程Deque<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();for(inti=0;i<size;i++){TreeNodecur=queue.poll();System.out.print(cur.val+"");if(cur.left!=null){queue.offer(cur.left);}if(cur.right!=null){queue.offer(cur.right);}}}}//传入一个以root为根节点的二叉树，就能求出该树的高度publicstaticintheight(TreeNoderoot){if(root==null){return0;}return1+Math.max(height(root.left),height(root.right));}//求出以root为根节点的二叉树第k层的节点个数publicstaticintgetKLevelNodes(TreeNoderoot,intk){if(root==null||k<=0){return0;}if(k==1){return1;}returngetKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);}//判断当前以root为根节点的二叉树中是否包含指定元素val，//若存在返回true，不存在返回falsepublicstaticbooleancontains(TreeNoderoot,charvalue){if(root==null){returnfalse;}if(root.val==value){returntrue;}returncontains(root.left,value)||contains(root.right,value);}publicstaticvoidmain(String[]args){TreeNoderoot=build();System.out.println("方法1(递归)：前序遍历的结果为:");preOrder(root);System.out.println();System.out.println("方法2(迭代)：前序遍历的结果为:");preOrderNonRecursion(root);System.out.println();System.out.println("方法1(递归)：中序遍历的结果为:");inOrder(root);System.out.println();System.out.println("方法2(迭代)：中序遍历的结果为:");inorderTraversalNonRecursion(root);System.out.println();System.out.println("方法1(递归)：后序遍历的结果为:");postOrder(root);System.out.println();System.out.println("方法2(迭代)：后序遍历的结果为:");postOrderNonRecursion(root);System.out.println();System.out.println();System.out.println("层序遍历的结果为:");levelOrder(root);System.out.println();System.out.println();System.out.println("方法1(递归)：当前二叉树一共有:"+getNodes(root)+"个节点数");System.out.println("方法2(迭代)：当前二叉树一共有:"+getNodesNoRecursion(root)+"个节点数");System.out.println("方法1(递归)：当前二叉树一共有:"+getLeafNodes(root)+"个叶子节点数");System.out.println("方法2(迭代)：当前二叉树一共有:"+getLeafNodesNoRecursion(root)+"个叶子节点数");System.out.println(contains(root,'E'));System.out.println(contains(root,'P'));System.out.println("当前二叉树的高度为:"+height(root));System.out.println("当前二叉树第3层的节点个数为:"+getKLevelNodes(root,3));}}

如上main引用结果如下：