环球ug官网:二叉树的建立与遍历(递归实现)

admin 4个月前 (06-20) 科技 56 0

在树的基本概念和术语总结一文中先容了二叉树的基本结构。

在不知道怎样用递归?按步骤来!一文中先容了若何使用递归。

二叉树的结构是递归的,以是建立、遍历也可以通过递归实现。

下面是一颗二叉树:

结点的界说:

public class Node {
    Integer value;
    Node leftChild;
    Node rightChild;

    public Node(Integer value) {
        this.value = value;
    }
}

建立

各个结点的值用一个ArrayList聚集来保留,凭据该聚集来建立二叉树。

根据不知道怎样用递归?按步骤来!中的方式剖析若何递归地建立一颗二叉树。

第一步:找到大问题是什么?

建立一颗二叉树。

private Node createBinaryTree(ArrayList<Integer> inputList) {
        
}

第二步:找到最简朴问题是什么?知足最简朴问题时应该做什么?

「建立一个空二叉树」是最简朴的问题,当知足时,直接返回null

private Node createBinaryTree(ArrayList<Integer> inputList) {   
    if (inputList == null || inputList.isEmpty()) {//最简朴问题
        return null;
    }
}

第三步:找到重复逻辑是什么?

由于我们把每个结点的值都放在ArrayList聚集中了,以是,每建立一个二叉树结点,都需要从聚集中拿值。

对于每个结点而言,它一定有左孩子和右孩子(上图中结点3的左孩子和右孩子可以看成「值为null的结点」),

以是要确定每个结点的左孩子和右孩子是谁。

以是重复逻辑是:

  1. 从聚集中拿值,建立结点。
  2. 确定该结点的左孩子和右孩子。
//大问题
private Node createBinaryTree(ArrayList<Integer> inputList) {
    if (inputList == null || inputList.isEmpty()) {//最简朴问题
        return null;
    }
    Node node = null;//重复逻辑
    Integer value = inputList.remove(0);//重复逻辑
    if (value != null) {
        node = new Node(value);//重复逻辑
        node.leftChild = ?;//重复逻辑
        node.rightChild = ?;//重复逻辑
    }

}

第四步:自己挪用自己

先解释一下上个代码片断中的问号。

要确定一个结点的左孩子和右孩子是谁,实在就是一个赋值操作,那么就一定要先有一些可选的结点

比如说,若是我们要确定结点1的左右孩子,那么结点2、结点5就必须已经被建立出来了,这样才气举行赋值操作。

那么若何在举行赋值操作之前建立结点2、结点5呢?谜底是自己挪用自己。

我们可以把结点2、结点5看成另一颗二叉树的根结点,只要我们建立好以结点2或结点5为根结点的二叉树,那么结点2和结点5自然就被建立出来了。

确定结点2和结点5的左右孩子同理,这样一直剖析下去,直到剖析成最简朴问题,或者从聚集中拿到null为止。

注重:自己挪用自己时参数的变小是通过inputList.remove(0)实现的。

//大问题
private Node createBinaryTree(ArrayList<Integer> inputList) {
    if (inputList == null || inputList.isEmpty()) {//最简朴问题
        return null;
    }
    Node node = null;//重复逻辑
    Integer value = inputList.remove(0);//重复逻辑
    if (value != null) {
        node = new Node(value);//重复逻辑
        node.leftChild = createBinaryTree(inputList);//重复逻辑,自己挪用自己
        node.rightChild = createBinaryTree(inputList);//重复逻辑,自己挪用自己
    }

}

第五步:返回

返回的是根结点,该根结点被确定为左孩子或右孩子,从而组成一颗更大的二叉树,直到知足最大问题的那颗二叉树被建立乐成,此时返回的根结点是真正的解。

