【數算-19】樹-有解無憂

文章目錄

- - 1、樹結構的優點
  - 2、樹的基本結構與術語
  - 3、二叉樹簡介
  - - 1、二叉樹的結構
    - 2、二叉樹的代碼實作
    - - 1、對單個結點的定義（Node.class）
      - 2、對二叉樹結構的定義（BinaryTree.class）
    - 3、二叉樹的三種遍歷方式
    - 4、二叉樹遍歷實體
    - - 1、先序遍歷
      - 2、中序遍歷
      - 3、后序遍歷
      - 4、對三種遍歷方式進行檢驗
    - 5、二叉樹的查找
    - - 1、先序查找
      - 2、中序查找
      - 3、后序查找
      - 4、對三種查找方式進行檢驗
      - 5、對三種查找演算法的測驗及比較
    - 6、洗掉某個節點
    - - 1、問題描述
      - 2、代碼實作
      - 3、代碼測驗
    - 7、洗掉結點擴展
    - - 1、問題描述
      - 2、代碼實作
      - 3、代碼測驗

1、樹結構的優點

在這里插入圖片描述

陣列在進行插入洗掉操作時，會使部分節點進行整體前后移動，造成不必要的開銷，但查找效率較鏈表較高
鏈表在進行查找操作時，每次都要從頭結點或首個結點進行遍歷，查找效率很低，但插入洗掉效率較陣列而言也較高
目前并沒有一種資料結構能夠較完美地進行各種資料操作，因此樹產生了

2、樹的基本結構與術語

在這里插入圖片描述

3、二叉樹簡介

1、二叉樹的結構

在這里插入圖片描述

這里注意完全二叉樹的概念

2、二叉樹的代碼實作

1、對單個結點的定義（Node.class）

public class Node {
    private Integer no;
    private String name;
    //	分別定義二叉樹的左、右子結點
    private Node left;
    private Node right;
    
    public Node(Integer no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "binary_tree.Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public Integer getNo() {
        return no;
    }

    public void setNo(Integer no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    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;
    }
}

2、對二叉樹結構的定義（BinaryTree.class）

public class BinaryTree {
    private Node root;

    public BinaryTree(Node root) {
        this.root = root;
    }
}

3、二叉樹的三種遍歷方式

在這里插入圖片描述
由上圖可知：

二叉樹采用哪種遍歷主要取決于其根結點遍歷順序：

先序遍歷：根-左-右
中序遍歷：左-根-右
后序遍歷：左-右-根

因此“先”、“中”、“后”針對的是根節點

4、二叉樹遍歷實體

在這里插入圖片描述

遍歷是根據某個節點的左右指標進行相應操作，因此具體的遍歷方法應該定義在Node.class中，而方法的呼叫應該具體針對的是某個點，因此需要在BinaryTree.class中對該方法進行再次封裝

1、先序遍歷

Node.class

    public void preOrderIterate() {
//        不用判斷該節點是否為空
//		  直接先列印當前節點
        System.out.println(this);
//        對當前節點的左子節點進行遞回遍歷
        if (this.left != null) {
            this.left.preOrderIterate();
        }
//        遞回遍歷當前節點的右子節點
        if (this.right != null) {
            this.right.preOrderIterate();
        }
    }

BinaryTree.class

	public void preIterate() {
        if (this.root != null) {
            this.root.preOrderIterate();
        } else {
            System.out.println("當前根節點為空！");
        }
    }

2、中序遍歷

Node.class

	public void midOrderIterate() {
        if (this.left != null) {
            this.left.midOrderIterate();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrderIterate();
        }
    }

BinaryTree.class

	public void midIterate() {
        if (this.root != null) {
            this.root.midOrderIterate();
        } else {
            System.out.println("當前根節點為空！");
        }
    }

3、后序遍歷

Node.class

	public void postIterate() {
        if (this.left != null) {
            this.left.postIterate();
        }
        if (this.right != null) {
            this.right.postIterate();
        }
        System.out.println(this);
    }

