歡迎關注個人主頁：逸狼

---

創造不易，可以點點贊嗎~

如有錯誤，歡迎指出~

---

---

樹結構

樹是一種非線性的數據結構，它是由n（n>=0）個有限結點組成一個具有層次關系的集合

注意：樹形結構中，子樹之間不能有交集，否則就不是樹形結構

常見概念?

?節點的度：一個節點含有子樹的個數，如A的度為6

樹的度：一顆樹所有節點的度的最大值，如上圖中樹的度為6

葉子節點（終端節點）：度為0的節點，如P,Q節點

父節點（雙親節點）：有子節點的節點，如A是B的父節點

子節點（孩子節點）：與父節點相反，如B是A的子節點

根節點：沒有父節點的節點，如A

節點的層次：從根節點為第1層 ，往下數，以此類推。

樹的高度：樹的最大層次數，如上圖樹的高度為4

樹的應用

?二叉樹

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

?注意：每個節點最多有兩顆子樹，且有左右之分。

?二叉樹的各種情況

滿二叉樹 與 完全二叉樹

滿二叉樹：每層的節點都達到最大值。（若滿二叉樹的層數為k,則節點個數為2^K-1）

完全二叉樹：每一層從左到右數，直到最后一個節點的前面必須是滿的。(滿二叉樹是特殊的完全二叉樹)

二叉樹的性質：

前、中、后、層序遍歷

前序遍歷：根、左、右

中序遍歷：左、根、右

后序遍歷：左、右、根

層序遍歷：從上到下，從左到右，依次遍歷?

創建二叉樹

二叉樹的節點

public class TestBinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val=val;}}
}

?手動搭建一個二叉樹

    public TreeNode createTree(){TreeNode A=new TreeNode('A');TreeNode B=new TreeNode('B');TreeNode C=new TreeNode('C');TreeNode D=new TreeNode('D');TreeNode E=new TreeNode('E');TreeNode F=new TreeNode('F');TreeNode G=new TreeNode('G');TreeNode H=new TreeNode('H');A.left=B;A.right=C;B.left=D;B.right=E;E.right=H;C.left=F;C.right=G;return A;}

    public void preOrder (TreeNode root){if(root==null){return;}System.out.print(root.val+" ");//遞歸遍歷左子樹preOrder(root.left);//遞歸遍歷右子樹preOrder(root.right);}public void inOrder(TreeNode root){if(root==null){return;}inOrder(root.left);System.out.print(root.val+" ");inOrder(root.right);}public void postOrder(TreeNode root){if(root==null){return;}postOrder(root.left);postOrder(root.right);System.out.print(root.val+" ");}

測試

        TestBinaryTree testBinaryTree=new TestBinaryTree();TestBinaryTree.TreeNode root= testBinaryTree.createTree();testBinaryTree.preOrder(root);System.out.println();testBinaryTree.inOrder(root);System.out.println();testBinaryTree.postOrder(root);

根據 前序遍歷 和 中序遍歷

或者 后序遍歷 和 中序遍歷 可以創建二叉樹

而 前序 和 后序 不能

獲取整棵樹的節點數size

子問題思路

左子樹節點數+右子樹節點數+1=整棵樹的

    //求整個樹的節點個數public int size(TreeNode root){if(root==null){return 0;}int ret=size(root.left)+size(root.right)+1;return ret;}

遍歷思路

每遍歷一個節點就++

//遍歷思路public int nodeSize;public void size2(TreeNode root){if(root==null){return;}nodeSize++;size2(root.right);size2(root.left);}

求葉子節點的個數

子問題思路

?整棵樹的葉子節點個數=左樹的+右樹的

    public  int getLeafNodeCount(TreeNode root){if (root==null){return 0;}if (root.right==null&&root.left==null){return 1;}return getLeafNodeCount(root.right)+getLeafNodeCount(root.left);}

?遍歷思路

    public  int leafSize;public void getLeafNodeCount2(TreeNode root) {if(root == null) {return ;}if(root.left == null && root.right == null) {leafSize++;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}

?計算第k層有多少個節點

已知前提：k是合法的

public int getKLevalNodeCount(TreeNode root,int k){if(root==null){return 0;}if(k==1){return 1;}return getKLevalNodeCount(root.left,k-1)+getKLevalNodeCount(root.right,k-1);}

?求樹的高度

整棵樹的高度=Math.max(左樹的高度和右樹高度)+1

    //求樹的高度public int getHeight(TreeNode root){if(root==null){return 0;}int leftHeight=getHeight(root.left);int rightHeight=getHeight(root.right);
//        return Math.max(leftHeight,rightHeight)+1;return leftHeight>rightHeight?leftHeight+1:rightHeight+1;}

找值為val的節點

//    找值為val的節點public TreeNode find(TreeNode root,char val){if(root==null){return null;}if(root.val==val){return root;}TreeNode ret=find(root.left,val);if(ret!=null){return ret;}ret=find(root.right,val);if(ret!=null){return ret;}return null;}