java实现二叉树的Node节点定义,并手撕8种遍历 |
您所在的位置：网站首页 › 叉的啥意思 › java实现二叉树的Node节点定义,并手撕8种遍历 |
java实现二叉树的Node节点定义,并手撕8种遍历
|
最近准备秋招面试，发现二叉树这种可以无限扩展知识点来虐别人的数据结构，很受面试官的青睐。 如果掌握的不好，会直接死在一面哦。 怕吗？当你原理、思想，内部结构通通明白，分分钟手撕代码的程度，还怕吗？ 本篇文章就从用java的思想和程序从最基本的怎么将一个int型的数组变成Node树状结构说起，再到递归前序遍历，递归中序遍历，递归后序遍历，非递归前序遍历，非递归前序遍历，非递归前序遍历，到最后的广度优先遍历和深度优先遍历 来咯！ 一、Node节点的java实现首先在可以看到打上Node这个字符串，就可以看到只能的IDEA系统提供的好多提示： 点进去看，却不是可以直接构成二叉树的Node，不是我们需要的东西。这里举个例子来看 org.w3c.dom 这里面的Node是一个接口，是解析XML时的文档树。在官方文档里面看出：该 Node 接口是整个文档对象模型的主要数据类型。它表示该文档树中的单个节点。当实现 Node 接口的所有对象公开处理子节点的方法时，不是实现 Node 接口的所有对象都有子节点。 所以我们需要自定义一个Node类 package com.sort.text; public class Node { private int value; //节点的值 private Node node; //此节点，数据类型为Node private Node left; //此节点的左子节点，数据类型为Node private Node right; //此节点的右子节点，数据类型为Node public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getNode() { return node; } public void setNode(Node node) { this.node = node; } 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; } public Node(int value) { this.value=value; this.left=null; this.right=null; } public String toString() { //自定义的toString方法，为了方便之后的输出 return this.value+" "; } }定义好了之后就可以开始直接使用了，相信大家都可以秒看懂。 二、数组升华二叉树一般拿到的数据是一个int型的数组，那怎么将这个数组变成我们可以直接操作的树结构呢？ 1、数组元素变Node类型节点 2、给N/2-1个节点设置子节点 3、给最后一个节点设置子节点【有可能只有左节点】 那现在就直接上代码 public static void create(int[] datas,List list) { //将数组里面的东西变成节点的形式 for(int i=0;i |
【本文地址】