6. 1 General Tree Definitions and Terminology General trees Root Ancestors of v Parent of∨ S1 S2 C1 C2 C3 Siblings of∨ Subtree rooted at v Chi| dren of∨
General Trees 6.1 General Tree Definitions and Terminology
6. 1 General Tree Definitions and Terminology General trees a nodes out degree is the number of children for that node Out degree of node d is 3 a forest is a collection of one or more trees
General Trees A node’s out degree is the number of children for that node. – Out degree of node D is 3. A forest is a collection of one or more trees. A B C D E F G H I J K L M 6.1 General Tree Definitions and Terminology
6. 1 General Tree Definitions and Terminology General Tree node / General tree node ADT template <typename e> class GTNode i public: E value() / Return value bool isLeaf ( / TRUE if is a leaf ANOde大 parent(); //Return parent GTNode* leftmostchild(;// First child GTNode* rightsibling(); //Right sibling void setvalue(E&) / Set value void insertFirst(gtnode<E>X) void insertNext(gtnode<E>X) void removeFirst(; / Remove first child void removeNext();//Remove sibling }
General Tree Node // General tree node ADT template <typename E> class GTNode { public: E value(); // Return value bool isLeaf(); // TRUE if is a leaf GTNode* parent(); // Return parent GTNode* leftmostChild(); // First child GTNode* rightSibling(); // Right sibling void setValue(E&); // Set value void insertFirst(GTNode<E>*); void insertNext(GTNode<E>*); void removeFirst(); // Remove first child void removeNext(); // Remove sibling }; 6.1 General Tree Definitions and Terminology
6. 1 General Tree Definitions and Terminology General Tree adt / General tree ADT template <typename E> class GenTree t public: void clears / Send nodes to free store Gtnode<E>* root( / Return the root //Combine two subtrees void newr。ot(E, ANode<E>大, GTNode<E>*); void print();//Print a tree
General Tree ADT // General tree ADT template <typename E> class GenTree { public: void clear(); // Send nodes to free store GTNode<E>* root(); // Return the root //Combine two subtrees void newroot(E&, GTNode<E>*, GTNode<E>*); void print(); // Print a tree }; 6.1 General Tree Definitions and Terminology
6. 1 General Tree Definitions and Terminology General Tree Traversal Preorder: first visit the root of the tree then performs a preorder traversal of each subtree from left to right Postorder: First performs a postorder traversal of the root's subtrees from left to right, then visit the root Inorder traversal does not have a natural defination ⊙
General Tree Traversal Preorder: First visit the root of the tree, then performs a preorder traversal of each subtree from left to right; Postorder: First performs a postorder traversal of the root’s subtrees from left to right, then visit the root; Inorder traversal does not have a natural defination. 6.1 General Tree Definitions and Terminology