认识树的结构（树的表达和应用）
认识树的结构（树的表达和应用）树的特点：对树中的每个结点X，他的左子树中所有项的值小于X中的项，他的右子树中所有项的值大于X中的项。特点：该树所有的元素都可以用某种一致的方式排序。图例表达形式：((a-b) *)*((c )* ) 2.后缀表达式（postfix expression）：递归打印左子树和右子树，然后打印操作符，即后序遍历（postorder traversal）。 特点：（左子树、右子树、结点）图例表达形式：ab-* c ** 3.前缀表达式( prefix expression)： 先打印出操作符，然后递归打印出左子树和右子树，即前序遍历（preorder traversal）。 特点：（结点，左子树，右子树）图例表达形式：* -ab** c 查找树（ADT）-二叉查找树（BinarySearchTree）性质：
表达式树包括：操作数（树叶）和操作符（结点）。
表达形式：
表达式树即通过递归的形式产生表达式类型包括：
1.中缀表达式（infix expression ）：递归产生带括号的左表达式和右表达式 即中序遍历策略（inorder traversal），特点：（左子树，结点，右子树）
图例表达形式：((a-b) *)*((c )* )
2.后缀表达式（postfix expression）：递归打印左子树和右子树，然后打印操作符，即后序遍历（postorder traversal）。 特点：（左子树、右子树、结点）
图例表达形式：ab-* c **
3.前缀表达式( prefix expression)： 先打印出操作符，然后递归打印出左子树和右子树，即前序遍历（preorder traversal）。 特点：（结点，左子树，右子树）
图例表达形式：* -ab** c 查找树（ADT）-二叉查找树（BinarySearchTree）
性质：
对树中的每个结点X，他的左子树中所有项的值小于X中的项，他的右子树中所有项的值大于X中的项。特点：该树所有的元素都可以用某种一致的方式排序。
树的特点：
树的定义是通过递归实现的，通常是递归的编写这些操作的例程。
二叉查找树的平均深度：
O(logN) 一般不必担心栈空间被用尽。
查找树特点：
查找是基于“<”操作符的，而该操作符对特定的Compare类型必须进行定义。特别是，若x<y和x>y均为false，那么，项x与项y匹配。这允许Comparable是一个复杂类型（例：雇员记录），而该复杂类型中有一部分类型（例：社保号数据成员或工资）具有比较功能。
二叉查找树类的框架：
注：
//二叉查找树类的框架 template <typename Comparable> class BinarySearchTree { public: BinarySearchTree();//二叉树函数 BinarySearchTree(const BianrySearchTree & rhs);//带参二叉树函数 BinarySearchTree();//二叉树析构函数，释放空间 const Comparable & findMin() const;//比较找最小值 const Comparable & findMax() const;//比较找最大值 bool contains(const Comparable & x) const;//判断树存储结构的容量Return true if x is present bool isEmpty() const ;//判断树的内容是否为空return true if empty; else false void printTree() const;//输出树的内容 void makeEmpty();//新建空树remove all items void insert(const Comparable & x);//向树内插入元素 void remove(const Comparable & x);//移除树中的元素 const BinarySearchTree & opeartor = (const BinarySearchTree & rhs);//树复合操作符 // private: //树结点结构体 struct BinaryNode { Comparable element;//结点变量 BinaryNode *left;//左指针变量 BinaryNode *right//右指针变量 BinaryNode(const Comparable & theElement BinaryNode * lt BinaryNode *rt) :element(theElement) left(lt) right(rt) { } //树结点表示方法 }; BinaryNode *root;//根节点指针 void insert( const Comparable & x BinaryNode * & t) const;//插入函数 void remove(const Comparable & x BinaryNode * & t) const;//移除函数 BinaryNode * findMin(BinaryNode *t ) const;//树结点最大值函数 BinaryNode * findMax(BinaryNode *t ) const;//树结点最小值函数 bool contains(const Comparable & x BinaryNode *t) const; //判断树容量 void makeEmpty(BinaryNode * & t);//建立空树 void printTree(BinaryNode *t) const;//打印树元素函数 BinaryNode * clone(BinaryNode *t) const;//克隆树结点函数 };
注：
1.数据成员指向树根节点的指针，该指针对空树为NULL。
2.public的成员函数使用调用private递归函数的常规技术。
3.private成员函数使用引址调用来传递指针变量的技术。这允许public成员函数将指向树根的指针传递给private递归成员函数。
共有成员函数调用私有递归成员函数的示例：
//共有成员调用私有递归成员函数的示例 /** * Returns true if x is found in the tree ; */ bool contains(const Comparable & x) const { return contains(x root); } /** * Insert x into the tree ; duplicates are ignored. */ void insert(const Comparable & x) { insert(x root ); } /* * Remove x from the tree Nothing is done if x is not found . */ void remove(const Comparable & x) { remove(x root); } 二叉查找树操作算子
1.contains包含函数
规则：
1.if （x属于树T），则contains()函数return-->true，else return -->false;
2.if (树T为空树)，则 return-->false ;
即：
//二叉查找树的contains操作 /* * Internal method to test if an item is in a subtree. * x is item to search for . * t is the node that roots the subtree . */ bool contains(const Comparable & x BinaryNode *t) const { if (t == NULL) return false; else if (x < t->element) return contains(x t->left); else if (t->element < x) return contains(x t->right); else return true; // Match }
注：
1.先测是否是空树。其余测试安排可能性最高的情况在最前面。
2.算法表达式的见明星是以速度的降低为代价的。
2.finMin函数（查找最小值）
规则：
根据查找二叉树的特点（左子树所有值小于根结点，右子树所有值大于根结点；所有子树左子树值小于结点值，右子树值大于结点值） --即查找左子树最左子树地址值（找地址--找值）
实现方法：
1.递归实现（if --if---NULL --- return）
2.非递归实现（if-- while(循环)--指针地址----return）
即：
//对二叉查找树的finMin的递归实现 /** *Internal method to find the smallest item in a subtree t . *return node containing the smallest item . */ BinaryNode * findMin(BinaryNode *t) const { if (t == NULL ) return NULL; if (t->left == NULL) return t; return findMin(t->left); }
3.finMax函数（查找最大值）
规则：
根据查找二叉树的特点（左子树所有值小于根结点，右子树所有值大于根结点；所有子树左子树值小于结点值，右子树值大于结点值） --即查找右子树最右子树地址值（找地址--找值）
实现方法：
1.递归实现（if --if---NULL --- return）
2.非递归实现（if-- while(循环)--指针地址----return）
即：
//对二叉查找树的finMax的非递归实现 /** *Internal method to find the largest item in a subtree t . *Return node containing the largest item . */ BinaryNode * findMax(BinaryNode *t) const { if (t != NULL) while (t->right != NULL) t = t_ > right; return t; }
4.Insert函数（向二叉查找树中插入元素值）
规则：
1.插入非重复元素值：遍历查找插入元素值。
2.插入重复元素值：通过结点记录中保留一个附加字段以指示此数据元出现的频率来处理。（增加了树的深度），如果“<”操作符使用的键只是一个更大的结构的一部分，那么可以把具有相同键的所有结构保留在一个辅助数据结构中，如表或另一棵查找树。
总结：
1.遍历方法（递归或循环）先找到插入数据的位置，然后在插入数据。
2.在递归历程中，只有当一个新树叶生产的时候，t才改变。
即：
//将元素插入到二叉查找树的例程 /** * Internal method to insert into a subtree . * x is the item to insert . * t is the node that roots the subtree. * set the new root of the subtree . */ void insert(const Comparable & x BinaryNode * & t) { if (t == NULL) t = new BinaryNode(x NULL NULL); else if (x < t->element) insert(x t->left); else if (t->element < x) insert(x t->right); else ; //Duplicate ; do nothing }
5.remove函数（删除二叉查找树的元素）
注：
同许多数据结构一样，最困难的操作是删除。删除会影响整条链的变动。
删除考虑要点：
1.结点是一片树叶：直接删除。
2.结点有一个儿子：删除结点，指向由（父结点-->儿子）变成由父结点的父结点（祖结点--->儿子）。
3.结点有两个儿子：勇气右子树的最小的数据（很容易找到）代替该结点的数据并递归地删除那个结点。
即：
//二叉查找树的删除例程 /** * Internal method to remove from a subtree. * x is the item to remove . * t is the node that roots the subtree . * Set the new root of the subtree . */ void remove(const Comparable & x BinaryNode * & t) { if (t == NULL) return; //item not found ; do nothing if (x < t->element) remove(x t->left); else if (t->element < x) remove(x t->right); else if (t->left != NULL && t->right != NULL) //Two children { t->element = findMin(t->right)->element; remove(t->element t->right); } else { BinaryNode *oldNode = t; t = (t->left != NULL) ? t->left : t->right; delete oldNode; } }
注：
懒惰删除
定义：
当一个元素要被删除时，他仍留在树中，而只是做了一个被删除的几号。
使用场景：
1.删除的次数不多，在有重复项时很流行，且减少删除时间损耗。
2.数据反复时，被删除项重新插入，可节约分配新单元的内存开销。