BinaryTree.class

	public void postIterate() {
        if (this.root != null) {
            this.root.postIterate();
        } else {
            System.out.println("當前根節點為空！");
        }
    }

4、對三種遍歷方式進行檢驗

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node1 = new Node(2,"吳用");
        Node node2 = new Node(3,"盧俊義");
        Node node3 = new Node(4,"林沖");
        Node node4 = new Node(5,"阮小七");
        Node node5 = new Node(6,"阮小五");
        Node node6 = new Node(7,"阮小六");
        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setRight(node4);
        node2.setRight(node3);

//                    1
//                /       \
//               2         3
//                \         \
//                 5         4

        System.out.println("前序遍歷");
        binaryTree.preIterate();
        System.out.println("----");
        System.out.println("中序遍歷");
        binaryTree.midIterate();
        System.out.println("----");
        System.out.println("后序遍歷");
        binaryTree.postIterate();
      }
   }

測驗結果：
在這里插入圖片描述

5、二叉樹的查找

二叉樹的查找也分為三種：先序查找、中序查找及后序查找

1、先序查找

Node.class

//  前序查找
    public Node preSearch(int value) {
        System.out.println("~~~");	//用來顯示遞回次數
//        先比較當前節點是否為指定值
        if (this.getNo() == value) {
            return this;
        }
        
//        若當前節點不為指定值，則判斷當前節點的左子節點是否為空，若不為空，則遞回前序查找
//        若做遞回前序查找，找到節點則回傳
        Node resNode = null;    //創建resNode用來接收no為value的節點
        if(this.left!=null) {
            resNode = this.left.preSearch(value);
        }
        if(resNode!=null){  //判斷結果集不為空，說明找到，直接回傳，避免左子樹找到還要去右子樹尋找
            return resNode;
        }
//        若左子樹沒找到，就去右子樹找
        if(this.right!=null){
            resNode = this.right.preSearch(value);
        }
//        直接回傳結果集即可
        return resNode;
    }

BinaryTree.class

public Node preSearch(int value){
        if(this.root!=null){
            return root.preSearch(value);
        }else{
            System.out.println("二叉樹為空，無法遍歷");
            return null;
        }
    }

2、中序查找

Node.class

//  中序查找
    public Node midSearch(int value){

        Node resNode = null;    //創建resNode用來接收no為value的節點
        if(this.left!=null) {
            resNode = this.left.midSearch(value);
        }
        if(resNode!=null){  //判斷結果集不為空，說明找到，直接回傳
            return resNode;
        }
        System.out.println("~~~");
        if(this.getNo()==value){
            return this;
        }
        if(this.right!=null){
            resNode = this.right.midSearch(value);
        }
        return resNode;
    }

BinaryTree.class

	public Node midSearch(int value){
        if(this.root!=null){
            return root.midSearch(value);
        }else{
            System.out.println("二叉樹為空，無法遍歷");
            return null;
        }
    }

3、后序查找

Node.class

//  后序查找
    public Node postSearch(int value){

        Node resNode = null;
        if(this.left!=null){
            resNode = this.left.postSearch(value);
        }
        if(resNode!=null){
            return resNode;
        }
        if(this.right!=null){
            resNode = this.right.postSearch(value);
        }
        if(resNode!=null){
            return resNode;
        }
        System.out.println("~~~");
        if(this.getNo()==value){
            return this;
        }
        return resNode;
    }

BinaryTree.class

	public Node postSearch(int value){
        if(this.root!=null){
            return root.postSearch(value);
        }else{
            System.out.println("二叉樹為空，無法遍歷");
        }
        return null;
    }

4、對三種查找方式進行檢驗

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node1 = new Node(2,"吳用");
        Node node2 = new Node(3,"盧俊義");
        Node node3 = new Node(4,"林沖");
        Node node4 = new Node(5,"阮小七");
        Node node5 = new Node(6,"阮小五");
        Node node6 = new Node(7,"阮小六");
        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setRight(node4);
        node2.setRight(node3);

