手写二叉树-先序构造(泛型)-层序遍历（Java版）

如题

• 先序构造
  • 数据类型使用了泛型,在后续的更改中,更换数据类型只需要少许的变更代码
• 层序遍历
  • 利用Node类的level属性
• 所有属性的权限全为public ,为了方便先这么写吧,建议还是用private来写.
• 还有个问题,值得注意, 就是先序构造的时候注意传入的root节点是形参, 无论通过"."还是"get"方法得到的属性都是形参;
  • 因此, 要在函数中添加返回体--返回相应修改后的字段,进行覆盖.
    
    

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;

	}

}

先序构造测试及相关输出

请输入该二叉树先序构造的数组序列(以单个空格隔开):

1 2 -1 -1 3 4 -1 -1 -1

---------层级输出-----------

1

2	3

		4