Skip to main content

数据结构-非线性结构-树

{t∈T: 0≤Deg(t)<∣T∣}\{t \in T:\space 0 \le Deg(t) < |T|\}

概念​

  • parent
  • child
  • sibling
  • leaf
  • inode
  • level
  • depth
  • sort

存储结构​

  • parent
    • T:{data:any,parent:number}[]
  • child
    • T:{data:any,child:number[]|undefined}[]
  • parent-child
    • T:{data:any,parent:number,child:number[]}[]
  • child-sibling
    • T:{data:any,nextchild:number,nextsiblin:number}[]

推广​

二叉树​

{t∈T: 2≤deg(t)<∣T∣}\{t \in T:\space 2 \le deg(t) < |T|\}

分类​

  • rooted
    • ∀t∈T, deg(t)≤2\forall t \in T,\space deg(t) \le 2
  • full
    • ∀t∈T, deg(t)∈{0,2}\forall t \in T,\space deg(t) \in \{0,2\}
  • perfect
    • ∀t∈T, deg(t)=2\forall t \in T,\space deg(t)=2
  • complete
  • infinite complete
  • balanced
    • ∀t∈T, ∣height(lchild(t))−height(rchild(t))∣le1\forall t \in T,\space |height(lchild(t))-height(rchild(t))|le1
  • degenerate
    • ∀t∈T, deg(t)∈{0,1}\forall t \in T,\space deg(t)\in \{0,1\}

存储结构​

  • 🧵
    • T:any[]
      • ∣T∣=∣{t∈T: t≠ϕ}∣len(T)=∣{t,t∈T}∣|T|=|\{t \in T: \space t \ne \phi\}| \\ len(T)=|\{t,t \in T\}|
      • ∀ ti∈Tif i=0⇒root(T)=ti if i>1⇒parent(ti)=⌊i÷2⌋if lchild(ti)=tk⇒k={2i2i≤∣T∣ϕ2i>∣T∣if rchild(ti)=tk⇒k={2i+12i+1≤∣T∣ϕ2i+1>∣T∣\forall \space t_i \in T \\ if \space i=0 \rArr root(T) = t_i \space \\ if \space i>1 \rArr parent(t_i) = \lfloor i \div 2 \rfloor \\ if \space lchild(t_i)=t_k \rArr k=\begin{cases} 2i && 2i \le |T| \\ \phi && 2i > |T| \end{cases} \\ if \space rchild(t_i)=t_k \rArr k=\begin{cases} 2i+1 && 2i+1 \le |T| \\ \phi && 2i+1 > |T| \end{cases} \\
      • ∃T, depth(T)=∣T∣=k⇒len(T)=2k−1\exists T,\space depth(T)=|T|=k \rArr len(T)=2^k-1
    • Huffman Tree
      T:{ch:char,weight:number,parent:number,lchild:number,rchild:number}[]`}
      • WPL=∑k=1∣{t∈T: deg(t)=0}∣weight(tk)⋅length(tk,t1)WPL=\sum^{|\{t \in T:\space deg(t)=0\}|}_{k=1}weight(t_k) \cdot length(t_k,t_1)
      • {w∈W: ∣W∣≥0}→{t∈T: ∣{t,deg(t)=0}∣=∣W∣}?W→{T∈F: ∣T∣=1, ti∈T=wi}T′={f(F)={wi+wj,ti,tj}, wi=Fmin,wj=Fmin∣F∣>1F1∣F∣=1\{w \in W:\space |W|\ge0\} \to \{t \in T:\space |\{t,deg(t)=0\}|=|W|\}? \\ W \to \{T \in F:\space |T|=1,\space t_i \in T=w_i\} \\ T'=\begin{cases} f(F)=\{w_i+w_j,t_i,t_j\},\space w_i=F_{min},w_j=F_{min} && |F|>1\\ F_1 && |F| =1 \end{cases}
  • ⛓ 
    • T:{lchild:number|null,data:any,rchild:number|null}[]
    • T:{lchild:numbre|null.data:any,parent:number|null,rchild:number}[]
    • T:{ltag:0|1,lchild:numbre|null.data:any,parent:number|null,rchild:number,rtag:0|1}[]
      • ∀t∈Tlchild(t)={lchild(t)ltag=0predecessor(t)ltag=1rchild(t)={rchild(t)rtag=0successor(t)rtag=1\forall t \in T \\ lchild(t)=\begin{cases} lchild(t) && ltag=0 \\predecessor(t) && ltag=1 \end{cases} \\ rchild(t)=\begin{cases} rchild(t) && rtag=0 \\successor(t) && rtag=1 \end{cases}