//                    1
//                /       \
//               2         3
//                \         \
//                 5         4

        System.out.println("前序查找");
		binary_tree.Node resNode1 = binaryTree.preSearch(5);
		if(resNode1!=null){
		    System.out.printf("找到了no=%d，name = %s的結點\n",resNode1.getNo(),resNode1.getName());
		}else{
		    System.out.println("找不到");
		}
		System.out.println("----");
		System.out.println("中序查找");
		binary_tree.Node resNode2 = binaryTree.midSearch(5);
		if(resNode2!=null){
		    System.out.printf("找到了no=%d，name = %s的結點\n",resNode2.getNo(),resNode2.getName());
		}else{
		    System.out.println("找不到");
		}
		System.out.println("----");
		System.out.println("后序查找");
		binary_tree.Node resNode3 = binaryTree.postSearch(5);
		if(resNode3!=null){
		    System.out.printf("找到了no=%d，name = %s的結點\n",resNode3.getNo(),resNode3.getName());
		}else{
		    System.out.println("找不到");
		}
      }
   }

5、對三種查找演算法的測驗及比較

根據上述代碼，以及對遞回進行了標識，可以看到對于5號結點來說，前序查找共呼叫方法3次，中序為2次，后序為1次
在這里插入圖片描述

6、洗掉某個節點

1、問題描述

在這里插入圖片描述

2、代碼實作

Node.class

//  洗掉指定序號的結點
   /*
    思路：因為二叉樹是單向的，所以在呼叫方法時判斷的是當前節點的子節點是否需要洗掉而不是當前結點是否需要洗掉
    若當前節點的左子節點不為空且no為value，則直接將其左子節點置為空并回傳 this.left = null
    右子節點同理 this.right = null
    若左右子節點均不是要洗掉的結點，則遞回呼叫其左右子節點的該方法進行判斷洗掉操作
    */

   public void delNode(int no){
//        判斷該節點的左右結點是否為待洗掉結點
//		左子樹不為空且其值等于no
        if(this.left != null &&this.left.getNo()==no){
            this.left = null;
        }
//		右子樹不為空且其值等于no
        if(this.right!=null&&this.right.getNo()==no){
            this.right = null;
        }
//        分別遞回左右子樹
        if(this.left!=null){
            this.left.delNode(no);
        }
        if(this.right!=null){
            this.right.delNode(no);
        }


    }

BinaryTree.class


//    洗掉節點
    public void delNode(int no){
        if(this.root!=null){
//            如果只有一個root節點，就需要判斷root是不是待洗掉結點
            if(this.root.getNo()==no){
                root = null;
            }else{
                root.delNode(no);
            }
        }else{
            System.out.println("樹為空，不能洗掉！");
        }
    }

3、代碼測驗

測驗類

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node1 = new Node(2,"吳用");
        Node node2 = new Node(3,"盧俊義");
        Node node3 = new Node(4,"林沖");
        Node node4 = new Node(5,"阮小七");
        Node node5 = new Node(6,"阮小五");
        Node node6 = new Node(7,"阮小六");
        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node2.setRight(node4);
        node4.setLeft(node5);
        node4.setRight(node6);
        
        System.out.println("洗掉no為3的結點");
        System.out.println("洗掉前");
        root.preOrderIterate();
        root.delNode(3);
        System.out.println("洗掉后：");
        root.preOrderIterate();
		}	
    }

在這里插入圖片描述

7、洗掉結點擴展

1、問題描述

在這里插入圖片描述

2、代碼實作

Node.class

