JAVA二叉树的几种遍历(递归,非递归)实现
程序员文章站
2022-06-22 10:01:09
首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点。本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先...
首先二叉树是树形结构的一种特殊类型,它符合树形结构的所有特点。本篇博客会针对二叉树来介绍一些树的基本概念,二叉树的基本操作(存储,返回树的深度,节点个数,每一层的节点个数),二叉树的四种遍历(层次,先序,中序,后序)
一.基本概念
二叉树有5种基本形态:
注:二叉树有序树,就是说一个节点的左右节点是有大小之分的,我们通常设定为左孩子一定大于右孩子,下面的实现都是基于这个规则的。二叉树分为三种:满二叉树,完全二叉树,不完全二叉树
二叉树的四种遍历:层次,先序,中序,后序首先是非递归实现上图的满二叉树:1.先序:根左右,用栈来实现,下面是它的流程图和入栈出栈的状态图(n是每个节点的值) 输出:12,10,9,11,15,14,16
2.中序:左根右,用栈来实现,中序的堆栈状态和先序一样,只是输出的位置不同,先序在入栈前输出,中序在出栈后输出 输出:9,10,11,12,14,15,16
3.后序:左右根,采用了两个栈 输出:9,11,10,14,16,15,12
下面是实现的代码:
//创建一个节点类 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实现Excel导入导出操作详解
下一篇: Nginx Rewrite