ITPub博客

首页 > Linux操作系统 > Linux操作系统 > 数据结构学习之二叉树(转)

数据结构学习之二叉树(转)

原创 Linux操作系统 作者:jcszjswkzhou 时间:2019-04-10 12:21:05 0 删除 编辑


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

  二叉树

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

  节点结构

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

template

struct BTNode

{

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

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

BTNode *left, *right, *parent;

T data;

};


  基本的二叉树类

template

class BTree

{

public:

BTree(BTNode *root = NULL) : root(root) {}

~BTree() { MakeEmpty(); }

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

protected:

BTNode *root;

private:

void destroy(BTNode* p)

{

if (p)

{

destroy(p->left);

destroy(p->right);

delete p;

}

}

}


  二叉树的遍历

  基本上有4种遍历方法,先、中、后根,逐层。当初我对这个很迷惑,搞这么多干什么?到了后面才明白,这是不同的应用需要的。例如,判断两个二叉树是否相等,只要子树根节点不同,那么就不等,显然这时要用先序遍历;而删除二叉树,必须先删除左右子树,然后才能删除根节点,这时就要用后序遍历。

  实际上,搞这么多遍历方法,根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树,这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性,这些遍历方法能很清晰的表达。

  1. 前序遍历

public:

void PreOrder(void (*visit)(T &data) = print) { PreOrder(root, visit); }

private:

void PreOrder(BTNode* p, void (*visit)(T &data))

{

if (p){ visit(p->data); PreOrder(p->left, visit); PreOrder(p->right, visit); }

}


  2. 中序遍历

public:
void InOrder(void (*visit)(T &data) = print) { InOrder(root, visit); }
private:
void InOrder(BTNode* p, void (*visit)(T &data))
{
if (p){ InOrder(p->left, visit); visit(p->data); InOrder(p->right, visit); }
}


  3. 后序遍历

public:
void PostOrder(void (*visit)(T &data) = print) { PostOrder(root, visit); }
private:
void PostOrder(BTNode* p, void (*visit)(T &data))
{
if (p){ PostOrder(p->left, visit); PostOrder(p->right, visit); visit(p->data); }
}


  4. 层次遍历

void LevelOrder(void (*visit)(T &data) = print)
{
queue< BTNode* > a; BTNode* p = root;//记得#include
while (p)
{
visit(p->data);
if (p->left) a.push(p->left); if (p->right) a.push(p->right);
if (a.empty()) break; p = a.front(); a.pop();
}
}
  附注:缺省的visit函数print如下
private:
static void print(T &data) { cout << data << ’ ’;}


  5. 不用栈的非递归中序遍历

  当有parent指针时,可以不用栈实现非递归的中序遍历,书上提到了有这种方法,但没给出例程。

public:
BTNode* next()
{
if(!current) return NULL;
if (current->right) { current = current->right; while (current->left) current = current->left; }
else
{
BTNode* y = current->parent;
while (y && current == y->right) {current = y; y = y->parent; }
current = y;
}
return current;
}
private:
BTNode* current;



  上面的函数能使current指针向前移动一个位置,如果要遍历整棵二叉树,需要使current指向中序序列的第一个节点,例如下面的成员函数:


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/10294527/viewspace-126059/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2007-08-29

  • 博文量
    2992
  • 访问量
    2209923