投稿
  1. 簡單一點首頁
  2. 編程

java二叉樹的建立和遞歸遍歷（java二叉樹的建立和遞歸遍歷有關係嗎）

簡單一點 • • 編程

本文目錄一覽：

建立二叉樹，並利用遞歸方法實現先序、中序、後序遍歷。

#include

#include

#include

#include

#include

using namespace std;

struct node;

typedef node *tree;

struct node{

char data;

tree lchild,rchild;

};

tree bt;

void build(tree bt){

char ch;

ch=getchar();

if(ch!=’.’){

bt=new node;

bt-data=ch;

build(bt-lchild);

build(bt-rchild);

}

else

bt=NULL;

}

void prework(){

ios::sync_with_stdio(false);

//freopen(“data.in”,”r”,stdin);

build(bt); //建樹

}

void preorder(tree bt){

if(bt){

coutdata;

preorder(bt-lchild);

preorder(bt-rchild);

}

}

void midorder(tree bt){

if(bt){

preorder(bt-lchild);

coutdata;

preorder(bt-rchild);

}

}

void backorder(tree bt){

if(bt){

preorder(bt-lchild);

coutdata;

preorder(bt-rchild);

}

}

void mainwork(){

preorder(bt);

coutendl;

midorder(bt);

coutendl;

backorder(bt);

}

int main(){

prework();

mainwork();

return 0;

}

//我這裡輸入的東西是要求葉子節點的子節點為’.’

但仍無鈴聲，則送維修店維修。三無受話現象：

用java怎麼構造一個二叉樹？

二叉樹的相關操作，包括創建，中序、先序、後序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和後序非遞歸遍歷的的實現。

package com.algorithm.tree;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Queue;

import java.util.Scanner;

import java.util.Stack;

import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {

}

public Tree(Node root) {

this.root = root;

}

//創建二叉樹

public void buildTree() {

Scanner scn = null;

try {

scn = new Scanner(new File(“input.txt”));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

root = createTree(root,scn);

}

//先序遍歷創建二叉樹

private Node createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals(“#”)) {

return null;

} else {

node = new Node((T)temp);

node.setLeft(createTree(node.getLeft(), scn));

node.setRight(createTree(node.getRight(), scn));

return node;

}

}

//中序遍歷(遞歸)

public void inOrderTraverse() {

inOrderTraverse(root);

}

public void inOrderTraverse(Node node) {

if (node != null) {

inOrderTraverse(node.getLeft());

System.out.println(node.getValue());

inOrderTraverse(node.getRight());

}

}

//中序遍歷(非遞歸)

public void nrInOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

System.out.println(node.getValue());

node = node.getRight();

}

}

//先序遍歷(遞歸)

public void preOrderTraverse() {

preOrderTraverse(root);

}

public void preOrderTraverse(Node node) {

if (node != null) {

System.out.println(node.getValue());

preOrderTraverse(node.getLeft());

preOrderTraverse(node.getRight());

}

}

//先序遍歷（非遞歸）

public void nrPreOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

System.out.println(node.getValue());

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

node = node.getRight();

}

}

//後序遍歷(遞歸)

public void postOrderTraverse() {

postOrderTraverse(root);

}

public void postOrderTraverse(Node node) {

if (node != null) {

postOrderTraverse(node.getLeft());

postOrderTraverse(node.getRight());

System.out.println(node.getValue());

}

}

//後續遍歷(非遞歸)

public void nrPostOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

Node preNode = null;//表示最近一次訪問的節點

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {

System.out.println(node.getValue());

node = stack.pop();

preNode = node;

node = null;

} else {

node = node.getRight();

}

}

}

//按層次遍歷

public void levelTraverse() {

levelTraverse(root);

}

public void levelTraverse(Node node) {

QueueNode queue = new LinkedBlockingQueueNode();

queue.add(node);

while (!queue.isEmpty()) {

Node temp = queue.poll();

if (temp != null) {

System.out.println(temp.getValue());

queue.add(temp.getLeft());

queue.add(temp.getRight());

}

}

}

}

//樹的節點

