二叉树示意图:
a
/
b
/ \
c d
/ / \
e f g
/ /
h i
/
j
二叉树的(链式)逻辑结构 示意图:
# a ^
/
# b #
/ \
# c ^ # d #
/ / \
^ e ^ # f ^ # g ^
/ /
^ h ^ # i ^
/
^ j ^
上述示意图, 符号#表示指针域, 符号^表示NULL(空指针)
先序遍历序列: a b c e d f h g i j
中序遍历序列: e c b h f d j i g a
后序遍历序列: e c h f j i g d b a
//C语言测试程序
#include "stdio.h"
#include "stdlib.h"
struct tree
{
char data
struct tree *left
struct tree *right
}
typedef struct tree treenode
typedef treenode *btree
btree createbtree(char *data,int pos,int maxPos) //递归创建法
{
btree newnode
if(data[pos]==0 || pos>maxPos)
{
return NULL
}
else
{
newnode=(btree)malloc(sizeof(treenode))
newnode->data=data[pos]
newnode->left=createbtree(data,2*pos,maxPos)
newnode->right=createbtree(data,2*pos+1,maxPos)
return newnode
}
}
void preorder(btree ptr) //先序遍历(递归法)
{
if(ptr!=NULL)
{
printf("%C ",ptr->data)
preorder(ptr->left)
preorder(ptr->right)
}
}
void inorder(btree ptr) //中序遍历(递归法)
{
if(ptr!=NULL)
{
inorder(ptr->left)
printf("%C ",ptr->data)
inorder(ptr->right)
}
}
void postorder(btree ptr) //后序遍历(递归法)
{
if(ptr!=NULL)
{
postorder(ptr->left)
postorder(ptr->right)
printf("%C ",ptr->data)
}
}
int main()
{
btree root=NULL
int i
char data[64]={0,'a','b',0,'c','d',0,0,
'e',0,'f','g',0,0,0,0,
0,0,0,0,'h',0,'i',0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,'j',0,0,0,
0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0}
root=createbtree(data,1,63)
printf("二叉树的顺序存储内容: ")
for(i=1i<64i++)
{
if(data[i]==0)
{
printf("^ ")
}
else
{
printf("%c ",data[i])
}
}
printf("\n二叉树的先序遍历序列: ")
preorder(root)
printf("\n二叉树的中序遍历序列: ")
inorder(root)
printf("\n二叉树的后序遍历序列: ")
postorder(root)
printf("\n")
return 0
}
线性是线性，顺序是顺序，线性是逻辑结构，顺序是储存结构，两者不是一个概念。线性是指一个节点只有一个子节点，而树，或二叉树一个节点后有多个子节点，且子节点不能相互联系。
顺序存储可能会浪费空间(在非完全二叉树的时候)，但是读取某个指定的节点的时候效率比较高。
链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低。
二叉树的顺序存储，寻找后代节点和祖先节点都非常方便，但对于普通的二叉树，顺序存储浪费大量的存储空间，同样也不利于节点的插入和删除。因此顺序存储一般用于存储完全二叉树。
链式存储相对顺序存储节省存储空间，插入删除节点时只需修改指针，但回寻找指定节点时很不方便。不过普通答的二叉树一般是用链式存储结构。
扩展资料：
(1)完全二叉树——若设二叉树的高度为h，除第h层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
二叉树是树的一种特殊情形，是一种更简单而且应用更加广泛的树。
参考资料来源：百度百科-二叉树
二叉树按照层序遍历，依次编号，按照编号的顺序，存储在连续存储单元的方式就是二叉树的顺序存储。
如果二叉树不是满二叉树，则只存储有内容的节点，缺失的结点在存储的过程中，所对应的位置不存储任何东西，即是空的。
对于题中所给的存储结构，构造一个满二叉树，结点为空，再按照层序遍历，依次编号，在相应的结点填上数据，没有数据的则为空结点。
最后删除所有的空结点，即为所对应的二叉树
扩展资料：
二叉树除了按顺序存储的存储方式，还有另外一种——链式存储方式，即用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。
其中，data存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表。如下图所示：
参考资料来源：百度百科-二叉树顺序存储
参考资料来源：百度百科-二叉树
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）