ITPub博客

首页 > 应用开发 > IT综合 > 数据结构学习(C++)——二叉树【1】 (转)

数据结构学习(C++)——二叉树【1】 (转)

原创 IT综合 作者:amyz 时间:2007-11-10 19:32:21 0 删除 编辑
数据结构学习(C++)——二叉树【1】 (转)[@more@]

这些天参与了CSDN论坛的讨论,改变了我以前的一些看法。回头看我以前的东西,我虽对这本书很不满,但我还是按照它的安排在一点点的写;这样就导致了,我过多的在意书中的偏漏,我写的更多是说“这本书怎样”,而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。正像我在前面所说的,虽然现有的教科书都不是很合理,但如果仅仅是抱怨这点,那无异于泼妇骂街。虽然本人的水平连初级都够不上,但至少先从我做一点尝试,以后这门课的教授方法必将一点点趋于合理。XML:namespace prefix = o ns = "urn:schemas-microsoft-com:Office:office" />

因此,后面不在按照书上的次序,将本着“实际应用(算法)决定数据结构”的思想来讲解,常见教科书上有的,基本不再重点叙述(除了重点,例如AVL树的平衡旋转),——因此,在看本文的同时,一定要有一本教科书。这只是一个尝试,希望大家多提宝贵意见。

因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等,而为了研究这类问题,必须能够将树储存,而如何储存将取决于所需要的操作。这里有个问题,是否允许存在空树。有些书认为树都是非空的,因为树表示的是一种现实结构,而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指向中序序列的第一个节点,例如下面的成员函数:

public:

void first() { current = root; while (current->left) current = current->left; }


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

请登录后发表评论 登录
全部评论
  • 博文量
    3984
  • 访问量
    7338473