欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

JAVA二叉树的几种遍历(递归,非递归)实现

程序员文章站 2022-06-22 10:01:09
首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点。本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先...

首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点。本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序)

一.基本概念

二叉树有5种基本形态:

JAVA二叉树的几种遍历(递归,非递归)实现

注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的。二叉树分为三种:满二叉树,完全二叉树,不完全二叉树

JAVA二叉树的几种遍历(递归,非递归)实现

二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉树:1.先序:根左右,用栈来实现,下面是它的流程图和入栈出栈的状态图(n是每个节点的值) 输出:12,10,9,11,15,14,16

JAVA二叉树的几种遍历(递归,非递归)实现
JAVA二叉树的几种遍历(递归,非递归)实现

2.中序:左根右,用栈来实现,中序的堆栈状态和先序一样,只是输出的位置不同,先序在入栈前输出,中序在出栈后输出 输出:9,10,11,12,14,15,16

JAVA二叉树的几种遍历(递归,非递归)实现

3.后序:左右根,采用了两个栈 输出:9,11,10,14,16,15,12

JAVA二叉树的几种遍历(递归,非递归)实现

JAVA二叉树的几种遍历(递归,非递归)实现

下面是实现的代码:

//创建一个节点类
 class node {
  public int key;//节点的值
  public string data;//节点存储的内容
  public node leftnode;//左孩子
  public node rightnode;//右孩子

  //节点类的构造方法
  public node(int key,string data){
    this.key=key;
    this.data=data;
    this.leftnode=null;
    this.rightnode=null;
  }

  //得到数据
  public int getkey(){
    return key;

}

}
public class binarytree {
  public node root;
  public int h=0;

  //插入数据
  public void insert(int key,string data){
    //实例化一个节点
    node newnode=new node(key, data);
    //判断此二叉树是否有根节点
    if(root==null){
      root=newnode;

    }
    else
    {
      node current=root;
      node parent;
      while(true){
        parent=current;
        //判断大小,决定新节点是放在左边还是右边
        if(key<current.key){
          current=current.leftnode;//往左子树方向找
          if(current==null){
            parent.leftnode=newnode;//找到叶子节点
            return;
          }//叶子节点的if end;
        }//左子树的if end;
        else{
          current=current.rightnode;
          if(current==null){
            parent.rightnode=newnode;
            return;
          }//叶子
        }//右子树

      }
    }
  }//insert end;

//打印
  public void printltree(node node){
    system.out.print("*");

    system.out.print(node.getkey());


  }




  //深度
  public int height(node node){
    if(node==null){
      return 0;
    }
    else{
      int i=height(node.leftnode);
      int j=height(node.rightnode);
      return (i>j)?(i+1):(j+1);

    }
  }

  //节点个数
  public int nodenum(node node){
    if(node==null){
      return 0;
    }
    return nodenum(node.leftnode)+nodenum(node.rightnode)+1;

  }

  //第k层节点的个数
  public int getleafnodenum(node node,int i){
    if(node==null){
      return 0;
    }
    else{
      if(i==0){
        return 1;
      }
      else{
        int numleft=getleafnodenum(node.leftnode,i-1);
        int numright=getleafnodenum(node.rightnode,i-1);
        return (numleft+numright);
      }
    }
    }



  //分层遍历
  public void levelorder(node node){
    queue<node> queue=new linkedlist<node>();
    if(node==null){
      return;
    }
    queue.add(node);
    while(!queue.isempty()){
      node temp=queue.poll();
      system.out.print("*");
      system.out.print(temp.getkey());
      if(temp.leftnode!=null){
        queue.add(temp.leftnode);
      }
      if(temp.rightnode!=null){
        queue.add(temp.rightnode);
      }
    }
  }

  //递归前序遍历
  public void preorder(node node){
    if(node!=null){
    printltree(node);
    preorder(node.leftnode);
    preorder(node.rightnode);
  }
  }
  //非递归前序遍历
  public void npreorder(node node){

    stack<node> sk=new stack<node>();
    node n=node;
    while(!sk.isempty()||n!=null){
      if(n!=null){
      system.out.print("<<<");
      system.out.print(n.getkey());

      sk.push(n);
      n=n.leftnode;
      }

      else{
      n=sk.pop();;
      n=n.rightnode;
    }
  }
  }


  //中序遍历
    public void inorder(node node){
      if(node!=null){
      preorder(node.leftnode);
      printltree(node);

      preorder(node.rightnode);
    }
    }

    //非递归的中序遍历
    public void ninorder(node node){
      stack<node> s=new stack<node>();
      node n=node;
      while(n!=null||!s.isempty()){
        if(n!=null){
          s.push(n);
          n=n.leftnode;
        }
        else{
          n=s.pop();
          system.out.println(n.getkey());
          n=n.rightnode;

        }
      }
    }

    //后序遍历
        public void postorder(node node){
          if(node!=null){
          preorder(node.leftnode);

          preorder(node.rightnode);
          printltree(node);

        }
        }

        //非递归后序遍历
        public void npostorder(node node){
          stack<node> s1=new stack<node>();//第一次入栈
          stack<node> s2=new stack<node>();//第二次入栈
          node n=node;
        while(!s1.isempty()||n!=null){
          if(n!=null){
            s1.push(n);
            s2.push(n);
            n=n.rightnode;
          }
          else{
            n=s1.pop();
            n=n.leftnode;
          }
        }
        while(!s2.isempty()){
          system.out.println("((("+s2.pop().getkey());
        }

        }

public static void main(string[] args) {

    binarytree bt=new binarytree();
    bt.insert(12, "a");
    bt.insert(10, "b");
    bt.insert(15, "c");
    bt.insert(9, "d");
    bt.insert(11, "e");
    bt.insert(14, "f");
    bt.insert(16, "g");

   system.out.println("这个二叉树的深度:"+bt.height(bt.root));
    system.out.println("这个二叉树的节点个数:"+bt.nodenum(bt.root));


    system.out.println("前序遍历:");
    bt.preorder(bt.root);
    system.out.println();

    system.out.println("非递归前序遍历:");
    bt.npreorder(bt.root);
    system.out.println();

    system.out.println("中序遍历:");
    bt.inorder(bt.root);
    system.out.println();

    system.out.println("非递归中序遍历:");
    bt.ninorder(bt.root);
    system.out.println();

    system.out.println("后序遍历:");
    bt.postorder(bt.root);
    system.out.println();

    system.out.println("非递归后序遍历:");
    bt.npostorder(bt.root);
    system.out.println();

    system.out.println("分层遍历:");
    bt.levelorder(bt.root);
    system.out.println();

    system.out.println("第二层有"+bt.getleafnodenum(bt.root, 2));

  }
    }

代码亲测可以运行(^-^)v

这些只是二叉树的一部分内容,希望可以帮助一些初学数据结构的亲,如果有错误的地方可以帮忙提出来的哦!!

相关标签: JAVA二叉树