二叉树重点整理.docx

?Tree Definitions and Terminology ?Binary Tree Definitions 树的定义，略?Binary Tree Properties The maximum number of nodes on ith level of a binary tree is 2^(i-1), i≥1.The maximum number of nodes in a binary tree of height k is (2^k)-1, k≥1.ADT for Tree Nodes // General tree node ADT template typename E class GTNode { public: E value(); // Return node’s value bool isLeaf(); // True if node is a leaf GTNode* parent(); // Return parent GTNode* leftmostChild(); // Return first childGTNode* rightSibling(); // Return right sibling void setValue(E); // Set node’s value void insertFirst(GTNodeE*); // Insert first child void insertNext(GTNodeE*); // Insert next sibling void removeFirst(); // Remove first child void removeNext(); // Remove right sibling };?The Full Binary Tree Theorem 满二叉:所有节点为0、2度节点完全二叉:每一层除了最后一层都是满的，最后一排必须从左往右?Binary Tree ADT // Binary tree node abstract class template typename E class BinNode { public: virtual ?BinNode() {} // Base destructor // Return the node’s value virtual E element() = 0; // Set the node’s value virtual void setElement(const E) = 0; // Return the node’s left child virtual BinNode* left() const = 0; // Set the node’s left child virtual void setLeft(BinNode*) = 0; // Return the node’s right child virtual BinNode* right() const = 0; // Set the node’s right child virtual void setRight(BinNode*) = 0; // Return true if the node is a leaf, false otherwise virtual bool isLeaf() = 0; };Binary Tree Traversals? Preorder OLRtemplate typename E void preorder2(BinNodeE* root) { visit(root); // Perform whatever action is desired if (root-left() != NULL) preorder2(root-left()); if (root-right() != NULL) preorder2(root-right()); }? Inorder LORInorder Traversal (recursive) template typename E void inorder(BinNodeE*