class Node {

private Node left;

private Node right;

private T value;

public Node() {

}

public Node(Node left,Node right,T value) {

this.left = left;

this.right = right;

this.value = value;

}

public Node(T value) {

this(null,null,value);

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public T getValue() {

return value;

}

public void setValue(T value) {

this.value = value;

}

}

測試代碼：

package com.algorithm.tree;

public class TreeTest {

/**

* @param args

*/

public static void main(String[] args) {

Tree tree = new Tree();

tree.buildTree();

System.out.println(“中序遍歷”);

tree.inOrderTraverse();

tree.nrInOrderTraverse();

System.out.println(“後續遍歷”);

//tree.nrPostOrderTraverse();

tree.postOrderTraverse();

tree.nrPostOrderTraverse();

System.out.println(“先序遍歷”);

tree.preOrderTraverse();

tree.nrPreOrderTraverse();

//

}

}

java構建二叉樹演算法

//******************************************************************************************************//

//*****本程序包括簡單的二叉樹類的實現和前序,中序,後序,層次遍歷二叉樹演算法,*******//

//******以及確定二叉樹的高度,制定對象在樹中的所處層次以及將樹中的左右***********//

//******孩子節點對換位置,返回葉子節點個數刪除葉子節點,並輸出所刪除的葉子節點**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //數據元數

private BinTree left,right; //指向左,右孩子結點的鏈

BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點

int front;//層次遍歷時隊首

int rear;//層次遍歷時隊尾

public BinTree()

{

}

public BinTree(Object data)

{ //構造有值結點

this.data = data;

left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //構造有值結點

this.data = data;

this.left = left;

this.right = right;

}

public String toString()

{

return data.toString();

}//前序遍歷二叉樹

public static void preOrder(BinTree parent){

if(parent == null)

return;

System.out.print(parent.data+” “);

preOrder(parent.left);

preOrder(parent.right);

}//中序遍歷二叉樹

public void inOrder(BinTree parent){

if(parent == null)

return;

inOrder(parent.left);

System.out.print(parent.data+” “);

inOrder(parent.right);

}//後序遍歷二叉樹

public void postOrder(BinTree parent){

if(parent == null)

return;

postOrder(parent.left);

postOrder(parent.right);

System.out.print(parent.data+” “);

}// 層次遍歷二叉樹

public void LayerOrder(BinTree parent)

{

elements[0]=parent;

front=0;rear=1;

while(frontrear)

{

try

{

if(elements[front].data!=null)

{

System.out.print(elements[front].data + ” “);

if(elements[front].left!=null)

elements[rear++]=elements[front].left;

if(elements[front].right!=null)

elements[rear++]=elements[front].right;

front++;

}

}catch(Exception e){break;}

}

}//返回樹的葉節點個數

public int leaves()

{

if(this == null)

return 0;

if(left == nullright == null)

return 1;

return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}//結果返回樹的高度

public int height()

{

int heightOfTree;

if(this == null)

return -1;

int leftHeight = (left == null ? 0 : left.height());

int rightHeight = (right == null ? 0 : right.height());

heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

return 1 + heightOfTree;

}

//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層

public int level(Object object)

{

int levelInTree;

if(this == null)

return -1;

if(object == data)

return 1;//規定根節點為第一層

int leftLevel = (left == null?-1:left.level(object));

int rightLevel = (right == null?-1:right.level(object));

if(leftLevel0rightLevel0)

return -1;

levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

return 1+levelInTree;

}

//將樹中的每個節點的孩子對換位置

public void reflect()

{

if(this == null)

return;

if(left != null)

left.reflect();

if(right != null)

right.reflect();

BinTree temp = left;

left = right;

right = temp;

}// 將樹中的所有節點移走,並輸出移走的節點

public void defoliate()

{

String innerNode = “”;

if(this == null)

return;

//若本節點是葉節點，則將其移走

if(left==nullright == null)

{

System.out.print(this + ” “);

data = null;

return;

}

//移走左子樹若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本節點，放在中間表示中跟移走…

innerNode += this + ” “;

data = null;

//移走右子樹若其存在

if(right!=null){

right.defoliate();

right = null;

}

}

/**

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

BinTree e = new BinTree(“E”);

BinTree g = new BinTree(“G”);

BinTree h = new BinTree(“H”);

BinTree i = new BinTree(“I”);

BinTree d = new BinTree(“D”,null,g);

BinTree f = new BinTree(“F”,h,i);

BinTree b = new BinTree(“B”,d,e);

BinTree c = new BinTree(“C”,f,null);

BinTree tree = new BinTree(“A”,b,c);

System.out.println(“前序遍歷二叉樹結果: “);

tree.preOrder(tree);

System.out.println();

System.out.println(“中序遍歷二叉樹結果: “);

tree.inOrder(tree);

System.out.println();

System.out.println(“後序遍歷二叉樹結果: “);

tree.postOrder(tree);

System.out.println();

System.out.println(“層次遍歷二叉樹結果: “);

tree.LayerOrder(tree);

System.out.println();

System.out.println(“F所在的層次: “+tree.level(“F”));

System.out.println(“這棵二叉樹的高度: “+tree.height());

System.out.println(“————————————–“);

tree.reflect();

System.out.println(“交換每個節點的孩子節點後……”);

System.out.println(“前序遍歷二叉樹結果: “);

tree.preOrder(tree);

System.out.println();

System.out.println(“中序遍歷二叉樹結果: “);

tree.inOrder(tree);

System.out.println();

System.out.println(“後序遍歷二叉樹結果: “);

tree.postOrder(tree);

System.out.println();

System.out.println(“層次遍歷二叉樹結果: “);

tree.LayerOrder(tree);

System.out.println();

System.out.println(“F所在的層次: “+tree.level(“F”));

System.out.println(“這棵二叉樹的高度: “+tree.height());

}

用java怎麼構造一個二叉樹呢？

java構造二叉樹，可以通過鏈表來構造，如下代碼：

public class BinTree {

public final static int MAX=40;

BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點

    int front;//層次遍歷時隊首

    int rear;//層次遍歷時隊尾

private Object data; //數據元數

private BinTree left,right; //指向左,右孩子結點的鏈

public BinTree()

{

}

public BinTree(Object data)

{ //構造有值結點

   this.data = data;

   left = right = null;

}

public BinTree(Object data,BinTree left,BinTree right)

{ //構造有值結點

   this.data = data;

   this.left = left;

   this.right = right;

}

public String toString()

{

   return data.toString();

}

//前序遍歷二叉樹

public static void preOrder(BinTree parent){ 

     if(parent == null)

      return;

     System.out.print(parent.data+” “);

     preOrder(parent.left);

     preOrder(parent.right);

}

//中序遍歷二叉樹

public void inOrder(BinTree parent){

   if(parent == null)

      return;

   inOrder(parent.left);

   System.out.print(parent.data+” “);

     inOrder(parent.right);

}

//後序遍歷二叉樹

public void postOrder(BinTree parent){

   if(parent == null)

    return;

   postOrder(parent.left);

   postOrder(parent.right);

   System.out.print(parent.data+” “);

}

// 層次遍歷二叉樹 

public void LayerOrder(BinTree parent)

{ 

     elements[0]=parent;

     front=0;rear=1;

   while(frontrear)

   {

    try

    {

        if(elements[front].data!=null)

        {

           System.out.print(elements[front].data + ” “);

           if(elements[front].left!=null)

          elements[rear++]=elements[front].left;

           if(elements[front].right!=null)

          elements[rear++]=elements[front].right;

           front++;

        }

    }catch(Exception e){break;}

   }

}

//返回樹的葉節點個數

public int leaves()

{

   if(this == null)

    return 0;

   if(left == nullright == null)

    return 1;

   return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());

}

//結果返回樹的高度

public int height()

{

   int heightOfTree;

   if(this == null)

    return -1;

   int leftHeight = (left == null ? 0 : left.height());

   int rightHeight = (right == null ? 0 : right.height());

   heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;

   return 1 + heightOfTree;

}

//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層

public int level(Object object)

{

   int levelInTree;

   if(this == null)

    return -1;

   if(object == data)

    return 1;//規定根節點為第一層

   int leftLevel = (left == null?-1:left.level(object));

   int rightLevel = (right == null?-1:right.level(object));

   if(leftLevel0rightLevel0)

    return -1;

   levelInTree = leftLevelrightLevel?rightLevel:leftLevel;

   return 1+levelInTree;

  

}

//將樹中的每個節點的孩子對換位置

public void reflect()

{

   if(this == null)

    return;

   if(left != null)

    left.reflect();

   if(right != null)

    right.reflect();

   BinTree temp = left;

   left = right;

   right = temp;

}

// 將樹中的所有節點移走,並輸出移走的節點

public void defoliate()

{

   if(this == null)

    return;

   //若本節點是葉節點，則將其移走

   if(left==nullright == null)

   {

    System.out.print(this + ” “);

    data = null;

    return;

   }

   //移走左子樹若其存在

   if(left!=null){

    left.defoliate();

    left = null;

   }

   //移走本節點，放在中間表示中跟移走…

   String innerNode += this + ” “;

   data = null;

   //移走右子樹若其存在

   if(right!=null){

    right.defoliate();

    right = null;

   }

}

   /**

* @param args

*/

public static void main(String[] args) {

   // TODO Auto-generated method stub

   BinTree e = new BinTree(“E”);

   BinTree g = new BinTree(“G”);

   BinTree h = new BinTree(“H”);

   BinTree i = new BinTree(“I”);

   BinTree d = new BinTree(“D”,null,g);

  

   BinTree f = new BinTree(“F”,h,i);

   BinTree b = new BinTree(“B”,d,e);

   BinTree c = new BinTree(“C”,f,null);

   BinTree tree = new BinTree(“A”,b,c);

  

        System.out.println(“前序遍歷二叉樹結果: “);

        tree.preOrder(tree);

        System.out.println();

        System.out.println(“中序遍歷二叉樹結果: “);

        tree.inOrder(tree);

        System.out.println();

        System.out.println(“後序遍歷二叉樹結果: “);

        tree.postOrder(tree);

        System.out.println();

      System.out.println(“層次遍歷二叉樹結果: “);

     tree.LayerOrder(tree);

     System.out.println();

        System.out.println(“F所在的層次: “+tree.level(“F”));

        System.out.println(“這棵二叉樹的高度: “+tree.height());

         System.out.println(“————————————–“);

         tree.reflect();

          System.out.println(“交換每個節點的孩子節點後……”);

          System.out.println(“前序遍歷二叉樹結果: “);

        tree.preOrder(tree);

        System.out.println();

        System.out.println(“中序遍歷二叉樹結果: “);

        tree.inOrder(tree);

        System.out.println();

        System.out.println(“後序遍歷二叉樹結果: “);

        tree.postOrder(tree);

        System.out.println();

      System.out.println(“層次遍歷二叉樹結果: “);

     tree.LayerOrder(tree);

     System.out.println();

        System.out.println(“F所在的層次: “+tree.level(“F”));

        System.out.println(“這棵二叉樹的高度: “+tree.height());

}

怎樣使用java對二叉樹進行層次遍歷

public class BinaryTree {

 

