歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

數據結構:樹和二叉樹定義和術語

1、樹的對象
 具有相同特性的數據元素的集合
2、關系
 如果沒有對象叫做空樹
 否則:
 在存在唯一的成為根的數據元素root
當元素個數大於1的時候,其他節點可以
 分為互不相交的樹,成為根root的子樹
        a
  b      c    d
 e f    g   
        i  j 
   
 b c d 叫做a為root節點的子樹
e f 叫做以b為root節點的子樹
 以此類推
3、相關術語
 結點:數據元素+若干指向子樹的分支
      如上數據元素a+指向子樹b c d的指針叫做結點
 結點的度:分支的個數 比如a的度就為3
樹的度:所有結點的度的最大值
 葉子結點:度為0的結點
 分支結點:度大約0的結點,也就是葉子結點以外的
          特殊的就是root根結點
 從根到結點的路徑:從根到結點所經歷的分支和結點構成


 孩子結點:子樹的根對於樹的根叫做孩子結點
 雙親結點:樹的根對於子樹的根叫做雙親結點
 兄弟結點:有相同根的子樹叫做兄弟結點
 祖先節點:從根到結點之間的全部節點叫做祖先節點
 子孫節點:一個根下的所有的節點叫做子孫節點


 結點的層次:角色根結點的層次為1,第L層的節點的子樹
            根結點的層次是L+1層
樹的深度:樹中葉子節點所在的最大層次
 如上例子:第3層的i的層次為3+1=4層,整個樹的深度為4


森林:是多棵互不相交的樹的集合,從定義可以看出,如果一棵樹去掉root根結點明顯他
      就是一個森林,如果一個森林加上一個root結點那麼就是一棵樹

 


 有向樹:
1、有確定的根
2、樹根和子樹根之間為有向關系


 一般討論無序樹,同一個層次之間無序

 


 和線性表的區別:
 第一個元素無前驅 根結點無前驅
 最後一個數據元素 多個葉子結點
 無後繼          無後繼
 其他數據元素    樹中其他節點
 一個前驅,      一個前驅、多個後繼
 一個後繼


 由於樹的不確定性和復雜性我們一般討論二叉樹
 二叉樹
 定義:
 二叉樹或為空樹;或者由一個根結點加上
 兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成
 並且一個根結點有且只有兩個子樹為左子樹和右子樹


      A
  B            E
 C            F
  D            G
              H  K
左子樹    右子樹


 二叉樹2種形態
1、空樹
2、只有根結點的樹
3、左子樹非空右子樹空
4、左子樹空右子樹非空
5、都不為空


 對於3和4不同二叉樹必須明確是左子樹為空還是右子樹為空,雖然
 只有一個子樹但是必須明確是左子樹還是右子樹


 重要特性:
1、在二叉樹的第i層上最多有2^(i-1)個結點(i>=1)
 2、深度為h的樹結點樹最多為2^h-1 
 3、對於任何一棵二叉樹,如果他含有n0個葉子節點,
  n2個度為2的節點,這必然存在關系n0=n2+1
注:二叉樹有3種節點:n0代表度為0的節點
    n1代表度為1的節點
                    n2代表度為2的節點
                    n0+n1+n2=n 總的結點
                    b為分支數量
                    n=b+1=1+n1+2n2
                      及:1+n1+2n2=n0+n1+n2
                      及:n0=n2+1
滿二叉樹:深度為k的樹含有2^k-1個結點,其實就是在一棵樹中
          不包含度為1的節點的樹,只有深度為k的層末尾節點
          才為葉子結點
 完全二叉樹:如果給滿二叉樹編號,按照編號一一對應的一棵樹
            及知道結點個數就知道樹的結構,且如果無左孩子
            結點那麼它就是葉子結點
 如:
        1
    2        3
  4  5    6  7
為滿二叉樹
        1
    2        3
  4  5    6 
為完全二叉樹
        1
    2        3
      4    5
不為完全二叉樹


 關於完全二叉樹的特性:
1、具有n個結點的完全二叉樹的深度為 [log2 n]+1
    符號[]為不大於log2 n的最大整數
2、如果i=1,則結點i是二叉樹的根,無雙親,如果i>1,
  這其雙親parent(i)結點為[i/2]
 3、如果2i>n則結點i無左孩子,否則左孩子是節點2i
 4、如果2i+1>n則結點無右孩子,否則其右孩子是節點2i+1

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

根據二叉樹的前序數組和中序序遍歷數組生成二叉樹 http://www.linuxidc.com/Linux/2016-09/135514.htm

後序遍歷求解判斷一顆二叉樹是否為平衡二叉樹 http://www.linuxidc.com/Linux/2016-08/134054.htm

判斷二叉樹是否為完全二叉樹 http://www.linuxidc.com/Linux/2016-08/134050.htm

求二叉樹中兩個節點的最遠距離 http://www.linuxidc.com/Linux/2016-08/134049.htm

Copyright © Linux教程網 All Rights Reserved