/*
    * 擴展：
    *   若洗掉的是非葉子結點且該結點只有一個子節點，那么就讓其子節點代替該葉子結點的位置
    *   若洗掉的是非葉子結點且該結點有兩個子節點，讓其左子節點代替該葉子結點的位置
    * */

    public void delNode(int no){
//        判斷該節點的左右結點是否為待洗掉結點
        if(this.left!=null&&this.left.getNo()==no){
            if(this.left.left!=null&&this.left.right==null){
                this.left = this.left.left;
            }
            if(this.left.right!=null&&this.left.left==null){
                this.left = this.left.right;
            }
            if(this.left.left !=null && this.left.right!=null){
//            洗掉的是非葉子結點且該結點有兩個子節點，讓其左子節點代替該葉子結點的位置，當前節點的右子節點變為當前節點左子節點的右子節點
                this.left.left.setRight(this.left.right);
                this.left = this.left.left;

            }
//            this.left = null;
        }
        if(this.right!=null&&this.right.getNo()==no){
            if(this.right.left!=null&&this.right.right==null){
                this.right = this.right.left;
            }
            if(this.right.right!=null&&this.right.left==null){
                this.right = this.right.right;
            }
            if(this.right.left!=null&&this.right.right!=null){
//            洗掉的是非葉子結點且該結點有兩個子節點，讓其左子節點代替該葉子結點的位置，當前節點的右子節點變為當前節點左子節點的右子節點
                this.right.left.setRight(this.right.right);
                this.right = this.right.left;
            }
//            this.right = null;
        }
//        分別遞回左右子樹
        if(this.left!=null){
            this.left.delNode(no);
        }
        if(this.right!=null){
            this.right.delNode(no);
        }


    }

BinaryTree.class

//    洗掉節點
    public void delNode(int no){
        if(this.root!=null){
//            如果只有一個root節點，就需要判斷root是不是待洗掉結點
            if(this.root.getNo()==no){
                root = null;
            }else{
                root.delNode(no);
            }
        }else{
            System.out.println("樹為空，不能洗掉！");
        }
    }

3、代碼測驗

對于擴展問題的兩個要求：

/*
    * 擴展：
    *   若洗掉的是非葉子結點且該結點只有一個子節點，那么就讓其子節點代替該葉子結點的位置
    *   若洗掉的是非葉子結點且該結點有兩個子節點，讓其左子節點代替該葉子結點的位置
* */

針對只有一個子節點的結點，可以洗掉node3（no=2）

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node1 = new Node(2,"吳用");
        Node node2 = new Node(3,"盧俊義");
        Node node3 = new Node(4,"林沖");
        Node node4 = new Node(5,"阮小七");
        Node node5 = new Node(6,"阮小五");
        Node node6 = new Node(7,"阮小六");
        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node2.setRight(node4);
        node4.setLeft(node5);
        node4.setRight(node6);
        
        System.out.println("洗掉no為2的結點");
        System.out.println("洗掉前");
        root.preOrderIterate();
        root.delNode(2);
        System.out.println("洗掉后：");
        root.preOrderIterate();
		}	
    }

圖示：
在這里插入圖片描述

在這里插入圖片描述

針對兩個子節點的節點，可以洗掉node6（no=5）

public class BinaryTreeTest {
    public static void main(String[] args) {
        Node root = new Node(1,"宋江");
        Node node1 = new Node(2,"吳用");
        Node node2 = new Node(3,"盧俊義");
        Node node3 = new Node(4,"林沖");
        Node node4 = new Node(5,"阮小七");
        Node node5 = new Node(6,"阮小五");
        Node node6 = new Node(7,"阮小六");
        BinaryTree binaryTree = new BinaryTree(root);
        root.setLeft(node1);
        root.setRight(node2);
        node1.setLeft(node3);
        node2.setRight(node4);
        node4.setLeft(node5);
        node4.setRight(node6);
        
        System.out.println("洗掉no為5的結點");
        System.out.println("洗掉前");
        root.preOrderIterate();
        root.delNode(6);
        System.out.println("洗掉后：");
        root.preOrderIterate();
		}	
    }

圖示：
在這里插入圖片描述

在這里插入圖片描述
綜上所述，代碼測驗結果均與分析結果相同

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/261057.html

標籤：java

上一篇：Java中static的作用

下一篇：爬取豆瓣電影