CS计算机代考程序代写 data structure c++ algorithm Trees

Trees
Overview
• Trees
• Search Trees
References
• Bruno R. Preiss: Data Structures and Algorithms with Object-Oriented Design Patterns in C++. John Wiley & Sons, Inc. (1999)
• Richard F. Gilberg and Behrouz A. Forouzan: Data Structures – A Pseudocode Approach with C. 2nd Edition. Thomson (2005)
• Stanley B. Lippman, Josée Lajoie, and Barbara E. Moo: C++ Primer. 4th Edition. Addison-Wesley (2006)
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction to Algorithms. 2nd Edition. The MIT Press (2001)
348
© Dr Markus Lumpe, 2021

Basics
• A tree T is a finite, non-empty set of nodes, T = {r} ⋃ T1 ⋃ T2 ⋃ … ⋃ Tn,
with the following properties:
A designated node of the set, r, is called the root The remaining nodes are partitioned into n ≥ 0
•
of the tree.
•
subsets T1, T2, …, Tn, each of which is a tree.
349
© Dr Markus Lumpe, 2021

Parent, Children, and Leaf
• The root node r of tree T is the parent of all the roots ri of the subtrees Ti, 1 < i ≤ n. • Each root ri of subtree Ti of tree T is called a child of r. • A leaf node is a tree with no subtrees. 350 © Dr Markus Lumpe, 2021 Tree Examples TA: A TB: B TC: D TA = {A} TB = {B, {C}} TC = {D, {E, {H}}, {F, {G,{I}}, {J, {K}, {L}}}} CEF HG J IKL 351 © Dr Markus Lumpe, 2021 Degree • The degree of a node is the number of subtrees associated with that node. For example, the degree of TC = {D, {E, {H}}, {F, {G,{I}}, {J, {K}, {L}}}} is 2. • A node of degree zero has no subtrees. Such a node is called a leaf. For example, the leaves of TC are {H, I, K, L}. • Two roots ri and rj of distinct subtrees Ti and Tj with the same parent in tree T are called siblings. For example, Ti = {G, {I}} and Tj = {J, {K}, {L}} are siblings in TC. 352 © Dr Markus Lumpe, 2021 Path and Path Length • Given a tree T containing the set of nodes R, a path in T is defined as a non-empty sequence of nodes P = {r1, r2, ..., rk} where ri ∈ R, for 1 ≤ i ≤ k such that the ith node in the sequence, ri, is the parent of the (i+1)th node in the sequence ri+1. • The length of path P is k-1, which corresponds to the distance from the root ri to the leaf rk. 353 © Dr Markus Lumpe, 2021 Depth and Height •Thedepthofanoderi ∈RinatreeTisthe length of the unique path in T from its root to the node ri. • The height of a node ri ∈ R in a tree T is the length of the longest path from node ri to a leaf. Therefore, the leaves are all at height zero. • The height of a tree T is the height of its root node r. 354 © Dr Markus Lumpe, 2021 Nodes With the Same Degree • The general case allows each node in a tree to have a different degree. We now consider a variant of trees in which each node has the same degree. • Unfortunately, it is not possible to construct a tree that has a finite number of nodes which all have the same degree N, except the trivial case N = 0. • We need a special notation, called empty tree, to realize trees in which all nodes have the same degree. 355 © Dr Markus Lumpe, 2021 N-ary Trees • An N-ary tree T, N ≥ 1, is a finite set of nodes with one of the following properties: Either the set is empty, T = ∅, or • The set consists of a root, R, and exactly N distinct • N-ary trees, That is, the remaining nodes are partitioned into N ≥ 1 subsets, T1, T2, ..., TN, each of which is an N-ary tree such that T = {R, T1, T2, ..., TN}. 356 © Dr Markus Lumpe, 2021 N-ary Tree Examples TA: N = 3 A TB: N= 4 D EF G TA = {A, ∅ , ∅ , ∅ } TB = {D, {E, ∅ , ∅ , ∅ , ∅ }, ∅ , {F, {G, ∅ , ∅ , ∅ , ∅ }, ∅ , ∅ , ∅ }, ∅ } 357 © Dr Markus Lumpe, 2021 The Empty Tree • The empty tree, T = ∅, is a tree. • From the modeling point of view an empty N-ary tree has no key and has to have the same type as a non-empty N-ary tree. • To use null (i.e., nullptr) to denote an empty N-ary tree is inappropriate, as null refers to nothing at all! 358 © Dr Markus Lumpe, 2021 Sentinel Node: NIL • A sentinel node is a programming idiom used to facilitate tree-based operations. • A sentinel node in tree structures indicates a node with no children. • Sentinel nodes behave like null-pointers. However, unlike null-pointers, which refer to nothing, sentinel nodes denote proper, yet empty, subtrees. 359 © Dr Markus Lumpe, 2021 Class Template NTree
We do not wish to allow clients to create empty NTrees.
360
© Dr Markus Lumpe, 2021

The Private NTree Constructor
• We use T(), the default constructor for type T, to initialize the fKey.
• Each subtree-node is set to to the location of NIL, the sentinel node
for NTree.
• This constructor is solely being used to set up the sentinel for NTree. Clients should and cannot use the default constructor.
361
© Dr Markus Lumpe, 2021

The Public NTree Constructors
• We copy (or move) aKey into fKey.
• Each child node in a non-empty NTree leaf node is set to the
location of NIL, the sentinel node for NTree. 362
© Dr Markus Lumpe, 2021

The NTree Destructor
• In the destructor of NTree only non-sentinel nodes are destroyed.
363
© Dr Markus Lumpe, 2021

The NTree Sentinel
• Static instance variables, like the NTree sentinel NIL, need to be initialized outside the class definition.
• Here, NIL is initialized using the private default constructor.
• The scope of NIL is NTree, which means that all members of NTree are available, including the private constructor to initialize NIL.
364
© Dr Markus Lumpe, 2021

The NTree Auxiliaries
• A tree of type NTree is empty if it is equal to the sentinel NIL.
• The dereference operator returns the payload (i.e., the root) of a NTree tree. (We can use NIL as temporary storage.)
365
© Dr Markus Lumpe, 2021

Attaching a New Subtree
366
© Dr Markus Lumpe, 2021

Accessing a Subtree
• We return a reference to the subtree rather than a pointer. This way, we prevent accidental manipulations outside the tree structure.
367
© Dr Markus Lumpe, 2021

2-ary Trees: Binary Trees
• A binary tree T is a finite set of nodes with one of the following properties:
Either the set is empty, T = ∅, or
The set consists of a root, r, and exactly 2 distinct
binary trees TL and TR, T = {r, TL, TR}.
• The tree TL is called the left subtree of T and
the tree TR is called the right subtree of T.
• •
370
© Dr Markus Lumpe, 2021

Related Posts