JAVA二叉樹的幾種遍歷(遞歸，非遞歸)實現(xiàn)
更新時間：2020年12月04日 18:53:11 作者：果凍愛吃小黃人
這篇文章主要介紹了JAVA二叉樹的幾種遍歷(遞歸，非遞歸)實現(xiàn),需要的朋友可以參考下
首先二叉樹是樹形結構的一種特殊類型，它符合樹形結構的所有特點。本篇博客會針對二叉樹來介紹一些樹的基本概念，二叉樹的基本操作（存儲，返回樹的深度，節(jié)點個數(shù)，每一層的節(jié)點個數(shù)），二叉樹的四種遍歷（層次，先序，中序，后序）
一.基本概念
二叉樹有5種基本形態(tài)：
注：二叉樹有序樹，就是說一個節(jié)點的左右節(jié)點是有大小之分的，我們通常設定為左孩子一定大于右孩子，下面的實現(xiàn)都是基于這個規(guī)則的。二叉樹分為三種：滿二叉樹，完全二叉樹，不完全二叉樹
二叉樹的四種遍歷：層次，先序，中序，后序首先是非遞歸實現(xiàn)上圖的滿二叉樹：1.先序：根左右，用棧來實現(xiàn)，下面是它的流程圖和入棧出棧的狀態(tài)圖（n是每個節(jié)點的值） 輸出：12，10，9，11，15，14，16
2.中序：左根右，用棧來實現(xiàn)，中序的堆棧狀態(tài)和先序一樣，只是輸出的位置不同，先序在入棧前輸出，中序在出棧后輸出 輸出：9，10，11，12，14，15，16
3.后序：左右根，采用了兩個棧 輸出：9，11，10，14，16，15，12
下面是實現(xiàn)的代碼：
//創(chuàng)建一個節(jié)點類
class Node {
public int key;//節(jié)點的值
public String Data;//節(jié)點存儲的內(nèi)容
public Node leftNode;//左孩子
public Node rightNode;//右孩子
//節(jié)點類的構造方法
public Node(int key,String Data){
this.key=key;
this.Data=Data;
this.leftNode=null;
this.rightNode=null;
}
//得到數(shù)據(jù)
public int getKey(){
return key;
}
}
public class BinaryTree {
public Node root;
public int h=0;
//插入數(shù)據(jù)
public void insert(int key,String Data){
//實例化一個節(jié)點
Node newNode=new Node(key, Data);
//判斷此二叉樹是否有根節(jié)點
if(root==null){
root=newNode;
}
else
{
Node current=root;
Node parent;
while(true){
parent=current;
//判斷大小，決定新節(jié)點是放在左邊還是右邊
if(key<current.key){
current=current.leftNode;//往左子樹方向找
if(current==null){
parent.leftNode=newNode;//找到葉子節(jié)點
return;
}//葉子節(jié)點的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);
}
}
//節(jié)點個數(shù)
public int NodeNum(Node node){
if(node==null){
return 0;
}
return NodeNum(node.leftNode)+NodeNum(node.rightNode)+1;
}
//第K層節(jié)點的個數(shù)
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("這個二叉樹的節(jié)點個數(shù)："+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
這些只是二叉樹的一部分內(nèi)容，希望可以幫助一些初學數(shù)據(jù)結構的親，如果有錯誤的地方可以幫忙提出來的哦?。?/p>
相關文章
MyBatisPlus標準數(shù)據(jù)層CRUD的使用詳解
這篇文章主要介紹了MyBatisPlus標準數(shù)據(jù)層CRUD的使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-07-07
下面小編就為大家?guī)硪黄P于Spring總結(必看篇)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-08-08
SpringBoot?@Transactional事務不生效排查方式
這篇文章主要介紹了SpringBoot?@Transactional事務不生效排查方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
這篇文章主要介紹了解讀Spring-boot的debug調(diào)試，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-12-12
這篇文章主要介紹了SpringBoot自定義Starter及使用,Starter是Spring Boot中的一個非常重要的概念，Starter相當于模塊，它能將模塊所需的依賴整合起來并對模塊內(nèi)的Bean根據(jù)環(huán)境進行自動配置,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了spring boot配置ssl(多cer格式)超詳細教程,本文通過圖文并茂的形式給大家介紹的非常詳細,對大家的學習或工作具有一定的參考借鑒價值,需要的朋友參考下吧2023-11-11
這篇文章主要介紹了Java 遍歷list和map的方法，幫助大家更好的理解和使用Java，感興趣的朋友可以了解下2020-12-12
Java中的BlockingQueue阻塞隊列原理以及實現(xiàn)詳解
這篇文章主要介紹了Java中的BlockingQueue阻塞隊列原理以及實現(xiàn)詳解,在最常見的使用到這個阻塞隊列的地方,就是我們耳熟能詳?shù)木€程池里面了,作為我們線程池的一大最大參與者,也是AQS的一個具體實現(xiàn),需要的朋友可以參考下2023-12-12
本文主要介紹了SpringBoot封裝JDBC的實現(xiàn)步驟，文中通過示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
這篇文章主要介紹了Java中常用的6種排序算法詳細分解,著重說明每個算法的計算過程分解,是探究實現(xiàn)原理級的文章,對于深入理解這些算法有很大幫助,需要的朋友可以參考下2014-07-07