这些天参与了CSDN论坛的讨论,改变了我以前的一些看法。回头看我以前的东西,我虽对这本书很不满,但我还是按照它的安排在一点点的写;这样就导致了,我过多的在意书中的偏漏,我写的更多是说“这本书怎样”,而偏离了我写这些的初衷——给正在学习数据结构的人一些帮助。
正像我在前面所说的,虽然现有的教科书都不是很合理,但假如仅仅是抱怨这点,那无异于泼妇骂街。虽然本人的水平连初级都够不上,但至少先从我做一点尝试,以后这门课的教授方法必将一点点趋于合理。
因此,后面不在按照书上的次序,将本着“实际应用(算法)决定数据结构”的思想来讲解,常见教科书上有的,基本不再重点叙述(除了重点,例如AVL树的平衡旋转),——因此,在看本文的同时,一定要有一本教科书。这只是一个尝试,希望大家多提宝贵意见。
树
因为现实世界中存在这“树”这种结构——族谱、等级制度、目录分类等等,而为了研究这类问题,必须能够将树储存,而如何储存将取决于所需要的操作。这里有个问题,是否答应存在空树。有些书认为树都是非空的,因为树表示的是一种现实结构,而0不是自然数;我用过的教科书都是说可以有空树,当然是为了和二叉树统一。这个没有什么原则上的差别,反正就是一种习惯。
二叉树
二叉树可以说是人们假想的一个模型,因此,答应有空的二叉树是无争议的。二叉树是有序的,左边有一个孩子和右边有一个的二叉树是不同的两棵树。做这个规定,是因为人们赋予了左孩子和右孩子不同的意义,在二叉树的各种应用中,你将会清楚的看到。下面只讲解链式结构。看各种讲数据结构的书,你会发现一个有趣的现象:在二叉树这里,基本操作有计算树高、各种遍历,就是没有插入、删除——那树是怎么建立起来的?其实这很好理解,对于非线性的树结构,插入删除操作不在一定的法则规定下,是毫无意义的。因此,只有在具体的应用中,才会有插入删除操作。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或节点结构
数据域、左指针、右指针肯定是必须的。除非很少用到节点的双亲,或者是资源紧张,建议附加一个双亲指针,这将会给很多算法带来方便,尤其是在这个“空间换时间”的时代。
template
strUCtBTNode
{
BTNode(Tdata=T(),BTNode*left=NULL,BTNode*right=NULL,BTNode*parent=NULL)
:data(data),left(left),right(right),parent(parent){}
BTNode*left,*right,*parent;
Tdata;
};
基本的二叉树类
template
classBTree
{
public:
BTree(BTNode*root=NULL):root(root){}
~BTree(){MakeEmpty();}
voidMakeEmpty(){destroy(root);root=NULL;}
PRotected:
BTNode*root;
private:
voiddestroy(BTNode*p)
{
if(p)
{
destroy(p-left);
destroy(p-right);
deletep;
}
}
}
二叉树的遍历
基本上有4种遍历方法,先、中、后根,逐层。当初我对这个很迷惑,搞这么多干什么?到了后面才明白,这是不同的应用需要的。例如,判定两个二叉树是否相等,只要子树根节点不同,那么就不等,显然这时要用先序遍历;而删除二叉树,必须先删除左右子树,然后才能删除根节点,这时就要用后序遍历。
实际上,搞这么多遍历方法,根本原因是在内存中储存的树是非线性结构。对于用数组储存的二叉树,这些名目繁多的方法都是没有必要的。利用C++的封装和重载特性,这些遍历方法能很清楚的表达。
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或1.前序遍历
public:
voidPreOrder(void(*visit)(T&data)=print){PreOrder(root,visit);}
private:
voidPreOrder(BTNode*p,void(*visit)(T&data))
{
if(p){visit(p-data);PreOrder(p-left,visit);PreOrder(p-right,visit);}
}
2.中序遍历
public:
voidInOrder(void(*visit)(T&data)=print){InOrder(root,visit);}
private:
voidInOrder(BTNode*p,void(*visit)(T&data))
{
if(p){InOrder(p-left,visit);visit(p-data);InOrder(p-right,visit);}
}
3.后序遍历
public:
voidPostOrder(void(*visit)(T&data)=print){PostOrder(root,visit);}
private:
voidPostOrder(BTNode*p,void(*visit)(T&data))
{
if(p){PostOrder(p-left,visit);PostOrder(p-right,visit);visit(p-data);}
}
4.层次遍历
voidLevelOrder(void(*visit)(T&data)=print)
{
queue*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:
staticvoidprint(T&data){cout
5.不用栈的非递归中序遍历
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或当有parent指针时,可以不用栈实现非递归的中序遍历,书上提到了有这种方法,但没给出例程。
public:
BTNode*next()
{
if(!current)returnNULL;
if(current-right){current=current-right;while(current-left)current=current-left;}
else
{
BTNode*y=current-parent;
while(y&¤t==y-right){current=y;y=y-parent;}
current=y;
}
returncurrent;
}
private:
BTNode*current;
上面的函数能使current指针向前移动一个位置,假如要遍历整棵二叉树,需要使current指向中序序列的第一个节点,例如下面的成员函数:
public:
voidfirst(){current=root;while(current-left)current=current-left;}
更多内容请看C/C++技术专题 数据结构 数据结构教程专题,或