java二叉树的建立和递归遍历（java二叉树的建立和递归遍历有关系吗）

发布时间：2022-11-09

本文目录一览：

  1. 建立二叉树，并利用递归方法实现先序、中序、后序遍历。
  2. 用java怎么构造一个二叉树？
  3. java构建二叉树算法
  4. 用java怎么构造一个二叉树呢？
  5. 怎样使用java对二叉树进行层次遍历
  6. 二叉树的java实现与几种遍历

建立二叉树，并利用递归方法实现先序、中序、后序遍历。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
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);
    build(bt); // 建树
}
void preorder(tree bt) {
    if (bt) {
        cout << bt->data;
        preorder(bt->lchild);
        preorder(bt->rchild);
    }
}
void midorder(tree bt) {
    if (bt) {
        preorder(bt->lchild);
        cout << bt->data;
        preorder(bt->rchild);
    }
}
void backorder(tree bt) {
    if (bt) {
        preorder(bt->lchild);
        cout << bt->data;
        preorder(bt->rchild);
    }
}
void mainwork() {
    preorder(bt);
    cout << endl;
    midorder(bt);
    cout << endl;
    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) {
            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() {
        Stack<Node> stack = new Stack<>();
        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() {
        Stack<Node> stack = new Stack<>();
        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() {
        Stack<Node> stack = new Stack<>();
        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) {
        Queue<Node> queue = new LinkedBlockingQueue<>();
        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<T> {
    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 {
    public static void main(String[] args) {
        Tree tree = new Tree();
        tree.buildTree();
        System.out.println("中序遍历");
        tree.inOrderTraverse();
        tree.nrInOrderTraverse();
        System.out.println("后续遍历");
        tree.postOrderTraverse();
        tree.nrPostOrderTraverse();
        System.out.println("先序遍历");
        tree.preOrderTraverse();
        tree.nrPreOrderTraverse();
    }
}

java构建二叉树算法

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 (front < rear) {
            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 == null && right == 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 = leftHeight > rightHeight ? leftHeight : rightHeight;
        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 (leftLevel < 0 && rightLevel < 0) return -1;
        levelInTree = leftLevel > rightLevel ? 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 == null && right == null) {
            System.out.print(this + " ");
            data = null;
            return;
        }
        if (left != null) {
            left.defoliate();
            left = null;
        }
        System.out.print(this + " ");
        data = null;
        if (right != null) {
            right.defoliate();
            right = null;
        }
    }
    public static void main(String[] args) {
        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 (front < rear) {
            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 == null && right == 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 = leftHeight > rightHeight ? leftHeight : rightHeight;
        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 (leftLevel < 0 && rightLevel < 0) return -1;
        levelInTree = leftLevel > rightLevel ? 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 == null && right == null) {
            System.out.print(this + " ");
            data = null;
            return;
        }
        if (left != null) {
            left.defoliate();
            left = null;
        }
        System.out.print(this + " ");
        data = null;
        if (right != null) {
            right.defoliate();
            right = null;
        }
    }
    public static void main(String[] args) {
        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 (data > root.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);
            }
        }
    }
}

当建立好二叉树类后可以创建二叉树实例，并实现二叉树的先根遍历，中根遍历，后根遍历，代码如下：

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; i < array.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种表现形式。

二叉树的遍历分为三种：

  • 前序遍历：按照“根左右”，先遍历根节点，再遍历左子树，最后遍历右子树。
  • 中序遍历：按照“左根右”，先遍历左子树，再遍历根节点，最后遍历右子树。
  • 后序遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点。 其中前、后、中指的是每次遍历时候的根节点被遍历的顺序。 具体实现看下图：
推荐文章