程序员人生网站导航

数据结构 - 二叉树的存储结构

栏目：数据库应用时间：2015-05-25 09:01:28

顺序存储结构

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叉树(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叉树的遍历，分别讨论递归遍历算法和非递归遍历算法。
递归遍历算法具有非常清晰的结构，但初学者常常难以接受或怀疑，不敢使用。实际上，递归算法是由系统通过使用堆栈来实现控制的。
非递归算法中的控制是由设计者定义和使用堆栈来实现的。

先序遍历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

------分隔线----------------------------