二叉樹

一.基本概念

概念
一棵二叉樹是結點的一個有限集合，該集合或者為空，或者是由一個根節點加上兩棵別稱為左子樹和右子樹的二叉樹組成，
特點：

每個結點最多有兩棵子樹，即二叉樹不存在度大于 2 的結點，
二叉樹的子樹有左右之分，其子樹的次序不能顛倒，因此二叉樹是有序樹，

3**.五種基本形態**

一棵空樹
只有一個節點
只有頭節點和左子樹
只有根和右子樹
根節點、左子樹、右子樹

二.特殊的倆種二叉樹

滿二叉樹
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹，也就是說，如果一個二叉樹的層數為K，且結點總數是，則它就是滿二叉樹，
完全二叉樹

完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的，對于深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹，要注意的是滿二叉樹是一種特殊的完全二叉樹，
在這里插入圖片描述

三.二叉樹的存盤方式

二叉樹的存盤結構分為：順序存盤和類似于鏈表的鏈式存盤，

3.1常用的鏈式存盤

//孩子表示法
class Node {
int val; // 資料域
Node left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
public Node(char val) {
        this.val = val;
    }
}

// 孩子雙親表示法
class Node {
int val; // 資料域
Node left; // 左孩子的參考，常常代表左孩子為根的整棵左子樹
Node right; // 右孩子的參考，常常代表右孩子為根的整棵右子樹
Node parent; // 當前節點的根節點
public Node(char val) {
        this.val = val;
    }
}

四.二叉樹的三種遍歷方式

前序遍歷(NLR):順序：根節點–》根的左子樹–》根的右子樹

//前序遍歷
    void preOrderTraversal(Node root){
        if (root == null)return;//如果樹為空樹，直接就退出；
        //到這一步說明樹不是空樹，那么就可以列印根節點；
        System.out.println(root.val+" ");
        /*那么就接著往下看它的左子樹，跟判斷它的父親節點同樣的判斷方法，因此進行不斷的遞回*/
        preOrderTraversal(root.left);
        //右子樹和左子樹同樣的道理；
        preOrderTraversal(root.right);
    }

中序遍歷(LNR):順序：根的左子樹–》根節點–》根的右子樹

 //中序遍歷
    void inOrderTraversal(Node root){
        if (root == null)return;
        inOrderTraversal(root.left);
        System.out.println(root.val+" ");
        inOrderTraversal(root.right);
    }

后序遍歷(LRN):順序：根的左子樹–》根的右子樹–》根節點

