6.2 The Parent Pointer Implementation Parent Pointer Implementation Advantages: Can answer the following question easily: Given two or more nodes, are they in the same tree? Disadvantages It is inadequate for such important operations as finding the leftmost child or the right sibling For a node B Parent' s Index 001112 777 LabelRABCDEFWXYZ Node Index012345678910
Parent Pointer Implementation Advantages: Can answer the following question easily: Given two or more nodes, are they in the same tree? Disadvantages: It is inadequate for such important operations as finding the leftmost child or the right sibling for a node. 6.2 The Parent Pointer Implementation
6.2 The Parent Pointer Implementation ADT for parent pointer implementation Class parptrfree i Private int大 array; int SiZe int FIND(int) const;//Find root Public Parptrtree(int)i ParptrTree()delete[] array void UNION (int, int)//Merge equivalences bool differ(intint)//TRUE if not in same tree }
ADT for parent pointer implementation Class ParPtrTree{ Private: int* array; int size: int FIND(int) const;//Find root Public: ParPtrTree(int); ~ParPtrTree(){delete[] array;} void UNION(int,int)//Merge equivalences bool differ(int,int)//TRUE if not in same tree }; 6.2 The Parent Pointer Implementation
6.2 The Parent Pointer Implementation Implementation of Findo int Parptrfree:: FIND (int curr const( While (array[curr!=RooT curr array [curr]i return curr 只 假设根的双亲值为-1,ROOT=-1 B e. g. FIND ( 4) Curr:4->1->0 Parents Index ∠001112 LabelLA CDEF Node Index 0 23456
Implementation of Find() int ParPtrTree::FIND(int curr) const{ while (array[curr]!=ROOT) curr = array[curr]; return curr; } 假设根的双亲值为-1，ROOT=-1. e.g. FIND(4) curr: 4->1->0 6.2 The Parent Pointer Implementation