欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

程序员文章站 2023-12-14 15:56:34
本文实例讲述了java实现的二叉树常用操作。分享给大家供大家参考,具体如下: import java.util.arraydeque; import java....

本文实例讲述了java实现的二叉树常用操作。分享给大家供大家参考,具体如下:

import java.util.arraydeque;
import java.util.queue;
import java.util.stack;
//二叉树的建树,前中后 递归非递归遍历 层序遍历
//node节点
class node {
    int element;
    node left;
    node right;
    public node() {
    }
    public node(int element) {
        this.element = element;
    }
}
// binarytree
public class tree {
    // creat tree from array
    public static node creattree(int[] data, int i) {
        if (i >= data.length || data[i] == -1)
            return null;
        node temp = new node(data[i]);
        temp.left = creattree(data, i * 2 + 1);
        temp.right = creattree(data, i * 2 + 2);
        return temp;
    }
    // pre前序遍历递归
    public static void pre(node temp) {
        if (temp == null)
            return;
        system.out.print(temp.element + " ");
        pre(temp.left);
        pre(temp.right);
    }
    // mid中序遍历递归
    public static void mid(node temp) {
        if (temp == null)
            return;
        mid(temp.left);
        system.out.print(temp.element + " ");
        mid(temp.right);
    }
    // last后序遍历递归
    public static void last(node temp) {
        if (temp == null)
            return;
        last(temp.left);
        last(temp.right);
        system.out.print(temp.element + " ");
    }
    // pre1前序遍历非递归
    public static void pre1(node temp) {
        stack<node> stack = new stack<>();
        while (temp != null || !stack.isempty()) {
            while (temp != null) {
                stack.push(temp);
                system.out.print(temp.element + " ");
                temp = temp.left;
            }
            if (!stack.isempty()) {
                temp = stack.pop().right;
            }
        }
    }
    // mid1中序遍历非递归
    public static void mid1(node temp) {
        stack<node> stack = new stack<>();
        while (temp != null || !stack.isempty()) {
            while (temp != null) {
                stack.push(temp);
                temp = temp.left;
            }
            if (!stack.isempty()) {
                temp = stack.pop();
                system.out.print(temp.element + " ");
                temp = temp.right;
            }
        }
    }
    // last1后序遍历非递归
    public static void last1(node temp) {
        stack<node> stack = new stack<>();
        stack<node> stack2 = new stack<>();
        while (temp != null || !stack.isempty()) {
            while (temp != null) {
                stack.push(temp);
                stack2.push(temp);
                temp = temp.right;
            }
            if (!stack.isempty()) {
                temp = stack.pop().left;
            }
        }
        while (!stack2.isempty())
            system.out.print(stack2.pop().element + " ");
    }
    // ceng层序遍历
    public static void ceng(node temp) {
        if (temp == null)
            return;
        queue<node> queue = new arraydeque<>();
        queue.offer(temp);
        while (!queue.isempty()) {
            temp = queue.poll();
            system.out.print(temp.element + " ");
            if (temp.left != null)
                queue.offer(temp.left);
            if (temp.right != null)
                queue.offer(temp.right);
        }
    }
    // demo
    public static void main(string[] args) {
        int[] array = { 1, 2, 3, 4, 5, 6, 7, -1, -1, 10, -1, -1, 13 };
        node tree = creattree(array, 0);
        system.out.println("测试结果:");
        pre(tree);
        system.out.println();
        pre1(tree);
        system.out.println();
        mid(tree);
        system.out.println();
        mid1(tree);
        system.out.println();
        last(tree);
        system.out.println();
        last1(tree);
        system.out.println();
        ceng(tree);
    }
}

运行结果:

Java实现的二叉树常用操作【前序建树,前中后递归非递归遍历及层序遍历】

更多关于java算法相关内容感兴趣的读者可查看本站专题:《java数据结构与算法教程》、《java操作dom节点技巧总结》、《java文件与目录操作技巧汇总》和《java缓存操作技巧汇总

希望本文所述对大家java程序设计有所帮助。

上一篇:

下一篇: