Java 데이터 구조에서 스레드 이진 트리를 구현하는 방법은 무엇입니까?

1. 단서 이진 트리 소개

열 {1, 3, 6, 8, 10, 14}을 이진 트리로 구성합니다.

문제 분석:

1. 트리 순회 중 배열은 {8, 3, 10, 1, 6, 14}

2입니다. 그러나 노드 6, 8, 10, 14의 왼쪽 및 오른쪽 포인터는 완전히 활용되지 않습니다.

3. 각 노드가 자신의 이전 노드와 다음 노드를 가리킬 수 있도록 각 노드의 왼쪽 및 오른쪽 포인터를 최대한 활용하려면 어떻게 해야 할까요?

4. 솔루션 - 단서 이진 트리

개념: 이진 트리의 저장 구조인 이진 연결 리스트는 노드의 왼쪽 및 오른쪽 자식을 찾는 것이 쉽지만 일반적으로 특정 순회 시퀀스에서 노드의 선행 노드와 후속 노드를 직접 찾는 것은 불가능합니다. . 따라서 스레딩을 사용하며 이진 트리 구조 연결리스트의 널 포인터 필드를 스레딩에 사용합니다.

2. 스레드 이진 트리의 기본 특성

n 노드의 이진 연결 목록에는 n+1 [공식 2n-(n-1)=n+1] 널 포인터 필드가 포함됩니다. 바이너리 연결 리스트의 널 포인터 필드를 사용하여 특정 순회 순서에 따라 노드의 선행 노드와 후속 노드에 대한 포인터를 저장합니다(이러한 추가 포인터를 "단서"라고 합니다)

이러한 추가 단서가 바이너리 연결 리스트라고 합니다. 스레드 연결 리스트이며, 이에 대응하는 이진 트리를 스레드 이진 트리(Threaded BinaryTree)라고 합니다. 단서의 다른 성격에 따라 단서 이진 트리는 선순 단서 이진 트리, 순순 단서 이진 트리, 후순 단서 이진 트리의 세 가지 유형으로 나눌 수 있습니다

3.

순차 단서 이진 트리 및 순회

적용 사례 설명: 다음 이진 트리를 순차 단서 이진 트리로 변환합니다. 순차 순회 수열은 {8, 3, 10, 1, 14, 6}

사고 분석

순차 순회 결과: {8, 3, 10, 1, 14, 6}

그러면 스레딩 후 바이너리 트리의 왼쪽 및 오른쪽 포인터는 위 그림과 같습니다↑

설명: 바이너리 트리가 스레드되면 Node 노드의 왼쪽 및 오른쪽 속성은 다음과 같습니다. 상황:

• left는 왼쪽 하위 트리를 가리키고, 또한 이전 노드가 가리키는 것일 수도 있습니다. 예를 들어 노드 ①의 왼쪽 하위 트리가 가리키고, 노드 ⑩의 왼쪽이 이전 노드를 가리킵니다.

  right는 오른쪽 하위 트리를 가리키거나 후속 노드를 가리킬 수 있습니다. 예를 들어 노드 ① right는 오른쪽 하위 트리를 가리키고 ⑩ 노드의 오른쪽은 후속 노드를 가리킵니다.

• 그래서 변경해야 합니다. 원래 이진 트리의 노드 구조

package com.studySelf.tree.threadedBinaryTree;

/**
 * @author wang
 * @version 1.0
 * @packageName com.studySelf.tree.tree01
 * @className Node
 * @date 2022/4/19 20:15
 * @Description Node结点
 */
public class Node {
    //唯一编号
    private int num;
    //结点的值
    private String name;
    //左结点
    private Node left;
    //右节点
    private Node right;

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;


    //构造方法

    public Node(int num, String name) {
        this.num = num;
        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 getNum() {
        return num;
    }

    public void setNum(int num) {
        this.num = num;
    }

    public String getName() {
        return name;
    }

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

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

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

    /**
     * 前序遍历
     */
    public void preSelect() {
        //首先输出根结点
        System.out.println(this);
        //其次判断是否有左结点
        if (this.left != null) {
            //没有左结点，就递归调用本方法输出该结点。
            this.left.preSelect();
        }
        if (this.right != null) {
            this.right.preSelect();
        }
    }

    /**
     * 中序遍历
     */
    public void infixSelect() {
        //首先判断左结点
        if (this.left != null) {
            //如果左结点不为空，递归向左子树调用
            this.left.infixSelect();
        }
        //当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点
        System.out.println(this);
        if (this.right != null) {
            //右节点同样如此，递归调用。直到没有结点为止。
            this.right.infixSelect();
        }
    }

    /**
     * 设二叉树有三个结点，根结点，左结点，右节点。
     * 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法
     * 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点
     * 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归，
     * 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点
     * 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。
     * 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根
     */

    public void afterSelect() {
        if (this.left != null) {
            this.left.afterSelect();
        }

        if (this.right != null) {
            this.right.afterSelect();
        }
        System.out.println(this);
    }

    /**
     * @param num
     * @Date 2022/4/21 17:51
     * @Param
     * @Return Node
     * @MetodName preSearchByNum
     * @Author wang
     * @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右
     */
    public Node preSearchByNum(int num) {
        //首先判断传进来的num与该结点的num是否相等
        //如果相等，那该结点就是我们要找的结点。
        if (this.num == num) {
            return this;
        }

        //如果不相等，该结点就不是我们要找的结点
        //那么我们就遍历该结点的左子节点，和右子结点
        //定义一个结点用于接收最后的返回结果
        Node resultNode = null;
        //如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值
        if (this.left != null) {
            resultNode = this.left.preSearchByNum(num);
        }

        //如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可，
        if (resultNode != null) {
            return resultNode;
        }

        //如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点
        if (this.right != null) {
            resultNode = this.right.preSearchByNum(num);
        }
        //最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/21 17:58
     * @Param
     * @Return Node
     * @MetodName infixSearchByNum
     * @Author wang
     * @Description 中序遍历查找，左，根，右进行查询即可。
     */
    public Node infixSearchByNum(int num) {
        //首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。
        Node resultNode = null;
        if (this.left != null) {
            resultNode = this.left.infixSearchByNum(num);
        }

        //如果左子结点已经找到了我们想要的结点，直接返回当前结点即可
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点
        if (this.num == num) {
            return this;
        }

        //判断右子结点，
        if (this.right != null) {
            resultNode = this.right.infixSearchByNum(num);
        }
        //最后返回我们的结果即可。
        return resultNode;
    }


    /**
     * @param num
     * @Date 2022/4/21 19:15
     * @Param
     * @Return Node
     * @MetodName afterSearchNum
     * @Author wang
     * @Description 后续遍历结点进行查找结点。左，右，根
     */
    public Node afterSearchNum(int num) {
        Node resultNode = null;
        //首先遍历左结点
        if (this.left != null) {
            resultNode = this.left.afterSearchNum(num);
        }

        //判断左结点是否找到哦啊
        if (resultNode != null) {
            return resultNode;
        }

        //判断右节点是否为空
        if (this.right != null) {
            resultNode = this.right.afterSearchNum(num);
        }

        //判断右节点是否找到
        if (resultNode != null) {
            return resultNode;
        }

        //判断根结点是否为我们找的结点
        if (this.num == num) {
            return this;
        }
        //最后返回
        return resultNode;
    }

    /**
     * @param num
     * @Date 2022/4/25 19:30
     * @Param
     * @Return void
     * @MetodName delNodeByNum
     * @Author wang
     * @Description 根据结点的编号删除结点
     */
    public void delNodeByNum(int num) {
        //首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等
        if (this.left != null && this.left.num == num) {
            //如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可
            this.left = null;
            return;
        }

        //如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点
        //那么就对右节点进行判断
        if (this.right != null && this.right.num == num) {
            this.right = null;
            return;
        }

        //如果左右结点均没有找到目标结点
        //那么就对左子树进行递归删除操作
        if (this.left != null) {
            this.left.delNodeByNum(num);
        }

        //同理，如果左子树没有目标结点，向右子树进行递归删除操作
        if (this.right != null) {
            this.right.delNodeByNum(num);
        }

    }
}

다음 두 가지 추가 속성이 있음을 알 수 있습니다.

    //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点
    private int leftType;
    //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点
    private int rightType;

순서 스레드 이진 트리

  /**中序线索化二叉树*/
    /**
     * @param node 该结点为根结点，从根节点开始线索化二叉树，中序
     */
    public void infixThreadNodes(Node node) {
        /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/
        if (node == null) {
            return;
        }

        /**接着对左子树进行线索化*/
        infixThreadNodes(node.getLeft());

        /**对当前结点进行线索化*/
        /**首先判断当前结点的左子结点是否为空*/
        if (node.getLeft() == null) {
            //如果左子结点为空，说明就找到了我们需要线索化的结点
            //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点，
            //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空
            node.setLeft(pre);
            //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点
            node.setLeftType(1);
        }

        /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/
        if (pre != null && pre.getRight() == null) {
            //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点，
            // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继，
            //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。
            //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化
            pre.setRight(node);
            pre.setRightType(1);
        }

        //当前两步走完之后，就可以将pre结点赋值为当前结点，
        // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束
        //这步十分重要，这一步不写，整个线索化就连接不上
        pre = node;

        /**对右子树进行线索化*/
        infixThreadNodes(node.getRight());
    }

중순 스레드 이진 트리 아이디어

순서대로 탐색된 이진 트리는 왼쪽 루트와 오른쪽이므로 먼저 왼쪽 하위 트리를 스레드하고 재귀적으로 스레드합니다.

1. 왼쪽 하위 트리의 가장 왼쪽 노드로 재귀할 때 왼쪽 노드는 비어 있어야 하며 그 다음 왼쪽 노드는 비어 있어야 합니다. 노드에는 pre 값이 할당됩니다(pre 노드에는 스레딩 노드의 마지막 단계에서 현재 값이 할당되므로 재귀가 계속될 수 있습니다). 왼쪽 노드의 유형은 1로 변경되어야 합니다. 이전 노드. 이전 노드가 단서를 잃었습니다.

2. 후속 노드의 처리는 선행 노드를 결정하는 것입니다. 현재 추세 노드가 비어 있지 않고 선행 노드의 오른쪽 노드가 비어 있으면 선행 노드의 오른쪽 노드를 현재 노드로 설정합니다. 즉, 설정되지 않은 이전 노드의 오른쪽 노드도 Successor

3. 로 설정해야 합니다. 마지막 단계는 현재 노드인 pre 노드에 값을 할당하는 것입니다. 다음 재귀에서는 현재 노드가 이전 노드가 됩니다. 여기서는 pre

4. 지점이 마지막으로 이진 트리의 올바른 자식 노드를 찾는 것입니다.

5. 순차 스레드 이진 트리 순회

순차 스레드 이진 트리를 순회할 때 순회 순서가 원래 순차 이진 트리 순회 결과와 동일해야 한다는 점을 먼저 분명히 해야 합니다. 그러면 순회가 성공할 것입니다

1. 첫 번째 단계는 루트 노드가 비어 있지 않은지 확인하는 것입니다. 이것이 루프 종료 조건입니다

2. 그런 다음 현재 노드의 왼쪽 자식 노드를 찾기 위해 루프를 반복합니다 유형이 0인 노드, 즉 스레드되지 않은 노드입니다. Point가 0인 한 노드는 항상 왼쪽 자식 노드에 값을 할당합니다. 첫 번째 스레드 노드를 찾아 출력할 때까지 이는 첫 번째 스레드 노드이자 순차 탐색의 첫 번째 왼쪽 하위 노드가 됩니다.

3. 출력 후 오른쪽 자식 노드가 스레드되었는지 확인하고 스레드된 경우 현재 노드 노드가 자체 오른쪽 자식 노드로 할당되고 그 뒤의 노드가 올바른 자식 유형이면 출력됩니다. 노드가 다시 1이 되면 계속해서 돌아가서 값을 할당하여 오른쪽 하위 노드의 유형이 0이 될 때까지 후속 노드가 있음을 나타냅니다

4. . 루프를 종료한 후 오른쪽에도 값을 할당해야 합니다. Post traversal

5. 코드 데모

    /**遍历中序线索化二叉树*/
    public void infixThreadNodesSelect() {
        /**第一个结点为根结点*/
        Node node = root;
        while(node != null) {
            /**当结点不为空，就一直遍历*/
            /**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点,
             * 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个
             * 左子结点类型为1的结点。*/
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            /**当左子结点的类型为1,输出左子结点*/
            System.out.println(node);

            /**当右子结点类型为1，当前结点输出完毕后
             * 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动
             * 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点，
             * 因此要在循环结束以后向后移动。*/
            while (node.getRightType() == 1) {
                node = node.getRight();
                System.out.println(node);
            }
            /**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/
            node = node.getRight();
        }

4로 계속 진행하세요. 스레드 바이너리 트리, traversal

스레드 바이너리 트리

를 선주문하세요.

 /**
     * 前序线索化二叉树
     */
    public void preThreadNodes(Node node) {
        /**首先判断当前节点是否为空*/
        if (node == null) {
            return;
        }

        /**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/
        if (node.getLeft() == null) {
            node.setLeft(pre);
            node.setLeftType(1);
        }

        /**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以
         * 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node);
            pre.setRightType(1);
        }

        /**这里是关键的一步*/
        pre = node;

        /**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况，
         * 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了
         * 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点
         * 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/
        if (node.getLeftType() != 1) {
            preThreadNodes(node.getLeft());
        }


        /**对右子结点进行递归线索化*/
        if (node.getRightType() != 1) {
            preThreadNodes(node.getRight());
        }
    }

 遍历线索化二叉树

/**
     * 前序遍历线索二叉树*/
    public void preThreadNodeSelect() {
        Node node = root;
        while(node !=null) {
            while(node.getLeftType() == 0) {
                /**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环
                 * 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/
                System.out.println(node);
                /**再最左子结点进行遍历*/
                node = node.getLeft();
            }
            /**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点
             * 之后结点向右移动继续遍历*/
            System.out.println(node);
            node = node.getRight();
        }
  }

图解

5.后序线索化二叉树

后续线索化二叉树

/**
 * 后序线索化二叉树的方法
 */
public void postThreadedBinaryTree(Node node) {
    /**首先判断结店不能为空*/
    if (node == null) {
        return;
    }

    /**先后续线索化左子结点*/
    postThreadedBinaryTree(node.getLeft());
    /**在后续线索化右子结点*/
    postThreadedBinaryTree(node.getRight());

    /**处理当前结点的前趋结点*/
    if (node.getLeft() == null) {
        node.setLeft(pre);
        node.setLeftType(1);
    }

    /**处理后继结点*/
    if (pre != null && pre.getRight() == null) {
        pre.setRight(node);
        pre.setRightType(1);
    }
    pre = node;
}

위 내용은 Java 데이터 구조에서 스레드 이진 트리를 구현하는 방법은 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!