//后序遍歷
    void postOrderTraversal(Node root){
        if (root == null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.println(root.val+" ");
    }

五.基本操作（重點）

求節點個數

//遍歷思路求樹的節點個數(按照前序遍歷的順序)
    static int size = 0;
    void getSize1(Node root){
        if (root == null)return;
        size++;
        getSize1(root.left);
        getSize1(root.right);
    }

    //子問題思想，求節點個數（先算左邊，在算右邊，最后加起來在加根節點的一）
    int getSize2(Node root){
        if (root == null)return 0;
        int left = getSize2(root.left);
        int right = getSize2(root.right);
        return left+right+1;
    }

求葉子節點個數（度為0的是葉子節點）

//遍歷思路
    static int leafsize = 0;
    public void getLeafSize1(Node root){
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafsize++;
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

//子問題思路--求葉子節點的個數
    public int getLeafSize2(Node root){
        if (root == null)return 0;
        if (root.left == null && root.right == null)
            return 1;
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

求第k層的節點個數

//子問題思路--求第k層的節點個數
    int getLevelSize (Node root,int k){
        if (root == null)return 0;
        if (k == 1)return 1;
        return getLevelSize(root.left,k-1)+getLevelSize(root.right,k-1);
    }

求樹的深度（左子樹和右子樹深度的最大值，再加上根節點的1）

//子問題思路--求樹的深度
    int getHeight(Node root){
        if (root == null)return 0;
        /*int left = getHeight(root.left;
        int right = getHeight(root.right);
        return Math.max(left,right)+1
        */
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }

查找 val 所在節點

/*查找 val 所在結點，沒有找到回傳 null
     按照 根 -> 左子樹 -> 右子樹的順序進行查找
     一旦找到，立即回傳，不需要繼續在其他位置查找*/
    Node find(Node root, int val){
        if (root == null)return null;
        if (root.val == val)return root;
        Node newroot =find(root.left,val);
        if (newroot != null){
        return newroot;}
        Node newroot1 = find(root.right,val);
        if (newroot1 != null){
            return newroot1;
        }
        return null;
    }

完整運行代碼

import java.lang.Math;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
/*
孩子表示法
 */
class Node {
    char val;
    Node left;
    Node right;
    //構造方法
    public Node(char val) {
        this.val = val;
    }
}
public class BinaryTree {
    //構造一顆樹
    public  Node createTree(){
          Node A = new Node('A');
          Node B = new Node('B');
          Node C = new Node('C');
          Node D = new Node('D');
          Node E = new Node('E');
          Node F = new Node('F');
          Node G = new Node('G');
          Node H = new Node('H');
          A.left = B;
          A.right = C;
          B.left = D;
          B.right = E;
          E.right = H;
          C.left = F;
          C.right = G;
          return A;
      }
  
    //前序遍歷
    void preOrderTraversal(Node root){
        if (root == null)return;
        System.out.print(root.val+" ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }
    //中序遍歷
    void inOrderTraversal(Node root){
        if (root == null)return;
        inOrderTraversal(root.left);
        System.out.print(root.val+" ");
        inOrderTraversal(root.right);
    }
    //后序遍歷
    void postOrderTraversal(Node root){
        if (root == null)return;
        postOrderTraversal(root.left);
        postOrderTraversal(root.right);
        System.out.print(root.val+" ");
    }


    static int size = 0;
    //子問題思想，求節點個數（先算左邊，在算右邊，最后加起來在加根節點的一）
    int getSize2(Node root){
        if (root == null)return 0;
        int left = getSize2(root.left);
        int right = getSize2(root.right);
        return left+right+1;
    }

    //遍歷思路求節點個數
    void getSize1(Node root){
        if (root == null)return;
        size++;
        getSize1(root.left);
        getSize1(root.right);

    }


    //子問題思路--求葉子節點的個數
    public int getLeafSize2(Node root){
        if (root == null)return 0;
        if (root.left == null && root.right == null)
            return 1;
        return getLeafSize2(root.left)+getLeafSize2(root.right);
    }

    //遍歷思路
    static int leafsize = 0;
    public void getLeafSize1(Node root){
        if (root == null) return;
        if (root.left == null && root.right == null)
            leafsize++;
        getLeafSize1(root.left);
        getLeafSize1(root.right);
    }

    //子問題思路--求第k層的節點個數
    int getLevelSize (Node root,int k){
        if (root == null)return 0;
        if (k == 1)return 1;
        return getLevelSize(root.left,k-1)+getLevelSize(root.right,k-1);
    }

    //子問題思路--求樹的深度
    int getHeight(Node root){
        if (root == null)return 0;
        /*int left = getHeight(root.left;
        int right = getHeight(root.right);
        return Math.max(left,right)+1
        */
        return Math.max(getHeight(root.left),getHeight(root.right))+1;
    }
    /*查找 val 所在結點，沒有找到回傳 null
     按照 根 -> 左子樹 -> 右子樹的順序進行查找
     一旦找到，立即回傳，不需要繼續在其他位置查找*/
    Node find(Node root, int val){
        if (root == null)return null;
        if (root.val == val)return root;
        Node newroot =find(root.left,val);
        if (newroot != null){
        return newroot;}
        Node newroot1 = find(root.right,val);
        if (newroot1 != null){
            return newroot1;
        }
        return null;
    }

//測驗類
class TestDemo{
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();//創建物件
        Node root = binaryTree.createTree();//構造一棵樹，通過呼叫BinaryTree類里面的createTree()方法
        System.out.print("前序遍歷:");
        binaryTree.preOrderTraversal(root);
        System.out.println();
        System.out.print("中序遍歷:");
        binaryTree.inOrderTraversal(root);
        System.out.println();
        System.out.print("后序遍歷:");
        binaryTree.postOrderTraversal(root);
        System.out.println();

        binaryTree.getSize1(root);
        System.out.println("樹的節點個數:"+binaryTree.size);
        System.out.println("樹的節點個數:"+binaryTree.getSize2(root));
        System.out.println();
        binaryTree.getLeafSize1(root);
        System.out.println("葉子節點個數:"+binaryTree.leafsize);
        System.out.println("葉子節點個數:"+binaryTree.getLeafSize2(root));
        System.out.println();
        System.out.println("第k層的節點個數:"+binaryTree.getLevelSize(root, 3));
        System.out.println();

        System.out.println("樹的深度:"+binaryTree.getHeight(root));
        System.out.println();
        Node root1 = binaryTree.find(root, 'A');
        System.out.println(root1.val);
        Node root2 = binaryTree.find(root, 'H');
        System.out.println(root2.val);
        Node root3 = binaryTree.find(root, 'l');
        if (root3 == null){
            System.out.println(root3);
        }else{
            System.out.println(root.val);
        }
        }
        }

結果

前序遍歷:A B D E H C F G 
中序遍歷:D B E H A F C G 
后序遍歷:D H E B F G C A 
樹的節點個數:8
樹的節點個數:8

葉子節點個數:4
葉子節點個數:4

第k層的節點個數:4

樹的深度:4

A
H
null

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

標籤：python

上一篇：[Java筆記]day13

下一篇：設計模式理解與實作（1）—— 單例模式

二叉樹入門

二叉樹