《数据结构与算法分析 C++描述》读书笔记第四章

旧城等待， 2022-09-28 15:21 181阅读 0赞

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  
\}  
\};

findMin和findMax:

这两个private例程分别指向树中包含最小元和最大元的结点的指针。为了执行findMin，从根开始并且只要有左儿子就向左进行。终止点就是最小元素。findMax例程除分支朝向右儿子外其余过程相同。

用递归编写findMin而非递归编写findMax：

BinaryNode \*findMin(BinaryNode \*t) const

if(t==NULL)

return NULL;

if(t->left==NULL)

return t;

return findMin(t->left);

BinaryNode \*findMax( BinaryNode \*t) const

if(t!=NULL)

while(t->right!=NULL)