hello，今天帶大家學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)中非常重要的一個(gè)知識(shí)點(diǎn)二叉樹(shù)，二叉樹(shù)主體的實(shí)現(xiàn)使用的是遞歸的知識(shí)，通過(guò)二叉樹(shù)我們可以更好的理解遞歸的應(yīng)用。今天就帶大家學(xué)習(xí)一下二叉樹(shù)的一些知識(shí)。

二叉樹(shù)的概念

概念：
樹(shù)是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個(gè)有限結(jié)點(diǎn)組成一個(gè)具有層次關(guān)系的集合。把它叫做樹(shù)是因?yàn)樗雌饋?lái)像一棵倒掛的樹(shù)，也就是說(shuō)它是根朝上，而葉朝下的。它具有以下的特點(diǎn)。

• 有一個(gè)特殊的結(jié)點(diǎn)，稱為根結(jié)點(diǎn)，根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)

• 除根結(jié)點(diǎn)外，其余結(jié)點(diǎn)被分成M(M > 0)個(gè)互不相交的集合T1、T2、…、Tm，其中每一個(gè)集合Ti (1 <= i <=
  m) 又是一棵與樹(shù)類似的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且只有一個(gè)前驅(qū)，可以有0個(gè)或多個(gè)后繼

• 樹(shù)是遞歸定義的。

二叉樹(shù)的節(jié)點(diǎn)介紹

• 結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)含有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度； 如上圖：A的度為6

• 樹(shù)的度：一棵樹(shù)中，所有結(jié)點(diǎn)度的最大值稱為樹(shù)的度； 如上圖：樹(shù)的度為6

• 葉子結(jié)點(diǎn)或終端結(jié)點(diǎn)：度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)； 如上圖：B、C、H、I…等節(jié)點(diǎn)為葉結(jié)點(diǎn)

• 雙親結(jié)點(diǎn)或父結(jié)點(diǎn)：若一個(gè)結(jié)點(diǎn)含有子結(jié)點(diǎn)，則這個(gè)結(jié)點(diǎn)稱為其子結(jié)點(diǎn)的父結(jié)點(diǎn)； 如上圖：A是B的父結(jié)點(diǎn)

• 孩子結(jié)點(diǎn)或子結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)含有的子樹(shù)的根結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子結(jié)點(diǎn)； 如上圖：B是A的孩子結(jié)點(diǎn)

• 根結(jié)點(diǎn)：一棵樹(shù)中，沒(méi)有雙親結(jié)點(diǎn)的結(jié)點(diǎn)；如上圖：A

• 結(jié)點(diǎn)的層次：從根開(kāi)始定義起，根為第1層，根的子結(jié)點(diǎn)為第2層，以此類推

• 樹(shù)的高度或深度：樹(shù)中結(jié)點(diǎn)的最大層次； 如上圖：樹(shù)的高度為4
  樹(shù)的以下概念只需了解，在看書(shū)時(shí)只要知道是什么意思即可：

• 非終端結(jié)點(diǎn)或分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)； 如上圖：D、E、F、G…等節(jié)點(diǎn)為分支結(jié)點(diǎn)

• 兄弟結(jié)點(diǎn)：具有相同父結(jié)點(diǎn)的結(jié)點(diǎn)互稱為兄弟結(jié)點(diǎn)； 如上圖：B、C是兄弟結(jié)點(diǎn)

• 堂兄弟結(jié)點(diǎn)：雙親在同一層的結(jié)點(diǎn)互為堂兄弟；如上圖：H、I互為兄弟結(jié)點(diǎn)

• 結(jié)點(diǎn)的祖先：從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)；如上圖：A是所有結(jié)點(diǎn)的祖先

• 子孫：以某結(jié)點(diǎn)為根的子樹(shù)中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫。如上圖：所有結(jié)點(diǎn)都是A的子孫

• 森林：由m（m>=0）棵互不相交的樹(shù)組成的集合稱為森林.

二叉樹(shù)構(gòu)造

那么如何構(gòu)造一個(gè)二叉樹(shù)呢？
實(shí)際中樹(shù)有很多種表示方式，如：雙親表示法，孩子表示法、孩子雙親表示法、孩子兄弟表示法 等等。我們這里就簡(jiǎn)單的了解其中最常用的孩子兄弟表示法

如何使用兄弟表示法構(gòu)造二叉樹(shù)

孩子兄弟法（Child-Sibling Representation）是一種用來(lái)表示樹(shù)的方法，其中每個(gè)節(jié)點(diǎn)都有兩個(gè)子節(jié)點(diǎn)：一個(gè)指向其第一個(gè)孩子節(jié)點(diǎn)，另一個(gè)指向它的下一個(gè)兄弟節(jié)點(diǎn)。這種表示方法可以用來(lái)構(gòu)造二叉樹(shù)，具體步驟如下：