//大问题
private Node createBinaryTree(ArrayList<Integer> inputList) {
    if (inputList == null || inputList.isEmpty()) {//最简朴问题
        return null;
    }
    Node node = null;//重复逻辑
    Integer value = inputList.remove(0);//重复逻辑
    if (value != null) {
        node = new Node(value);//重复逻辑
        node.leftChild = createBinaryTree(inputList);//重复逻辑,自己挪用自己
        node.rightChild = createBinaryTree(inputList);//重复逻辑,自己挪用自己
    }
	return node;//返回
}

遍历

先序遍历

第一步:找到大问题是什么?

先序遍历一颗二叉树,打印出每个结点的值。

public void preOrderTraveral(Node node) {
    
}

第二步:找到最简朴问题是什么?知足最简朴问题时应该做什么?

「遍历一颗空二叉树」是最简朴问题,此时任何操作都不用做。

public void preOrderTraveral(Node node) {
    if (node == null) {//最简朴问题
        return;
    }
}

第三步:找到重复逻辑是什么?

打印每个结点的值

public void preOrderTraveral(Node node) {
    if (node == null) {//最简朴问题
        return;
    }
    System.out.print(node.value);//重复逻辑
}

第四步:自己挪用自己

先序遍历的历程:

  1. 遍历根结点
  2. 先序遍历左子树
  3. 先序遍历右子树
public void preOrderTraveral(Node node) {
    if (node == null) {//最简朴问题
        return;
    }
    System.out.print(node.value);//重复逻辑
    preOrderTraversal(node.leftChild);//自己挪用自己
    preOrderTraversal(node.rightChild);//自己挪用自己
}

自己挪用自己时参数通过node.leftChildnode.rightChild不停变小

第五步:返回

不需要返回值。

中序遍历和后序遍历同理

完整代码

//二叉树结点
public class Node {
    Integer value;
    Node leftChild;
    Node rightChild;

    public Node(Integer value) {
        this.value = value;
    }
}
//二叉树
public class BinaryTree {

    private Node root;

    public Node getRoot() {
        return root;
    }

    public BinaryTree(ArrayList<Integer> inputList) {
        Node root = createBinaryTree(inputList);
        this.root = root;
    }

	//建立二叉树
    private Node createBinaryTree(ArrayList<Integer> inputList) {
        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        Node node = null;
        Integer value = inputList.remove(0);
        if (value != null) {
            node = new Node(value);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }
        return node;
    }

    //先序遍历
    public void preOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        System.out.print(node.value);
        preOrderTraversal(node.leftChild);
        preOrderTraversal(node.rightChild);
    }
	
    //中序遍历
    public void inOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inOrderTraversal(node.leftChild);
        System.out.print(node.value);
        inOrderTraversal(node.rightChild);
    }

    //后序遍历
    public void postOrderTraversal(Node node) {
        if (node == null) {
            return;
        }
        postOrderTraversal(node.leftChild);
        postOrderTraversal(node.rightChild);
        System.out.print(node.value);
    }
}
//测试
public static void main(String[] args) {
    List<Integer> list = Arrays.asList(new Integer[]{1, 2, 3, null, null, 4, null, null, 5, null, 6});
    ArrayList inputList = new ArrayList(list);

    BinaryTree binaryTree = new BinaryTree(inputList);
    Node root = binaryTree.getRoot();
    System.out.print("先序遍历:");
    binaryTree.preOrderTraversal(root);
    System.out.print("\n中序遍历:");
    binaryTree.inOrderTraversal(root);
    System.out.print("\n后序遍历:");
    binaryTree.postOrderTraversal(root);
}

若有错误,还请指正。

文章首发于微信民众号『行人观学』

,

欧博开户

欢迎进入欧博开户(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

Allbet声明:该文看法仅代表作者自己,与本平台无关。转载请注明:环球ug官网:二叉树的建立与遍历(递归实现)

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:439
  • 页面总数:0
  • 分类总数:8
  • 标签总数:870
  • 评论总数:126
  • 浏览总数:3177