《数据结构与算法分析 C++描述》读书笔记第四章_typename comparator=less<object>-CSDN博客

本文链接：https://blog.csdn.net/mvpsendoh/article/details/6170802

1.树由称作根的结点r以及零个或多个非空的（子树）T1，T2，...Tk组成，这些子树中每一棵的根都被来自根r的一条有向的边所连接。每一棵子树的根叫做根r的儿子，而r是每一课子树的根的父亲。一棵树是N个结点和N-1条边的集合。其中的一个结点叫做根。每条边都将某个结点连接到它的父亲，而除去根结点外每个结点都有一个父亲。没有儿子的结点称为叶结点。具有相同父亲的结点为兄弟。

2.从结点n1到nk的路径定义为结点n1,n2,...nk的一个序列。路径的长为路径上的边的条数，即k-1。从每一个结点到它自己有一条长为0的路径。对任意结点ni,ni的深度为从根到ni的唯一路径的长。根的深度为0。ni的高是从ni到一片树叶的最长路径的长。因此所有的树叶的高都是0。一棵树的高等于它的根的高。

3.树的实现：

将每个结点的所有儿子都放在树结点的链表中：

struct TreeNode

{

Object element;

TreeNode *firstChild; //指向第一个儿子

TreeNode *nextSibling; //指向下一个兄弟

};

4.树的遍历：

前序遍历：

//伪码，源码如何实现？？

void FileSystem::listAll( int depth=0 )const

{

printName(depth); //print the name of the object

if( isDirectory() )

for each file c in the directory (for each child)

c.listAll(depth+1);

}

后序遍历：

int FileSystem::size() const

{

int totalSize=sizeOfThisFile();

if(isDirectory())

for each file c in this directory( for each child )

totalSize+=c.size();

return totalSize;

}

5.二叉树：

（1）二叉树是一棵每个结点都不能有多于两个儿子的树。

二叉树的一个性质是平均二叉树的深度要比结点个数N小得多。这个平均深度为O(√N)。而对于特殊类型的二叉树，即二叉查找树，其深度的平均值是O(logN)。

（2）实现：

因为一个二叉树结点最多有两个儿子，因此可以直接链接他们：

struct BinaryNode

{

Object element; //the data in the node

BinaryNode *left; //left child

BinaryNode *right; //right child

};

（3）表达式树：

表达式树的树叶是操作数，其他结点是操作符。

6.二叉查找树：

性质：对于树的每个结点X,它的左子树中所有项的值小于X中的项。而它的右子树中所有项的值大于X中的项。

下面是一个BinarySearchTree类模板的接口，查找是基于<操作符的,而该操作符对特定的Compareble类型必须定义：

template <typename Comparable>
class BinarySearchTree
{
public:
BinarySearchTree();
BinarySearchTree( const BinarySearchTree &rhs);
~BinarySearchTree();

const Comparable &findMin() const ;
const Comparable &findMax() const;
bool contains( const Comparable &x) const;
bool isEmpty() const;
void printTree() const;
void makeEmpty();
void insert( const Comparable &x);
void remove( const Comparable &x);
const BinarySearchTree & operator=(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 printTree( BinaryNode * &t);
void printTree( BinaryNode *t) const;
BinaryNode *clone(BinaryNode *t) const;
};

contains:如果在树X中有项为X的结点，那么contains操作就返回true，否则，若没有这样的结点就返回false。树结构使得该操作很简单。如果T为空，那么就可以返回false，否则，如果存储在T中的项为X，就返回true。

bool contains ( const Comparable &x) const
{
return contains(x,root);
}

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

}

注意首先要对是否为空树进行验证，如果不这么做就会产生一个企图通过NULL指针访问数据成员的运行错误。

下面是使用函数对象而不是使用Comparable项所需要做的微小修改：

template <typename Object,typename Comparator=less<Object> >
class BinarySearchTree
{
public:
//same methods,with Object replacing Comparable
private:
BinaryNode *root;
Comparator isLessThan;
//same methods,with Object replacing Comparable
bool contains( const Object &x,BinaryNode *t) const
{
  if(t==NULL)
   return false;
  else if( isLessThan(x,t->element) )
   return contains(x,t->left);
  else if( isLessThan(t->element,x) )
   return contains(x,t->right);
  else
   return true;   //Match
}
};