1. 創(chuàng)建一個(gè)類，和一個(gè)頭結(jié)點(diǎn)，結(jié)構(gòu)中包含節(jié)點(diǎn)的值以及指向其第一個(gè)孩子節(jié)點(diǎn)和下一個(gè)兄弟節(jié)點(diǎn)的指針。
2. 為每個(gè)節(jié)點(diǎn)分配內(nèi)存，并設(shè)置節(jié)點(diǎn)的值。
3. 根據(jù)孩子兄弟法的規(guī)則，構(gòu)造二叉樹(shù)：
   遍歷樹(shù)的每個(gè)節(jié)點(diǎn)，對(duì)于每個(gè)節(jié)點(diǎn)，找到它的第一個(gè)孩子節(jié)點(diǎn)和下一個(gè)兄弟節(jié)點(diǎn)。
4. 將第一個(gè)孩子節(jié)點(diǎn)作為其左子節(jié)點(diǎn)，將下一個(gè)兄弟節(jié)點(diǎn)作為其右子節(jié)點(diǎn)。如果沒(méi)有孩子節(jié)點(diǎn)或兄弟節(jié)點(diǎn)，則相應(yīng)的指針為空。
   重復(fù)步驟3，直到樹(shù)的所有節(jié)點(diǎn)都處理完畢。

這里使用孩子兄弟法創(chuàng)建一個(gè)二叉樹(shù):

static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
       //建立一個(gè)簡(jiǎn)單的數(shù)
        public TreeNode creatTree(){
           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;
           C.left=F;
           C.right=G;
           E.right=H;

           return A;
        }

好了，我們之前在學(xué)習(xí)鏈表和順序表的時(shí)候，都涉及到它的基礎(chǔ)操作遍歷這個(gè)數(shù)據(jù)結(jié)構(gòu)，那么在二叉樹(shù)中我們?nèi)绾伪闅v這些節(jié)點(diǎn)呢？

兩種特別的二叉樹(shù)

滿二叉樹(shù)：
一棵二叉樹(shù)，如果每層的結(jié)點(diǎn)數(shù)都達(dá)到最大值，則這棵二叉樹(shù)就是滿二叉樹(shù)。也就是說(shuō)，如果一棵二叉樹(shù)的層數(shù)為K，且結(jié)點(diǎn)總數(shù)是2*k-1 ，則它就是滿二叉樹(shù)。
完全二叉樹(shù)：
完全二叉樹(shù)是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹(shù)是由滿二叉樹(shù)而引出來(lái)的。對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從0至n-1的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完
要注意的是滿二叉樹(shù)是一種特殊的完全二叉樹(shù)。

二叉樹(shù)的基本性質(zhì)：

1. 若規(guī)定根結(jié)點(diǎn)的層數(shù)為1，則一棵非空二叉樹(shù)的第i層上最多有 (i>0)個(gè)結(jié)點(diǎn)
2. 若規(guī)定只有根結(jié)點(diǎn)的二叉樹(shù)的深度為1，則深度為K的二叉樹(shù)的最大結(jié)點(diǎn)數(shù)是 (k>=0)
3. 對(duì)任何一棵二叉樹(shù), 如果其葉結(jié)點(diǎn)個(gè)數(shù)為 n0, 度為2的非葉結(jié)點(diǎn)個(gè)數(shù)為 n2,則有n0＝n2＋1
4. 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度k為log2(n+1) 上取整
5. 對(duì)于具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，如果按照從上至下從左至右的順序?qū)λ泄?jié)點(diǎn)從0開(kāi)始編號(hào)，則對(duì)于序號(hào)為i
   的結(jié)點(diǎn)有：
   若i>0，雙親序號(hào)：(i-1)/2；i=0，i為根結(jié)點(diǎn)編號(hào)，無(wú)雙親結(jié)點(diǎn)
   若2i+1<n，左孩子序號(hào)：2i+1，否則無(wú)左孩子
   若2i+2<n，右孩子序號(hào)：2i+2，否則無(wú)右孩子

二叉樹(shù)的存儲(chǔ)

通常二叉樹(shù)的存儲(chǔ)，我們使用鏈?zhǔn)酱鎯?chǔ)，和順序存儲(chǔ)，今天帶大家使用類似于鏈表的結(jié)構(gòu)實(shí)現(xiàn)二叉樹(shù)。

// 孩子表示法
class Node {
int val; // 數(shù)據(jù)域
Node left; // 左孩子的引用，常常代表左孩子為根的整棵左子樹(shù)
Node right; // 右孩子的引用，常常代表右孩子為根的整棵右子樹(shù)
}

二叉樹(shù)的遍歷：

前序遍歷：

NLR：前序遍歷(Preorder Traversal 亦稱先序遍歷)——訪問(wèn)根結(jié)點(diǎn)—>根的左子樹(shù)—>根的右子樹(shù)

public void preOrder(TreeNode root){
           if(root==null){
               return;
           }
            System.out.print(root.val+ " ");
           preOrder(root.left);
           preOrder(root.right);
        }

中序遍歷：

