songzi 2008-5-3 22:26
二叉树详解(二)（数据结构）
一、复习[url=http://219.219.90.4:8080/datastru/class21/class21.htm#2103][color=#0000ff]二叉树的定义[/color][/url]
[indent]二叉树的基本特征：每个结点的度不大于２。
[/indent]二、顺序存储结构
[indent]#define MAX_TREE_SIZE 100
typedef TElemType SqBiTree[MAX_TREE_SIZE];
SqBiTree bt;
[img]http://www.bccn.net/Article/UploadFDL05/200411/20041112072736446.jpg[/img]
[table=75%][tr][td]结点编号[/td][td][align=center][color=#ff0000]1[/color][/align][/td][td][align=center][color=#0000ff]2[/color][/align][/td][td][align=center][color=#0000ff]3[/color][/align][/td][td][align=center][color=#ffcc99]4[/color][/align][/td][td][align=center][color=#ff00ff]5[/color][/align][/td][td][align=center]6[/align][/td][td][align=center]7[/align][/td][td][align=center]8[/align][/td][td][align=center]9[/align][/td][td][align=center]10[/align][/td][td][align=center]11[/align][/td][td][align=center]12[/align][/td][td][align=center]13[/align][/td][td][align=center]14[/align][/td][td][align=center]15[/align][/td][/tr][tr][td]结点值[/td][td][align=center]1[/align][/td][td][align=center][color=#cccccc]2[/color][/align][/td][td][align=center][color=#cccccc]3[/color][/align][/td][td][align=center]4[/align][/td][td][align=center]5[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][td][align=center]6[/align][/td][td][align=center]7[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][td][align=center]0[/align][/td][/tr][/table]第i号结点的左右孩子一定保存在第2i及2i+1号单元中。
缺点：对非完全二叉树而言，浪费存储空间
[/indent]三、链式存储结构
[indent]一个二叉树的结点至少保存三种信息：数据元素、左孩子位置、右孩子位置
对应地，链式存储二叉树的结点至少包含三个域：数据域、左、右指针域。
[img=314,231]http://www.bccn.net/Article/UploadFDL05/200411/20041112072738536.jpg[/img]
也可以在结点中加上指向父结点的指针域P。
[img=322,221]http://www.bccn.net/Article/UploadFDL05/200411/20041112072738664.jpg[/img]
对结点有二个指针域的存储方式有以下表示方法：
typedef struct BiTNode{
TElemType data;
struct BitNode *lchild,*rchild;
}BiTNode,*BiTree;
基于该存储结构的二叉树基本操作有：
Status CreteBiTree(BiTree &T);
//按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示的二叉树T。
Status PreOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//先序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status InOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//中序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status PostOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//后序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
Status LevelOrderTraverse(BiTree T,Status(*Visit)(TElemType e));
//采用二叉链表存储结构,Visit是对结点操作的应用函数
//层序遍历二叉树T,对每个结点调用函数Visit一次且仅一次
//一旦visit()失败,则操作失败
[/indent]四、总结本课内容
[indent]顺序存储与链式存储的优缺点。
[/indent]