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

2021-06-30 10:48:44

文章目录

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

前言

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

一、结点结构


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;
    }


}

码农公寓