Recursive Definitions Definition A rooted tree consists of a single vertex V, called the root of the tree, together with a forest F whose trees are called the subtrees of the root A forest F is a (possibly empty) set of rooted trees Definition An ordered tree T consists of a single vertex v, called the root of the tree, together with an orchard o whose trees are called the subtrees of the root v We may denote the ordered tree with the ordered pair T=vON An orchard o is either the empty set ;, or consists of an ordered tree T, called the first tree of the orchard, together with another orchard o(which contains the remaining trees of the orchard). We may denote the orchard with the ordered pair O=(T, O)
Recursive Definitions Definition A rooted tree consists of a single vertex v, called the root of the tree, together with a forest F , whose trees are called the subtrees of the root. A forest F is a (possibly empty) set of rooted trees. Definition An ordered tree T consists of a single vertex v, called the root of the tree, together with an orchard O,whose trees are called the subtrees of the root v. We may denote the ordered tree with the ordered pair T = {v,O}. An orchard O is either the empty set ;, or consists of an ordered tree T , called the first tree of the orchard, together with another orchard O’ (which contains the remaining trees of the orchard). We may denote the orchard with the ordered pair O = (T ,O’)
FIrst tree Orchard of I remalnIng Orchard of subtree --------=---- Adjoin Delete new Toot Ordered tree Orchard Ordered tree
4. The Formal Correspondence Definition a binary tree B is either the empty set; or consiste 数学归纳法 ot vertex v with two binary trees B1 and B2.c ray denote the binary tree with the ordered trip B=[v; B1; B2 Theorem 11.1 LS be any finite set of vertices.There is a one-to-one c rrespondence f from the set of orchards whose st t of vertices is s to the set of binary trees whose et of vertices is S Proof. Define f (o)=( Define f(V, 013, O)=[v, f(O,), f(O2)1 Show by mathematical induction on the number of vertices that fis a one-to-one correspondence
4. The Formal Correspondence Definition A binary tree B is either the empty set ; or consists of a root vertex v with two binary trees B1 and B2 . We may denote the binary tree with the ordered triple B = [v;B1;B2]. Theorem 11.1 Let S be any finite set of vertices. There is a one-to-one correspondence f from the set of orchards whose set of vertices is S to the set of binary trees whose set of vertices is S. Proof. Define f () = Define f ({v,O1 },O2 ) = [ v,f(O1 ) ,f(O2 ) ] Show by mathematical induction on the number of vertices that f is a one-to-one correspondence. 数学归纳法
5 Rotations e Draw the orchard so that the first child of each vertex is immediately below the vertex. . Draw a vertical link from each vertex to its first child and draw a horizontal link from each vertex to its next sibling o Remove the remaining original links o Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links Rotate 45 Orchard Colored links added broken lInks removed BInary tree
5.Rotations • Draw the orchard so that the first child of each vertex is immediately below the vertex. • Draw a vertical link from each vertex to its first child, and draw a horizontal link from each vertex to its next sibling. • Remove the remaining original links. • Rotate the diagram 45 degrees clockwise, so that the vertical links appear as left links and the horizontal links as right links
6. Summary Orchards and binary trees correspond by any of o first child and next sibling links o rotations of diagrams, o formal notational equivalence
6. Summary Orchards and binary trees correspond by any of: • first child and next sibling links, • rotations of diagrams, • formal notational equivalence