JAVA二叉树的几种遍历(递归，非递归)实现
果冻爱吃小黄人 人气:0首先二叉树是树形结构的一种特殊类型，它符合树形结构的所有特点。本篇博客会针对二叉树来介绍一些树的基本概念，二叉树的基本操作（存储，返回树的深度，节点个数，每一层的节点个数），二叉树的四种遍历（层次，先序，中序，后序）
一.基本概念
二叉树有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
这些只是二叉树的一部分内容，希望可以帮助一些初学数据结构的亲，如果有错误的地方可以帮忙提出来的哦！！
加载全部内容