LNR：中序遍歷(Inorder Traversal)——根的左子樹(shù)—>根節(jié)點(diǎn)—>根的右子樹(shù)。

 //2.中序遍歷
        public void inOrder(TreeNode root){
           if(root==null){
               return;
           }
          inOrder(root.left);
           System.out.println(root.val);
           inOrder(root.right);

        }

后序遍歷：

LRN：后序遍歷(Postorder Traversal)——根的左子樹(shù)—>根的右子樹(shù)—>根節(jié)點(diǎn)。

public void postOrder(TreeNode root){
           if(root==null){
               return;
           }
           postOrder(root.left);
           postOrder(root.right);
            System.out.println(root.val);
        }

• 前序遍歷結(jié)果：1 2 3 4 5 6
• 中序遍歷結(jié)果：3 2 1 5 4 6
• 后序遍歷結(jié)果：3 1 5 6 4 1

層序遍歷

層序遍歷：除了先序遍歷、中序遍歷、后序遍歷外，還可以對(duì)二叉樹(shù)進(jìn)行層序遍歷。設(shè)二叉樹(shù)的根節(jié)點(diǎn)所在層數(shù)為1，層序遍歷就是從所在二叉樹(shù)的根節(jié)點(diǎn)出發(fā)，首先訪問(wèn)第一層的樹(shù)根節(jié)點(diǎn)，然后從左到右訪問(wèn)第2層
上的節(jié)點(diǎn)，接著是第三層的節(jié)點(diǎn)，以此類推，自上而下，自左至右逐層訪問(wèn)樹(shù)的結(jié)點(diǎn)的過(guò)程就是層序遍歷。

二叉樹(shù)的基礎(chǔ)操作

我們介紹了二叉樹(shù)了一些基礎(chǔ)知識(shí)，如何構(gòu)造，如何遍歷二叉樹(shù)，接著我們還要學(xué)習(xí)如何進(jìn)行二叉樹(shù)的基礎(chǔ)操作。

// 獲取樹(shù)中節(jié)點(diǎn)的個(gè)數(shù)
int size(Node root);
// 獲取葉子節(jié)點(diǎn)的個(gè)數(shù)
int getLeafNodeCount(Node root);
// 子問(wèn)題思路-求葉子結(jié)點(diǎn)個(gè)數(shù)
// 獲取第K層節(jié)點(diǎn)的個(gè)數(shù)
int getKLevelNodeCount(Node root,int k);
// 獲取二叉樹(shù)的高度
int getHeight(Node root);
// 檢測(cè)值為value的元素是否存在
Node find(Node root, int val);
//層序遍歷
void levelOrder(Node root);

這里的代碼比較簡(jiǎn)單，我們都使用遞歸實(shí)現(xiàn)，遞歸的代碼相對(duì)來(lái)說(shuō)比較簡(jiǎn)單的去理解，主要需要我們多多畫(huà)圖，理解這個(gè)遞歸的整個(gè)過(guò)程。
我把自己實(shí)現(xiàn)的代碼給大家，有問(wèn)題的話大家私信我哦~~~

public class TestBinaryTree {
    //建立一個(gè)二叉樹(shù)的基本信息
   static class TreeNode {
        public char val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
       //建立一個(gè)簡(jiǎn)單的數(shù)
        public TreeNode creatTree(){
           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;
           C.left=F;
           C.right=G;
           E.right=H;

           return A;
        }
        //樹(shù)的一些基本操作
        //1.前序遍歷
        public void preOrder(TreeNode root){
           if(root==null){
               return;
           }
            System.out.print(root.val+ " ");
           preOrder(root.left);
           preOrder(root.right);
        }

        //2.中序遍歷
        public void inOrder(TreeNode root){
           if(root==null){
               return;
           }
          inOrder(root.left);
           System.out.println(root.val);
           inOrder(root.right);

        }
        //3.后續(xù)排序
        public void postOrder(TreeNode root){
           if(root==null){
               return;
           }
           postOrder(root.left);
           postOrder(root.right);
            System.out.println(root.val);
        }
        //獲取數(shù)的節(jié)點(diǎn)個(gè)數(shù)
        public int size(TreeNode root){
           if(root==null){
               return -1;
           }
           int ret=size(root.left)+size(root.right)+1;
           return ret;
        }
        public static int nodeSize;
        public void size2(TreeNode root) {
            if (root == null){
                return ;
            }
            nodeSize++;
            size2(root.left);
            size2(root.right);
        }
        //求葉子節(jié)點(diǎn)的個(gè)數(shù)
        public int getLeafNodeCount(TreeNode root){
            if(root==null){
                return -1;
            }
            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);
         }
     }

好了今天就帶大家學(xué)習(xí)這么多，下次帶大家做幾道二叉樹(shù)的算法題，讓大家對(duì)二叉樹(shù)有一個(gè)更深刻的認(rèn)識(shí)。謝謝大家~~~

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-844543.html

到了這里，關(guān)于【java數(shù)據(jù)結(jié)構(gòu)-二叉樹(shù)(上)】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！