对外经济贸易大学《C++程序设计》课件-lecture10Tree Traversal Techniques; Heaps.pptVIP

CS 1031lecture10Tree Traversal Techniques; Heaps Tree Traversal ConceptTree Traversal Techniques: Preorder, Inorder, PostorderFull Trees Almost Complete TreesHeaps对外经济贸易大学《C++程序设计》 CS 1032Binary-Tree Related DefinitionsThe children of any node in a binary tree are ordered into a left child and a right childA node can have a left and a right child, a left child only, a right child only, or no childrenThe tree made up of a left child (of a node x) and all its descendents is called the left subtree of xRight subtrees are defined similarly10131198465712 CS 1033A Binary-tree Node Classclass TreeNode { public: typedef int datatype; TreeNode(datatype x=0, TreeNode *left=NULL, TreeNode *right=NULL){ data=x; this-left=left; this-right=right; }; datatype getData( ) {return data;}; TreeNode *getLeft( ) {return left;}; TreeNode *getRight( ) {return right;}; void setData(datatype x) {data=x;}; void setLeft(TreeNode *ptr) {left=ptr;}; void setRight(TreeNode *ptr) {right=ptr;}; private: datatype data; // different data type for other apps TreeNode *left; // the pointer to left child TreeNode *right; // the pointer to right child}; CS 1034Binary Tree Classclass Tree { public: typedef int datatype; Tree(TreeNode *rootPtr=NULL){this-rootPtr=rootPtr;}; TreeNode *search(datatype x); bool insert(datatype x); TreeNode * remove(datatype x); TreeNode *getRoot(){return rootPtr;}; Tree *getLeftSubtree(); Tree *getRightSubtree(); bool isEmpty(){return rootPtr == NULL;}; private: TreeNode *rootPtr;}; CS 1035Binary Tree TraversalTraversal is the process of visiting every node onceVisiting a node entails doing some processing at that node, but when describing a traversal strategy, we need not concern ourselves with what that processing is CS 1036Binary Tree Traversal TechniquesThree recursive techniques for binary tree traversalIn each technique, the l