根据所定乂的操作不同,可以有不同性能的二叉树 (1)线索化二叉树( Threaded Binary Tree):在二叉树结点中增加前 驱指针和后继指针,使得在二叉树中查找当前结点的在某种遍 历方式下的前驱和后继结点很方便 (2)堆(Heap):用来实现高效率的优先级队列的二叉树,采用顺序 存储结构。其特点是:树中任一结点的关键码均小(大)于或 等于它的左子结点和右子结点的关键码,称为最小(大)堆。 (3)霍夫曼树( Huffman tree):带权路径长度WPL最小的(扩充) 二叉树。WPL-- Weighted Path Length (4)二叉排序树 Binary Sorting Tree) 叉搜索树( Binary Search Tree) 中序遍历为严格递增的二叉树。这种树可以提高搜索(查找) 效率。 (5)最优二叉搜索树:平均搜索长度最小的二叉搜索树。 (6)AVL树:高度平衡的二叉搜索树,可以提高搜索效率,减/平 均搜索长度 (7)其他 2021220
2021/2/20 11 根据所定义的操作不同，可以有不同性能的二叉树 （1）线索化二叉树( Threaded Binary Tree )：在二叉树结点中增加前 驱指针和后继指针，使得在二叉树中查找当前结点的在某种遍 历方式下的前驱和后继结点很方便 （2）堆( Heap )：用来实现高效率的优先级队列的二叉树，采用顺序 存储结构。其特点是：树中任一结点的关键码均小（大）于或 等于它的左子结点和右子结点的关键码，称为最小（大）堆。 （3）霍夫曼树(Huffman Tree ) ：带权路径长度WPL 最小的（扩充） 二叉树。WPL----Weighted Path Length （4）二叉排序树(Binary Sorting Tree ) 二叉搜索树(Binary Search Tree ) 中序遍历为严格递增的二叉树。这种树可以提高搜索（查找） 效率。 （5）最优二叉搜索树：平均搜索长度最小的二叉搜索树。 （6）AVL 树：高度平衡的二叉搜索树，可以提高搜索效率，减小平 均搜索长度 （7）其他
64二叉树遍历( Binary Tree Traversal)操作 遍历:按照某种顺序不重复地访问遍二叉树中的所有结点。此处的 访问可以是输出、修改等操作,根据实际需要而定。 遍历操作可以从一种非线性结构中得到相应的线性序列。 有不同顺序的遍历操作,对于二叉树有三种遍历操作 先序痛历(NLR)中序遍历(LNR) 后序遍历(LRN) 访问根结点 中序遍历左子树 后序遍历左子树 先序遍历左子树访问根结点 后序遍历右子树 先序遍历右子树中序遍历右子树 访问根结点 可以看出,上述三种顺序的二叉树遍历操作都是递归定义的 因此用递归算法实现很容易。 2021220 12
2021/2/20 12 6.4 二叉树遍历(Binary Tree Traversal ) 操作 遍历：按照某种顺序不重复地访问遍二叉树中的所有结点。此处的 访问可以是输出、修改等操作，根据实际需要而定。 遍历操作可以从一种非线性结构中得到相应的线性序列。 有不同顺序的遍历操作，对于二叉树有三种遍历操作： 先序遍历（NLR） 中序遍历（LNR） 后序遍历（LRN） 访问根结点 中序遍历左子树 后序遍历左子树 先序遍历左子树 访问根结点 后序遍历右子树 先序遍历右子树 中序遍历右子树 访问根结点 可以看出，上述三种顺序的二叉树遍历操作都是递归定义的， 因此用递归算法实现很容易
叉树的先序遍历操作递归算法 template <class Type> void Binary Tree<Type>: PreOrder( ∥公共函数:先序遍历二叉树,通过调用私有函数 PreOrder实现 PreOrder( root) template <class Type> void Binary Tree< Type> PreOrder( BinTreeNode<Type>* current /有函数:先序遍历根结点指针为 current的二叉树 i if current! =NULL) {/若二叉树不空,则先序遍历之 Visit( current ∥)问根结点* current PreOrder( current-> leftchild);,∥先序遍历左子树 PreOrder( current->right Child);先序遍历右子树 2021220
2021/2/20 13 二叉树的先序遍历操作递归算法 template <class Type> void BinaryTree<Type>:: PreOrder ( ) //公共函数：先序遍历二叉树，通过调用私有函数 PreOrder 实现 { PreOrder ( root ); } template <class Type> void BinaryTree<Type> :: PreOrder ( BinTreeNode<Type> * current ) //私有函数：先序遍历根结点指针为current 的二叉树 { if ( current ! = NULL ) {//若二叉树不空，则先序遍历之 Visit ( current ); //访问根结点*current PreOrder ( current -> leftChild ); //先序遍历左子树 PreOrder ( current -> rightChild ); //先序遍历右子树 } }
叉树定义中部分成员函数的实现: template <class Type> void Binary Tree<Type> destroy( bin TreeNode<Type>* current /有函数:若指针 current不空,则删除根指针为 current的子树 i if( current!= NULL destroy( current-> leftchild);∥删除左子树 destroy( current-> right Child);/删除右子树 delete current;}}∥删除根结点* current。后序遍历 template <class Type> Bin TreeNode< Type>* Binary Tree< Type Parent( BinTreeNode<Type>* start, BinTreeNode<type>* current) /有函数:在根结点为* start的二叉树中查找结点* current的父结点,若存 在则返回其指针,否则返回NULL if( start=NULL) return NULL:空树 if( start-> leftChild -current start->right Child -=current )return start ∥根结点即为所找结点 Bin TreeNode <lype>p if((p=Parent( start->left Child, current ))! NULL )return p ∥俤归搜索左子树若找到则返回其指针 else return Parent( start-> right Child, current):) 则递归搜索右子树,若找到则返回其指针,否则返回NULI 2021220
2021/2/20 14 二叉树定义中部分成员函数的实现： template <class Type> void BinaryTree<Type> :: destroy ( BinTreeNode<Type> * current ) //私有函数：若指针 current 不空，则删除根指针为 current 的子树 { if ( current ! = NULL ) { destroy ( current -> leftChild ) ; //删除左子树 destroy ( current -> rightChild ) ; //删除右子树 delete current ; } } //删除根结点 *current 。后序遍历 template <class Type> BinTreeNode<Type> * BinaryTree<Type> :: Parent ( BinTreeNode<Type> * start , BinTreeNode<Type> * current ) //私有函数：在根结点为 *start 的二叉树中查找结点 *current 的父结点，若存 //在则返回其指针，否则返回 NULL { if ( start == NULL ) return NULL ;//空树 if ( start -> leftChild == current || start -> rightChild == current ) return start ; //根结点即为所找结点 BinTreeNode<Type> * p ; if ((p=Parent ( start -> leftChild , current )) != NULL ) return p ; //递归搜索左子树,若找到则返回其指针 else return Parent ( start -> rightChild , current ) ; } //否则递归搜索右子树，若找到则返回其指针，否则返回 NULL
template <class Type> void Binary Tree<type> Traverse( Bin TreeNode Type>* current, ostream out )const /有函数:先序遆历输出根指针为 current二叉树的所有结点的值 if( current!=NUL)年空树则遍历输出 out<< current-data<<;∥输出根结点的值 Traverse( current- leftchild,out);/历输出左子树 Traverse( current-> right Child,out);∥)历输出右子树 template <class Type> ostream operator<<(ostream &out Binary Tree<Type>& Tree 重载 Inserting操作符“≤”,用于直接输出一棵二叉树 out<<"Preorder traversal of binary tree. n Tre. Traverse(Tree.Root,out);∥/先序遍历输出 out << endl return out 2021220
2021/2/20 15 template <class Type> void BinaryTree<Type> :: Traverse ( BinTreeNode < Type> * current , ostream & out ) const //私有函数：先序遍历输出根指针为current 二叉树的所有结点的值 { if ( current != NULL ) //非空树则遍历输出 { out << current -> data << ‘ ‘ ; //输出根结点的值 Traverse ( current -> leftChild , out ) ; //遍历输出左子树 Traverse ( current -> rightChild , out ) ; //遍历输出右子树 } } template <class Type> ostream & operator << ( ostream & out , BinaryTree<Type> & Tree ) //重载inserting 操作符“ << ” ， 用于直接输出一棵二叉树 { out << “Preorder traversal of binary tree. \n” ; Tree . Traverse ( Tree . Root , out ) ; //先序遍历输出 out << endl ; return out ; }