如题
- 先序构造
- 数据类型使用了泛型,在后续的更改中,更换数据类型只需要少许的变更代码
- 层序遍历
- 利用Node类的level属性
- 所有属性的权限全为public ,为了方便先这么写吧,建议还是用private来写.
- 还有个问题,值得注意, 就是先序构造的时候注意传入的root节点是形参, 无论通过"."还是"get"方法得到的属性都是形参;
-
因此, 要在函数中添加返回体--返回相应修改后的字段,进行覆盖.
大致的工程组织.png
-
Node.java
package com.szs;
/**
* @description 描述二叉树的每个节点的类
* @author Administrator
*
* @param <T> 设置泛型
*/
public class Node<T>{
//数据data 和 左右儿子 ,level: 层级数
public Node lChild;
public Node rChild;
public T data;
public int level;
//两种构造器
public Node(){
data = null;
lChild=null;
rChild=null;
}
public Node(T x){
data = x;
lChild=new Node();
rChild=new Node();
}
}
BinaryTree.java
package com.szs;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;
/**
* @description 描述二叉树的每种操作方法的类,创建/
* @author Administrator
*
* @param <T> 设置泛型
*/
public class BinaryTree<T> {
//二叉树的根节点
public Node<T> root;
//两种构造器
//创建一棵以数据元素为根节点的二叉树
public BinaryTree(T x) {
this.root = new Node<T>(x);
}
//创建一空的二叉树,但需要初始化根节点,相当于C语言中的分配内存空间
public BinaryTree() {
//this.root = null; //错误写法
this.root = new Node<T>();
}
/**为先序序列的构建提供数据*/
public LinkedList<Integer> array;
//先序构造一棵二叉树, 迭代构造
@SuppressWarnings("unchecked")
public <T> Node<T> preOrderBuild(Node<T> rootNode){
if(rootNode==null){
return null;
}
/*从队首取出一个数据,然后删除*/
int value = (Integer) array.get(0);
array.removeFirst();
if(value!=-1){
//构建当前根节点 , 注意这里的泛型
rootNode = (Node<T>) new Node<Integer>(value);
//迭代构建左右子树
rootNode.lChild = preOrderBuild(rootNode.lChild);
rootNode.rChild = preOrderBuild(rootNode.rChild);
}
return rootNode;
}
//层次遍历该树,迭代输出,非递归
public <T> void levelRetrieve(){
//建立列表
List<Node> list = new LinkedList<Node>();
if(this.root!=null){
this.root.level=0;
list.add(this.root);
}
int i=0;
while(i<list.size()){
int level = list.get(i).getLevel();
Node node = list.get(i);
if(node.lChild!=null){
node.lChild.level = level+1;
list.add(node.lChild);
}
if(node.rChild!=null){
node.rChild.level = level+1;
list.add(node.rChild);
}
//顺序遍历
i++;
}
//层级输出
System.out.println("---------层级输出-----------");
for(int j=0;j<list.size();j++){
if(list.get(j).data!=null){
System.out.print(list.get(j).data);
}
if(j<list.size()-1 && list.get(j).level==list.get(j+1).level){
System.out.print("\t");
}else{
System.out.print("\n");
}
}
}
}
TestBinaryTree.java 主测试二叉树的类
package com.szs;
import java.util.LinkedList;
import java.util.Scanner;
public class TestBinaryTree {
public static void main(String[] args) {
//构造
BinaryTree<Integer> binaryTree = new BinaryTree<Integer>(null);
//先序创建二叉树 , 如下提供了三组简单数据
// 1 2 -1 -1 3 4 -1 -1 -1
// 1 2 -1 -1 3 -1 -1
// 1 2 -1 -1 -1
init(binaryTree);
binaryTree.root = binaryTree.preOrderBuild(binaryTree.root);
//层序
binaryTree.levelRetrieve();
}
/**
* 初始化构造二叉树数据的数组
* @param binaryTree
*/
public static void init(BinaryTree<Integer> binaryTree){
System.out.println("请输入该二叉树先序构造的数组序列(以单个空格隔开): ");
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
String[] arrStrings=str.trim().split(" ");
LinkedList<Integer> intArr = new LinkedList<Integer>();
for(int i=0;i<arrStrings.length;i++){
intArr.add( Integer.parseInt( arrStrings[i]));
}
binaryTree.array=intArr;
}
}
先序构造测试及相关输出
image.png
请输入该二叉树先序构造的数组序列(以单个空格隔开):
1 2 -1 -1 3 4 -1 -1 -1
---------层级输出-----------
1
2 3
4
