一、二叉树顺序存储实现:
1.存储结构:(数组)
···
/* 0号单元存储根结点 */
typedef CElemType SqBiTree[MAX_TREE_SIZE];
typedef struct {
int level; //结点层
int order; //本层的序号(按照满二叉树给定序号规则)
}Position;
2.遍历方式:
层次遍历:T 为存储数组
int i = MAX_TREE_SIZE-1;
//找到最后一个非空结点的序号
while (T[i] == Nil) i--;
//从根结点起,按层序遍历二叉树
for (int j = 0; j <= i; j++)
//只遍历非空结点
if (T[j] != Nil)
visit(T[j]);
printf("\n");
前序遍历二叉树:
void PreTraverse(SqBiTree T,int e){
//打印结点数据
visit(T[e]);
//先序遍历左子树
if (T[2 * e + 1] != Nil) {
PreTraverse(T, 2*e+1);
}
//最后先序遍历右子树
if (T[2 * e + 2] != Nil) {
PreTraverse(T, 2*e+2);
}
}
Status PreOrderTraverse(SqBiTree T){
//树不为空
if (!BiTreeEmpty(T)) {
PreTraverse(T, 0);
}
printf("\n");
return OK;
}
中序遍历
void InTraverse(SqBiTree T, int e){
/* 左子树不空 */
if (T[2*e+1] != Nil)
InTraverse(T, 2*e+1);
visit(T[e]);
/* 右子树不空 */
if (T[2*e+2] != Nil)
InTraverse(T, 2*e+2);
}
Status InOrderTraverse(SqBiTree T){
/* 树不空 */
if (!BiTreeEmpty(T)) {
InTraverse(T, 0);
}
printf("\n");
return OK;
}
后序遍历
void PostTraverse(SqBiTree T,int e)
{
//左子树不空
if(T[2*e+1]!=Nil)
PostTraverse(T,2*e+1);
/* 右子树不空 */
if(T[2*e+2]!=Nil)
PostTraverse(T,2*e+2);
visit(T[e]);
}
Status PostOrderTraverse(SqBiTree T)
{
if(!BiTreeEmpty(T)) /* 树不空 */
PostTraverse(T,0);
printf("\n");
return OK;
}
输出:
二叉树T的存储: 1 2 3 4 5 6 7 8 9 10
二叉树T层序遍历:1 2 3 4 5 6 7 8 9 10
二叉树T先序遍历:1 2 4 8 9 5 10 3 6 7
二叉树T中序遍历:8 4 9 2 10 5 1 6 3 7
二叉树T后序遍历:8 9 4 10 5 2 6 7 3 1
二、链式存储 (链表)
// 结点结构
typedef struct BiTNode {
CElemType data; //结点数据
struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
前序递归遍历T
初始条件:二叉树T存在;
操作结果: 前序递归遍历T
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
中序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
void InOrderTraverse(BiTree T)
{
if(T==NULL)
return ;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
后序递归遍历T
初始条件:二叉树T存在;
操作结果: 中序递归遍历T
void PostOrderTraverse(BiTree T)
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c",T->data);/* 显示结点数据,可以更改为其它对结点操作 */
}
网友评论