和线性表一样,二叉树也有顺序存储结构和连锁存储结构
二叉树的顺序存储
二叉树顺序存储是指用一系列地址连续的存储单元存储二叉树的数据元素。
二叉树或完全二叉树适合采用顺序存储结构,可以使用数组下标来确定节点在二叉树中的位置和节点之间的关系,同时尽可能节约存储空间。
一般二叉树需要增加很多空节点才能改造成完整的二叉树,但一般树非常不建议采用顺序存储结构,空间浪费较多。最坏情况:只有右分支的右单枝树(除叶节点外,各节点只有一个右边的孩子的树)、高h的右单枝树),但如图所示,需要分配存储单元)
对于普通二叉树:
孩子找父母:
如果孩子的节点号为I,则父母的节点为 [i // 2]。 保留整数部分
父母寻找孩子:
如果父母节点的编号为I,则左侧孩子的节点为 [2i],右侧孩子的节点为 [2i+1]。
二叉树的链式存储
在二叉树的连锁记忆中,二叉树的每个节点
lchild(左指针字段,包含左孩子节点的地址) ) )。
data(用于存储相应数据元素的值域) )。
由3358www.Sina.com/(右指针字段,存储右孩子节点的地址)三部分组成,这种存储结构由根节点指针b存储在rchild两股中
叉链中的节点类型声明如下:
类型结构节点{数据类型数据; 结构节点*液晶屏; 结构节点*字符; } BT节点; 如图所示:
双链存储结构的优点:
一般二叉树节省记忆空间
访问某个节点的孩子的节点很有用
但是,访问一个节点的父母的节点需要扫描所有节点。
二叉链(binary linked list)。
二叉树的基本运算及其实现:为方便起见,我们采用双链实现二叉树的基本运算。
1 .二叉树高度
| 1 t-lchild==NULLt-rchild==NULL
h(t ) |
|max(h(t-lchild )、H(t-rchild ) ) 1其他
2 .二叉树的节点数
| 1 t-lchild==NULLt-rchild==NULL
C(T )=*
| c (叔字符) c (叔字符) 1其他
3 .二叉树叶节点数
| 1 t-lchild==NULLt-rchild==NULL
C1(T ) |
C1 (叔液晶屏) C1 (叔液晶屏)其他
顺序遍历:
1 .访问根节点
2 .首先遍历左边的树
3 .遍历右边的子树
中序扫描:
1 .依次遍历左边的树
2 .访问根节点
3 .依次遍历右边的子树
反向遍历:
1 .向后遍历左边的树
2 .依次遍历右边的子树
3 .访问根节点
层次遍历:
如果二叉树不为空,则从上到下、从左到右依次访问每个节点
二叉树的遍历
任何n个节点的二叉树都可以做到
中序序列和前序序列
中序序列和层序序列
中序序列和后序序列
唯一确定。