2叉树存储结构的类型定义：
＃define MAX_SIZE 100
typedef telemtype sqbitree[MAX_SIZE];用1组地址连续的存储单元顺次“自上而下、自左至右”存储完全2叉树的数据元素。
对完全2叉树上编号为i的结点元素存储在1维数组的下标值为i⑴的份量中，如图6⑹(c)所示。
对1般的2叉树，将其每一个结点与完全2叉树上的结点相对比，存储在1维数组中，
设计不同的结点结构可构成不同的链式存储结构。
(1) 结点的类型及其定义
① 2叉链表结点。有3个域：1个数据域，两个分别指向左右子结点的指针域
typedef struct BTNode
{ ElemType data ;
struct BTNode *Lchild , *Rchild ;
}BTNode ; ② 3叉链表结点。除2叉链表的3个域外，再增加1个指针域，用来指向结点的父结点
typedef struct BTNode_3
{ ElemType data ;
struct BTNode_3 *Lchild , *Rchild , *parent ;
}BTNode_3 ; 遍历2叉树(Traversing Binary Tree)：是指按指定的次序（规律）顺次访问2叉树中所有结点，使得每一个结点被访问1次且仅被访问1次。
访问：指对结点做某种处理。如：输出信息、修改结点的值等。
次序（规律）：2叉树是1种非线性结构，每一个结点都可能有左、右两棵子树，所以在访问完1个结点以后，下1个被访问的结点面临着不同的选择。因此，需要寻觅1种次序（规律），使2叉树上的结点能排列在1个线性队列上，从而便于遍历。
2叉树的基本组成：根结点、左子树、右子树。若能顺次遍历这3部份，就是遍历了2叉树。
若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，则有6种遍历方案：DLR、LDR、LRD、DRL、RDL、RLD。
若规定先左后右，则只有前3种情况3种情况，分别是：
DLR――先(根)序遍历。
LDR――中(根)序遍历。
LRD――后(根)序遍历。
已知2叉树，写出先序序列、中序序列、后序序列
已知先序序列和中序序列，肯定2叉树
已知后序序列和中序序列，肯定2叉树
对2叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。
递归遍历算法具有非常清晰的结构，但初学者常常难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。
非递归算法中的控制是由设计者定义和使用堆栈来实现的。
1 递归算法
算法的递归定义是：
若2叉树为空，则遍历结束；否则
⑴ 访问根结点；
⑵ 先序遍历左子树(递归调用本算法)；
⑶ 先序遍历右子树(递归调用本算法)。
先序遍历的递归算法
void PreorderTraverse(BTNode *T)
{ if (T==NULL)
return;
visit(T->data) ; /* 访问根结点 */
PreorderTraverse(T->Lchild) ; //再先序遍历左子树
PreorderTraverse(T->Rchild) ; //再先序遍历右子树
}
说明：1、visit()函数是访问结点的数据域，其要求视具体问题而定,可以是最简单的打印输出。
2、树采取2叉链表的存储结构，用指针变量T来指向。
2 非递归算法
设T是指向2叉树根结点的指针变量，非递归算法是：
若2叉树为空，则返回；否则，令p=T；
⑴ 访问p所指向的结点；
⑵ q=p->Rchild ，若q不为空，则q进栈；
⑶ p=p->Lchild ，若p不为空，转(1)，否则转(4)；
⑷ 退栈到p ，转(1)，直到栈空为止。
算法实现：
#define MAX_STACK_SIZE 50
void PreorderTraverse( BTNode *T)
{ BTNode *Stack[MAX_STACK_SIZE ] ,*p=T, *q ;
int top=0 ;
if (T==NULL) printf(“ Binary Tree is Empty!
”) ;
else { do
{ visit( p-> data ) ; q=p->Rchild ;
if ( q!=NULL ) stack[top++]=q ;
p=p->Lchild ;
if (p==NULL&& top!=0)
{top-- ；p=stack[top] ; }
}
while (p!=NULL) ;
}
}
上一篇 忙碌的5月~~~
下一篇 【J2EE浅析】――JNDI
程序员人生，我编程，我富裕，记住wfuyu网，php教程，php学习，php手册，CMS模版制作
声明：本站大部分内容是作者原创，少部分收集于互联网供大家一起学习，原版权很多不明，如有侵权请联系本站，谢谢！
粤ICP备14040726号-1 2015-2020 程序员人生 版权所有