 int data;      //根節點數據

 BinaryTree left;    //左子樹

 BinaryTree right;   //右子樹

 

 public BinaryTree(int data)    //實例化二叉樹類

 {

  this.data = data;

  left = null;

  right = null;

 }

 

 public void insert(BinaryTree root,int data){     //向二叉樹中插入子節點

  if(dataroot.data)                               //二叉樹的左節點都比根節點小

  {

   if(root.right==null){

    root.right = new BinaryTree(data);

   }else{

    this.insert(root.right, data);

   }

  }else{                                          //二叉樹的右節點都比根節點大

   if(root.left==null){

    root.left = new BinaryTree(data);

   }else{

    this.insert(root.left, data);

   }

  }

 }

}

當建立好二叉樹類後可以創建二叉樹實例，並實現二叉樹的先根遍歷，中根遍歷，後根遍歷，代碼如下：

package package2;

public class BinaryTreePreorder {

 

 public static void preOrder(BinaryTree root){  //先根遍歷

  if(root!=null){

   System.out.print(root.data+”-“);

   preOrder(root.left);

   preOrder(root.right);

  }

 }

 

 public static void inOrder(BinaryTree root){     //中根遍歷

  if(root!=null){

   inOrder(root.left);

   System.out.print(root.data+”–“);

   inOrder(root.right);

  }

 }

 

