频道栏目
首页 > 数据库 > DB2 > 正文
数据结构-二叉树的存储结构
2015-04-30 10:14:35         来源:王照陆博客  
收藏   我要投稿

顺序存储结构

二叉树存储结构的类型定义:

#define MAX_SIZE  100
 typedef telemtype sqbitree[MAX_SIZE];

用一组地址连续的存储单元依次“自上而下、自左至右”存储完全二叉树的数据元素。
对于完全二叉树上编号为i的结点元素存储在一维数组的下标值为i-1的分量中,如图6-6(c)所示。
对于一般的二叉树,将其每个结点与完全二叉树上的结点相对照,存储在一维数组中,

链式存储结构

设计不同的结点结构可构成不同的链式存储结构。

(1) 结点的类型及其定义
① 二叉链表结点。有三个域:一个数据域,两个分别指向左右子结点的指针域

typedef struct BTNode
{  ElemType  data ;
struct BTNode  *Lchild , *Rchild ;
}BTNode ; 

② 三叉链表结点。除二叉链表的三个域外,再增加一个指针域,用来指向结点的父结点

typedef struct BTNode_3
{  ElemType  data ;
struct BTNode_3  *Lchild , *Rchild , *parent ;
}BTNode_3 ; 

遍历二叉树(Traversing Binary Tree)

遍历二叉树(Traversing Binary Tree):是指按指定的次序(规律)依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
访问:指对结点做某种处理。如:输出信息、修改结点的值等。
次序(规律):二叉树是一种非线性结构,每个结点都可能有左、右两棵子树,所以在访问完一个结点之后,下一个被访问的结点面临着不同的选择。因此,需要寻找一种次序(规律),使二叉树上的结点能排列在一个线性队列上,从而便于遍历。
二叉树的基本组成:根结点、左子树、右子树。若能依次遍历这三部分,就是遍历了二叉树。

若以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树,则有六种遍历方案:DLR、LDR、LRD、DRL、RDL、RLD。
   若规定先左后右,则只有前三种情况三种情况,分别是:

DLR——先(根)序遍历。
LDR——中(根)序遍历。
LRD——后(根)序遍历。
已知二叉树,写出先序序列、中序序列、后序序列
已知先序序列和中序序列,确定二叉树
已知后序序列和中序序列,确定二叉树

遍历算法

对于二叉树的遍历,分别讨论递归遍历算法和非递归遍历算法。
递归遍历算法具有非常清晰的结构,但初学者往往难以接受或怀疑,不敢使用。实际上,递归算法是由系统通过使用堆栈来实现控制的。
非递归算法中的控制是由设计者定义和使用堆栈来实现的。

先序遍历二叉树

1 递归算法
算法的递归定义是:
若二叉树为空,则遍历结束;否则
⑴ 访问根结点;
⑵ 先序遍历左子树(递归调用本算法);
⑶ 先序遍历右子树(递归调用本算法)。

先序遍历的递归算法
void  PreorderTraverse(BTNode  *T)
     {    if  (T==NULL) 
                return;
    visit(T->data) ;       /*  访问根结点  */
PreorderTraverse(T->Lchild) ; //再先序遍历左子树
PreorderTraverse(T->Rchild) ; //再先序遍历右子树
}
说明:1、visit()函数是访问结点的数据域,其要求视具体问题而定,可以是最简单的打印输出。
      2、树采用二叉链表的存储结构,用指针变量T来指向。

2 非递归算法
设T是指向二叉树根结点的指针变量,非递归算法是:
若二叉树为空,则返回;否则,令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!\n”) ;
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) ;
}
}
点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 结构
上一篇:数据结构-二叉树的遍历
下一篇:数据结构-树和二叉树
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站