Java数据结构---线索二叉树递归创建与遍历

本文主要是介绍Java数据结构---线索二叉树递归创建与遍历，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

文章目录

前言
一、结点结构
二、递归创建二叉树
三、线索化与遍历
四、使用方法
五、完整代码

前言

概念了解
如果已经直到线索二叉树的概念已经大致的实现思路那么久不需要看上面的文章了,直接看下面的代码以及使用方法即可

一、结点结构

class TNode {
    private int data;
    private String name;
    private TNode left;
    private TNode right;
    private int leftType;
    private int rightType;
    private TNode parent;

    public TNode getParent() {
        return parent;
    }

    public void setParent(TNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", name='" + name + '\'' +
                '}';
    }

    public TNode() {
    }

    public TNode(int data, String name) {
        this.data = data;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TNode getLeft() {
        return left;
    }

    public void setLeft(TNode left) {
        this.left = left;
    }

    public TNode getRight() {
        return right;
    }

    public void setRight(TNode right) {
        this.right = right;
    }


}

二、递归创建二叉树

这一部分使用递归创建的方法创建一个二叉树,之后该二叉树可以使用前序或者中序的方法线索化并且遍历.

    public void createTree(TNode node) {
        Scanner in = new Scanner(System.in);
        String str;
        System.out.println("输入name,按#退出");
        str = in.nextLine();
        if ("#".equals(str)) {
            node = null;
        } else {
            node.setData(1);
            node.setName(str);
            node.setLeft(new TNode());
            node.setRight(new TNode());
            createTree(node.getLeft());
            createTree(node.getRight());
        }
    }

三、线索化与遍历

  public void preThreadBinaryTree(TNode node) {//前序线索化二叉树
        if (node == null) {
            return;
        }
        //2:线索化当前节点
        if (node.getLeft() == null) {
            node.setLeftType(1);
            node.setLeft(pre);
        }
        if (pre != null && pre.getRight() == null && pre.getLeft() != node) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //1:先线索化左子树
        if (node.getLeftType() == 0) {
            preThreadBinaryTree(node.getLeft());
        }
        //3:线索化右子树
        preThreadBinaryTree(node.getRight());
    }

    public void preTraverseThreadTree() {
        TNode node = this.root;
        while (node != null) {
            System.out.println(node);
            while (node.getLeftType() == 0) {
                node = node.getLeft();
                System.out.println(node);
            }//退出时达到中序遍历第一个需要输出的节点

            if (node.getRightType() == 1) {
                node = node.getRight();
            } else if (node.getRight() == null) {
                //线索化前序遍历的最后一个结点的right一定为null,所以遍历完毕 退出循环
                break;
            }
        }
    }

  public void midThreadBinaryTree(TNode node) {//中续线索化二叉树
        if (node == null) {
            return;
        }
        //1:先线索化左子树
        midThreadBinaryTree(node.getLeft());
        //2:线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //3:线索化右子树
        midThreadBinaryTree(node.getRight());
    }

    public void midTraverseThreadTree() {//对中序线索二叉树进行遍历
        TNode node = root;
        while (node != null) {
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }//退出时达到中序遍历第一个需要输出的节点
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }

四、使用方法

输入 # 代表当前结点为空,默认是向左递归创建
例如第一次输入root之后会先创建root.left的结点,之后就是root.left.left
如果你输入了#那么就是root.right
在这里插入图片描述

在这里插入图片描述

五、完整代码

package algorithm.DataStruct.Tree;

import java.util.Scanner;

/**
 * @author: Serendipity
 * Date: 2022/2/4 18:53
 * Description:
 */
public class ThreadBinaryTree {
    public static void main(String[] args) {
        ThreadBiTree tree = new ThreadBiTree();
        tree.createTree(tree.getRoot());
        tree.midThreadBinaryTree();
        tree.midTraverseThreadTree();

    }
}

class ThreadBiTree {
    private TNode root = new TNode(1, "root");
    private TNode pre = null;

    public ThreadBiTree() {
    }

    public TNode getRoot() {
        return root;
    }

    public void setRoot(TNode root) {
        this.root = root;
    }

    public void createTree(TNode node) {
        Scanner in = new Scanner(System.in);
        String str;
        System.out.println("输入name,按#退出");
        str = in.nextLine();
        if ("#".equals(str)) {
            node = null;
        } else {
            node.setData(1);
            node.setName(str);
            node.setLeft(new TNode());
            node.setRight(new TNode());
            createTree(node.getLeft());
            createTree(node.getRight());
        }
    }