 public static void postOrder(BinaryTree root){    //後根遍歷

  if(root!=null){

   postOrder(root.left);

   postOrder(root.right);

   System.out.print(root.data+”—“);

  }

 }

 

 public static void main(String[] str){

  int[] array = {12,76,35,22,16,48,90,46,9,40};

  BinaryTree root = new BinaryTree(array[0]);   //創建二叉樹

  for(int i=1;iarray.length;i++){

   root.insert(root, array[i]);       //向二叉樹中插入數據

  }

  System.out.println(“先根遍歷：”);

  preOrder(root);

  System.out.println();

  System.out.println(“中根遍歷：”);

  inOrder(root);

  System.out.println();

  System.out.println(“後根遍歷：”);

  postOrder(root);

二叉樹的java實現與幾種遍歷

二叉樹的定義

二叉樹(binary tree)是結點的有限集合，這個集合或者空，或者由一個根及兩個互不相交的稱為這個根的左子樹或右子樹構成.

從定義可以看出，二叉樹包括：1.空樹 2.只有一個根節點 3.只有左子樹   4.只有右子樹  5.左右子樹都存在    有且僅有這5種表現形式

二叉樹的遍歷分為三種：前序遍歷 中序遍歷 後序遍歷

前序遍歷：按照「根左右」,先遍歷根節點，再遍歷左子樹 ，再遍歷右子樹

中序遍歷：按照「左根右「,先遍歷左子樹，再遍歷根節點，最後遍歷右子樹

後續遍歷：按照「左右根」，先遍歷左子樹，再遍歷右子樹，最後遍歷根節點

其中前，後，中指的是每次遍歷時候的根節點被遍歷的順序

具體實現看下圖：

原創文章，作者：簡單一點，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/128905.html

贊 (0)
打賞 微信掃一掃 微信掃一掃 支付寶掃一掃 支付寶掃一掃
簡單一點的頭像簡單一點
0 0
上一篇 2024-10-03 23:25
下一篇 2024-10-03 23:25

相關推薦

  • Python遍歷集合中的元素

    本文將從多個方面詳細闡述Python遍歷集合中的元素方法。 一、for循環遍歷集合 Python中，使用for循環可以遍歷集合中的每個元素，代碼如下： my_set = {1, 2…

    RTWSY的頭像 RTWSY
    編程 2025-04-29

  • Python如何遍歷字典中的key和value

    本文將詳細講解Python中如何遍歷字典中的key和value，包括多種遍歷方式以及在遍歷過程中的一些應用場景。 一、遍歷字典中的key和value 在Python中，字典是一種無…

    EFCIZ的頭像 EFCIZ
    編程 2025-04-29

  • 台階走法遞歸

    台階走法遞歸是一個經典的遞歸問題，在計算機演算法中有著廣泛的應用。本篇文章將從遞歸的思想出發，詳細分析如何解決這個問題。 一、遞歸基礎知識 遞歸是指一個函數直接或間接地調用自身。遞歸…

    AQZSG的頭像 AQZSG
    編程 2025-04-29

  • MySQL遞歸函數的用法

    本文將從多個方面對MySQL遞歸函數的用法做詳細的闡述，包括函數的定義、使用方法、示例及注意事項。 一、遞歸函數的定義 遞歸函數是指在函數內部調用自身的函數。MySQL提供了CRE…

    CQFQV的頭像 CQFQV
    編程 2025-04-29

  • Python遞歸累加求和

    Python遞歸累加求和是一種常見的遞歸演算法，在解決一些數學問題或者邏輯問題時常常被使用。下面我們將從多個方面來詳細闡述這個演算法。 一、基本概念 遞歸是一種在函數中調用自身的演算法，…

    YWXFX的頭像 YWXFX
    編程 2025-04-28

  • 使用PHP foreach遍歷有相同屬性的值

    本篇文章將介紹如何使用PHP foreach遍歷具有相同屬性的值，並給出相應的代碼示例。 一、基礎概念 在講解如何使用PHP foreach遍歷有相同屬性的值之前，我們需要先了解幾…

    ATMUX的頭像 ATMUX
    編程 2025-04-28

  • 依賴關係代碼的用法介紹

    依賴關係代碼在軟體開發中扮演著至關重要的角色。它們指定了項目中各個模塊之間的依賴關係。本文將從多個方面對依賴關係代碼進行詳細的闡述。 一、依賴關係代碼的作用 依賴關係代碼可以幫助開…

    FTXLC的頭像 FTXLC
    編程 2025-04-28

  • 用遞歸方法反轉一個字元串python

    本文將從以下幾個方面對用遞歸方法反轉一個字元串python做詳細的闡述，包括：遞歸的基本原理和過程、遞歸反轉字元串的實現方法、時間與空間複雜度分析等。 一、遞歸的基本原理和過程 遞…

    KCQQB的頭像 KCQQB
    編程 2025-04-28

  • 二叉樹非遞歸先序遍歷c語言

    本文將為您詳細介紹二叉樹的非遞歸先序遍歷演算法，同時提供完整的C語言代碼示例。通過本文，您將了解到二叉樹的先序遍歷演算法，以及非遞歸實現的方式。 一、二叉樹的先序遍歷演算法介紹 在介紹二…

    VLYRD的頭像 VLYRD
    編程 2025-04-28

  • Python如何遍歷列表

    在Python編程中，列表是一種常用的數據類型，它允許我們存儲多個值。但是，我們如何遍歷列表並對其中的每個值進行操作呢？ 一、for循環遍歷列表 fruits = [‘apple’…

    UZNJM的頭像 UZNJM
    編程 2025-04-28

發表回復

登錄後才能評論