Java实现二叉树的示例代码(递归&迭代)

Java实现二叉树的示例代码(递归&迭代)

目录

1.二叉树基本概念见上节：详解java中二叉树的基础概念(递归&迭代)

2.本次展示链式存储

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

//基础二叉树实现

//使用左右孩子表示法

import java.util.*;

import java.util.Deque;

public class myBinTree {

private static class TreeNode{

char val;

TreeNode left;

TreeNode right;

public TreeNode(char val) {

this.val = val;

}

}

public static TreeNode build(){

TreeNode nodeA=new TreeNode('A');

TreeNode nodeB=new TreeNode('B');

http:// TreeNode nodeC=new TreeNode('C');

TreeNode nodeD=new TreeNode('D');

TreeNode nodeE=new TreeNode('E');

TreeNode nodeF=new TreeNode('F');

TreeNode nodeG=new TreeNode('G');

TreeNode nodeH=new TreeNode('H');

nodeA.left=nodeB;

nodeA.right=nodeC;

nodeB.left=nodeD;

nodeB.right=nodeE;

nodeE.right=nodeH;

nodeC.left=nodeF;

nodeC.right=nodeG;

return nodeA;

}

//方法1(递归)

//先序遍历: 根左右

public static void preOrder(TreeNode root){

if(root==null){

return;

}

System.out.print(root.val+" ");

preOrder(root.left);

preOrder(root.right);

}

//方法1(递归)

//中序遍历

public static void inOrder(TreeNode root){

if(root==null){

return;

}

inOrder(root.left);

System.out.print(root.val+" ");

inOrder(root.right);

}

//方法1(递归)

//后序遍历

public static void postOrder(TreeNode root){

if(root==null){

return;

}

postOrder(root.left);

postOrder(root.right);

System.out.print(root.val+" ");

}

//方法2(迭代)

//先序遍历 (迭代)

public static void preOrderNonRecursion(TreeNode root){

if(root==null){

return ;

}

Deque stack=new LinkedList<>();

stack.push(root);

while (!stack.isEmpty()){

TreeNode cur=stack.pop();

System.out.print(cur.val+" ");

if(cur.right!=null){

stack.push(cur.right);

}

if(cur.left!=null){

stack.push(cur.left);

}

}

}

//方法2(迭代)

//中序遍历 (迭代)

public static void inorderTraversalNonRecursion(TreeNode root) {

if(root==null){

return ;

}

Deque stack=new LinkedList<>();

// 当前走到的节点

TreeNode cur=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(迭代)

//后序遍历 (迭代)

public static void postOrderNonRecursion(TreeNode root){

if(root==null){

return;

}

Deque stack=new LinkedList<>();

TreeNode cur=root;

TreeNode prev=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操作

public static int getNodes(TreeNode root){

if(root==null){

return 0;

}

return 1+getNodes(root.left)+getNodes(root.right);

}

//方法2(迭代)

//使用层序遍历来统计当前树中的节点个数

public static int getNodesNoRecursion(TreeNode root){

if(root==null){

return 0;

}

int size=0;

Deque queue=new LinkedList<>();

queue.offer(root);

while (!queue.isEmpty()) {

TreeNode cur = queue.poll();

size++;

if (cur.left != null) {

queue.offer(cur.left);

}

if (cur.right != null) {

queue.offer(cur.right);

}

}

return size;

}

//方法1(递归)

//传入一颗二叉树的根节点，就能统计出当前二叉树的叶子结点个数

public static 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);

}

//方法2(迭代)

//使用层序遍历来统计叶子结点的个数

public static int getLeafNodesNoRecursion(TreeNode root){

if(root==null){

return 0;

}

int size=0;

Deque queue=new LinkedList<>();

queue.offer(root);

while (!queue.isEmpty()){

TreeNode cur=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);

}

}

return size;

}

//层序遍历

public static void levelOrder(TreeNode root) {

if(root==null){

return ;

}

// 借助队列来实现遍历过程

Deque queue =new LinkedList<>();

queue.offer(root);

while (!queue.isEmpty()){

int size=queue.size();

for (int i = 0; i < size; i++) {

TreeNode cur=queue.poll();

System.out.print(cur.val+" ");

if(cur.left!=null){

queue.offer(cur.left);

}

if(cur.right!=null){

queue.offer(cur.right);

}

}

}

}

//传入一个以root为根节点的二叉树，就能求出该树的高度

public static int height(TreeNode root){

if(root==null){

return 0;

}

return 1+ Math.max(height(root.left),height(root.right));

}

//求出以root为根节点的二叉树第k层的节点个数

public static int getKLevelNodes(TreeNode root,int k){

if(root==null || k<=0){

return 0;

}

if(k==1){

return 1;

}

return getKLevelNodes(root.left,k-1)+getKLevelNodes(root.right,k-1);

}

//判断当前以root为根节点的二叉树中是否包含指定元素val，

//若存在返回true，不存在返回false

public static boolean contains(TreeNode root,char value){

if(root==null){

return false;

}

if(root.val==value){

return true;

}

return contains(root.left,value) || contains(root.right,value);

}

public static void main(String[] args) {

TreeNode root=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引用结果如下：

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。