软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> 树、二叉树(二) -> 正文阅读
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress

[开发杂谈]树、二叉树(二)

  2016-03-09 15:31:54

限于篇幅过长上一篇我们只谈了树、二叉树(一)比较基础的认识,下面我们深入的学习树与二叉树。

顺序存储结构


使用一组地址(一维数组)连续的存储单元来存储数据元素

    //-------二叉树的顺序存储表示---------
    #define MAXTSIZE 100  //二叉树的最大结点数
    typedef TElemType SqBiTree[MAXTSIZE];
    SqBiTree bt;

完全二叉树:只需要从根起按层序存储,依次自上而下、自左至右存储结点元素,即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-1的分量中。



一般二叉树:一般二叉树同样要遵循完全二叉树的规则,将结点进行相对照,存储在一维数组的相对应分量中。



顺序存储的优点与缺点


  1. 对于完全二叉树来说,顺序存储结构既简单又节约存储空间。

  2. 一般的二叉树采取顺序存储结构时,虽然简单,但容易造成存储空间的浪费。

  3. 在顺序存储的二叉树做插入和删除结点时,要大量移动结点。

链式存储结构


对照上面顺序存储结构的不足,我们引入了链式存储,二叉树的结点至少有三个域:数据域、左、右指针域。有时候我们还要知道它的双亲,所以还要加上一个指向双亲结点的指针域。

//----二叉树的二叉链表存储表示---
typedef struct BiTNode{
TElemType data;//结点数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;


遍历二叉树


遍历二叉树是沿着某个指定路径有规律的进行访问树的每一个结点,保证每个结点均能被访问一次,并且只能被访问一次。
遍历的实质是通过遍历结果将非线性结构的树中结点排成一个线性序列。
通过上一篇树、二叉树(一)
我们得知二叉树有根结点(D)、左子树(L)和右子树(R)三部分组成。
根据高中数学知识得知一共有DLR、LDR、LRD、DRL、RDL、RLD六种方式遍历。但若限定先左后右的原则则只有DLR、LDR、LRD三种情况,分别称为先(根)序遍历、中(根)序遍历、后(根)序遍历。

先序遍历


(1)访问根节点;
(2)先序遍历左子树;
(3)先序遍历右子数。
Status PreOrderTraverse(BiTree T)
{
 if(T==NULL)return OK;//空二叉树
 else{
 cout<<T->data;//访问根结点
 PreOrderTraverse(T->child);//递归遍历左子树
  PreOrderTraverse(T->child);//递归遍历右子树
}
}

中序遍历


(1)中序遍历左子树;
(2)访问根结点;
(3)中序遍历右子树。
    Status InOrderTraverse(BiTree T)
{
 if(T==NULL)return OK;//空二叉树
 else{
  InOrderTraverse(T->child);//递归遍历左子树
 cout<<T->data;//访问根结点

  InOrderTraverse(T->child);//递归遍历右子树
}
}

后序遍历


(1)后序遍历左子树;
(2)后序遍历右子树;
(3)访问根结点。
    Status PostOrderTraverse(BiTree T)
{
     if(T==NULL)return OK;//空二叉树
 else{
  PostOrderTraverse(T->child);//递归遍历左子树
  PostOrderTraverse(T->child);//递归遍历右子树
  cout<<T->data;//访问根结点
 }
}

通过伪代码我们可以看到这三种方式
访问路径是相同的,只是访问结点的时机不同。

例子:

先序遍历
+ * * / A B C D E
中序遍历
A / B * C * D + E
后序遍历
A B / C * D * E +

结论:


若二叉树中各结点的值均不相同,则:
由二叉树的前序序列和中序序列,或由其后序序列和中序序列均能唯一地确定一棵二叉树,但由前序列和后序列却不一定能唯一确定一颗二叉树。

上一篇文章      下一篇文章      查看所有文章
2016-03-09 15:31:34  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 人民的名义 人民的名义在线看 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图
中国文化英文 多播视频 装修知识库
2017-5-26 7:48:19
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --