首页 > > 程序设计 > C/C++ >

数据结构学习（C ）之二叉树

2008-02-23 05:25:20来源：互联网阅读 ()

　树

　　因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等，而为了研究这类问题，必须能够将树储存，而如何储存将取决于所需要的操作。这里有个问题，是否允许存在空树。有些书认为树都是非空的，因为树表示的是一种现实结构，而0不是自然数；我用过的教科书都是说能够有空树，当然是为了和二叉树统一。这个没有什么原则上的差别，反正就是一种习惯。

　　二叉树

　　二叉树能够说是人们假想的一个模型，因此，允许有空的二叉树是无争议的。二叉树是有序的，左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定，是因为人们赋予了左孩子和右孩子不同的意义，在二叉树的各种应用中，您将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书，您会发现一个有趣的现象：在二叉树这里，基本操作有计算树高、各种遍历，就是没有插入、删除——那树是怎么建立起来的？其实这很好理解，对于非线性的树结构，插入删除操作不在一定的法则规定下，是毫无意义的。因此，只有在具体的应用中，才会有插入删除操作。

　　节点结构

　　数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲，或是资源紧张，建议附加一个双亲指针，这将会给很多算法带来方便，尤其是在这个“空间换时间”的时代。

template <class T>

struct BTNode

{

BTNode(T data = T(), BTNode<T>* left = NULL, BTNode<T>* right = NULL, BTNode<T>* parent = NULL)

: data(data), left(left), right(right), parent(parent) {}

BTNode<T> *left, *right, *parent;

T data;

};

　　基本的二叉树类

template <class T>

class BTree

{

public:

BTree(BTNode<T> *root = NULL) : root(root) {}

~BTree() { MakeEmpty(); }

void MakeEmpty() { destroy(root); root = NULL; }

protected:

BTNode<T> *root；

private:

void destroy(BTNode<T>* p)

{

if (p)

{

destroy(p->left);

destroy(p->right);

delete p;

}

}

}