    public void midThreadBinaryTree() {
        midThreadBinaryTree(root);
    }

    public void preThreadBinaryTree() {
        preThreadBinaryTree(root);
    }

    public void postThreadBinaryTree() {
        postThreadBinaryTree(root);
    }

    public void preThreadBinaryTree(TNode node) {//前序线索化二叉树
        if (node == null) {
            return;
        }
        //2:线索化当前节点
        if (node.getLeft() == null) {
            node.setLeftType(1);
            node.setLeft(pre);
        }
        if (pre != null && pre.getRight() == null && pre.getLeft() != node) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //1:先线索化左子树
        if (node.getLeftType() == 0) {
            preThreadBinaryTree(node.getLeft());
        }
        //3:线索化右子树
        preThreadBinaryTree(node.getRight());
    }

    public void preTraverseThreadTree() {
        TNode node = this.root;
        while (node != null) {
            System.out.println(node);
            while (node.getLeftType() == 0) {
                node = node.getLeft();
                System.out.println(node);
            }//退出时达到中序遍历第一个需要输出的节点

            if (node.getRightType() == 1) {
                node = node.getRight();
            } else if (node.getRight() == null) {
                //线索化前序遍历的最后一个结点的right一定为null,所以遍历完毕 退出循环
                break;
            }
        }
    }

    public void midThreadBinaryTree(TNode node) {//中续线索化二叉树
        if (node == null) {
            return;
        }
        //1:先线索化左子树
        midThreadBinaryTree(node.getLeft());
        //2:线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //3:线索化右子树
        midThreadBinaryTree(node.getRight());
    }

    public void midTraverseThreadTree() {//对中序线索二叉树进行遍历
        TNode node = root;
        while (node != null) {
            while (node.getLeftType() == 0) {
                node = node.getLeft();
            }//退出时达到中序遍历第一个需要输出的节点
            System.out.println(node);
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }


    public void postThreadBinaryTree(TNode node) {//后续线索化二叉树
        if (node == null) {
            return;
        }
        //1:先线索化左子树
        postThreadBinaryTree(node.getLeft());
        //3:线索化右子树
        postThreadBinaryTree(node.getRight());
        //2:线索化当前节点
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }

    //与前中后续线索化二叉树遍历不同的是 后续线索化二叉树需要有一个双亲结点
    //不然由于遍历当前节点后无法回到双亲结点会导致死循环
    public void postTraverseThreadTree() {//对后续线索二叉树进行遍历
        //1、找后序遍历方式开始的节点
        TNode node = root;
        while (node != null && !(node.getLeftType() == 1)) {
            node = node.getLeft();
        }

        TNode preNode = null;
        while (node != null) {
            //右节点是线索
            if (node.getRightType() == 1) {
                System.out.print(node.getData() + ", ");
                preNode = node;
                node = node.getRight();

            } else {
                //如果上个处理的节点是当前节点的右节点
                if (node.getRight() == preNode) {
                    System.out.print(node.getData() + ", ");
                    if (node == root) {
                        return;
                    }

                    preNode = node;
                    node = node.getParent();

                } else {    //如果从左节点的进入则找到有子树的最左节点
                    node = node.getRight();
                    while (node != null && !(node.getLeftType() == 1)) {
                        node = node.getLeft();
                    }
                }
            }
        }

    }
}

class TNode {
    private int data;
    private String name;
    private TNode left;
    private TNode right;
    private int leftType;
    private int rightType;
    private TNode parent;

    public TNode getParent() {
        return parent;
    }

    public void setParent(TNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                ", name='" + name + '\'' +
                '}';
    }

    public TNode() {
    }

    public TNode(int data, String name) {
        this.data = data;
        this.name = name;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TNode getLeft() {
        return left;
    }

    public void setLeft(TNode left) {
        this.left = left;
    }

    public TNode getRight() {
        return right;
    }

    public void setRight(TNode right) {
        this.right = right;
    }


}

这篇关于Java数据结构---线索二叉树递归创建与遍历的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！

Java教程

Java数据结构---线索二叉树递归创建与遍历

文章目录

前言

一、结点结构

二、递归创建二叉树

三、线索化与遍历

四、使用方法

五、完整代码

前端开发

后端开发

移动端开发

数据库

服务器运维

人工智能

区块链

游戏开发

网站运营

大数据/云计算

软件工程

软件/开发工具使用

资讯