如題

• 先序構造
  • 數(shù)據(jù)類型使用了泛型,在后續(xù)的更改中,更換數(shù)據(jù)類型只需要少許的變更代碼
• 層序遍歷
  • 利用Node類的level屬性
• 所有屬性的權限全為public ,為了方便先這么寫吧,建議還是用private來寫.
• 還有個問題,值得注意, 就是先序構造的時候注意傳入的root節(jié)點是形參, 無論通過"."還是"get"方法得到的屬性都是形參;

  • 因此, 要在函數(shù)中添加返回體--返回相應修改后的字段,進行覆蓋.

    
    
    大致的工程組織.png

Node.java

package com.szs;
/**
 * @description 描述二叉樹的每個節(jié)點的類
 * @author Administrator
 *
 * @param <T> 設置泛型
 */
public class Node<T>{
    //數(shù)據(jù)data 和 左右兒子 ,level: 層級數(shù)
    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 描述二叉樹的每種操作方法的類,創(chuàng)建/
 * @author Administrator
 *
 * @param <T> 設置泛型
 */
public class BinaryTree<T> {
    //二叉樹的根節(jié)點
    public Node<T> root;
    
    //兩種構造器
    //創(chuàng)建一棵以數(shù)據(jù)元素為根節(jié)點的二叉樹
    public BinaryTree(T x) {
        this.root = new Node<T>(x);
    }
    //創(chuàng)建一空的二叉樹,但需要初始化根節(jié)點,相當于C語言中的分配內存空間
    public BinaryTree() {
        //this.root = null;   //錯誤寫法
        this.root = new Node<T>();
    }
    
    /**為先序序列的構建提供數(shù)據(jù)*/
    public LinkedList<Integer> array;

    //先序構造一棵二叉樹, 迭代構造
    @SuppressWarnings("unchecked")
    public <T>  Node<T> preOrderBuild(Node<T> rootNode){
        if(rootNode==null){
            return null;
        }
        
        /*從隊首取出一個數(shù)據(jù),然后刪除*/
        int value = (Integer) array.get(0);
        array.removeFirst();
        
        if(value!=-1){
            //構建當前根節(jié)點 , 注意這里的泛型
            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); 
        
        //先序創(chuàng)建二叉樹 , 如下提供了三組簡單數(shù)據(jù)
        //  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();
    }
    /**
     * 初始化構造二叉樹數(shù)據(jù)的數(shù)組
     * @param binaryTree
     */
    public static void init(BinaryTree<Integer> binaryTree){
        System.out.println("請輸入該二叉樹先序構造的數(shù)組序列(以單個空格隔開):   ");
        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

請輸入該二叉樹先序構造的數(shù)組序列(以單個空格隔開):   
1 2 -1 -1 3 4 -1 -1 -1
---------層級輸出-----------
1
2   3
        4