《数据结构 Data Structure》课程教学资源（PPT课件讲稿）06 非二叉树 Non-Binary Trees

6 Non-Binary Trees

1 6 Non-Binary Trees

Contents 6.1 General tree Definitions and Terminology 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.4 K-ary trees 6.5 Sequential Tree Implementations

Contents 6.1 General Tree Definitions and Terminology 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.4 K-ary Trees 6.5 Sequential Tree Implementations

Contents 6.1 General Tree Definitions and Terminology 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.4 K-ary trees 6.5 Sequential Tree Implementations

Contents 6.1 General Tree Definitions and Terminology 6.2 The Parent Pointer Implementation 6.3 General Tree Implementations 6.4 K-ary Trees 6.5 Sequential Tree Implementations

6. 1 General Tree Definitions and Terminology 6.1 General Tree Definitions and Terminology

4 6.1 General Tree Definitions and Terminology 6.1 General Tree Definitions and Terminology

6. 1 General Tree Definitions and Terminology General trees A Tree is a finite set of n(n>0)nodes such that One and only one node r, is called the root of The remaining nodes are partitioned into m(m≥0) disjoint subsets To,T1……Tm, each of which is a tree, and whose roots ro, rl.....rm-i respectively are children of r The subsets T(0si<m) are said to be subtrees of t

General Trees A Tree is a finite set of n (n>0) nodes such that • One and only one node R, is called the root of T. • The remaining nodes are partitioned into m(m0) disjoint subsets T0 ,T1…..Tm-1 , each of which is a tree, and whose roots R0 , R1…..Rm-1 , respectively, are children of R. • The subsets Ti (0i<m) are said to be subtrees of T. 6.1 General Tree Definitions and Terminology

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 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(gtnodeX) void insertNext(gtnodeX) void removeFirst(; / Remove first child void removeNext();//Remove sibling }

General Tree Node // General tree node ADT template 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*); void insertNext(GTNode*); 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 class GenTree t public: void clears / Send nodes to free store Gtnode* root( / Return the root //Combine two subtrees void newr。ot(E, ANode大, GTNode*); void print();//Print a tree

General Tree ADT // General tree ADT template class GenTree { public: void clear(); // Send nodes to free store GTNode* root(); // Return the root //Combine two subtrees void newroot(E&, GTNode*, GTNode*); 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