CHAPTER 4 8 1 Preliminaries TREES 1. Terminology Pedigree Tree binary tree Lineal Tree
CHAPTER 4 TREES §1 Preliminaries 1. Terminology Lineal Tree Pedigree Tree ( binary tree )
Definition A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root (2) and zero or more nonempty(sub)trees T1,., Tk, each of whose roots are connected by a directed edge from r Note Subtrees must not connect together. Therefore every node in the tree is the root of some subtree There are N-1 edges in a tree with N nodes > Normally the root is drawn at the top
【Definition】A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of (1) a distinguished node r, called the root; (2) and zero or more nonempty (sub)trees T1 , , Tk , each of whose roots are connected by a directed edge from r. Note: ➢ Subtrees must not connect together. Therefore every node in the tree is the root of some subtree. ➢ There are edges in a tree with N nodes. ➢ Normally the root is drawn at the top. N − 1
degree of a node: : =number of subtrees of the node. For exam ple, degree(A)=3, degree(F)=0 ③⑦ o degree of a tree: =nomeree degree(node ⑥⑥⑥⑦ For example, degree of this tree= 3 o' parent: : =a node that has subtrees e children ::=the roots of the subtrees of a parent s siblings =children of the same parent leaf terminal node): = a node with degree o(no children)
A B C D E F G H I J K L M degree of a node ::= number of subtrees of the node. For example, degree(A) = 3, degree(F) = 0. degree of a tree ::= For example, degree of this tree = 3. max degree(node ) nodetree leaf ( terminal node ) ::= a node with degree 0 (no children). parent ::= a node that has subtrees. children ::= the roots of the subtrees of a parent. siblings ::= children of the same parent
a' path from n, to nk:: =a(unique) sequence of nodes n1,n2,……, nk such that n; is the parent of n;+ for Isi<k o' length of path: number of edges or⑥⑥⊙⑤ the path o depth of n; :=length of the unique path from the root to n Depth(root=0 a' height of n; : := length of the longest path from n, to a leaf Height(leaf)=0, and height(D)=2 o' height (depth) of a tree : height(root)=depth (deepest leaf) o' ancestors of a node: = all the nodes along the path from the node up to the root. descendants of a node: =all the nodes in its subtrees
A B C D E F G H I J K L M ancestors of a node ::= all the nodes along the path from the node up to the root. descendants of a node ::= all the nodes in its subtrees. depth of ni ::= length of the unique path from the root to ni . Depth(root) = 0. height of ni ::= length of the longest path from ni to a leaf. Height(leaf) = 0, and height(D) = 2. height (depth) of a tree ::= height(root) = depth(deepest leaf). path from n1 to nk ::= a (unique) sequence of nodes n1 , n2 , …, nk such that ni is the parent of ni+1 for 1 i < k. length of path ::= number of edges on the path
2. Implementation 令 List Representation (A) (A(B,C,D)) o@⑦⑦(A(B(E,F,C(G,D(H,J)) (A(B(E(K,L),F),C(G),D(H(M),L,J))) K F C+G 位M D
2. Implementation ❖ List Representation A B C D E F G H I J K L M ( A ) ( A ( B, C, D ) ) ( A ( B ( E, F ), C ( G ), D ( H, I, J ) ) ) ( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) ) A B C D E F G H I J K L M