美文网首页
二叉树的存储及遍历

二叉树的存储及遍历

作者: 旅行者_sz | 来源:发表于2020-04-25 15:25 被阅读0次

一、二叉树顺序存储实现:

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);/* 显示结点数据,可以更改为其它对结点操作 */
}

相关文章

  • 二叉树操作

    树节点 逐行顺序解析二叉树 前序遍历二叉树 中序遍历二叉树 后序遍历二叉树 删除指定数值的节点 前序遍历顺序存储的...

  • 二叉树遍历

    二叉树 二叉树的存储结构 前序遍历 中序遍历 后序遍历 遍历代码 反转二叉树 深入学习二叉树 二叉树-你必须要懂!...

  • 数据结构基础学习之(树与二叉树)

    主要知识点: 树的定义及常用术语 树的存储表示 二叉树、满二叉树和完成二叉树的定义 二叉树的遍历此操作实现 哈夫曼...

  • 二叉树 (Binary Tree) 三种存储结构及四种遍历:先根

    Binary Tree 三种存储结构及四种遍历:先根、中根、后根、层序 一、二叉树的分类: 完全二叉树:一个二叉树...

  • 二叉树遍历(递归算法和非递归算法)

    实验三 二叉树遍历(递归算法和非递归算法) 一.实验目的 1.掌握二叉树的存储结构与基本操作 2.掌握二叉树的遍历...

  • 数据结构题目42:二叉树的前序遍历(非递归)

    题目:若二叉树为二叉链表存储结构,写出二叉树的前序遍历的非递归算法。 解题思路:和中序遍历很相似,只是遍历到结点要...

  • 常用数据结构

    一、序列 数组:顺序存储,随机访问 链表:链表存储,顺序访问 栈 队列 串 二、树 1)二叉树 2)遍历二叉树 前...

  • 一般二叉树普通二叉树,前、中、后序遍历以及搜索 顺序存储二叉树将数组以树的思想标识,包括前、中、后续遍历 线索化二...

  • 二叉树的存储及遍历

    一、二叉树顺序存储实现: 1.存储结构:(数组)···/* 0号单元存储根结点 */typedef CElemT...

  • 二叉树遍历方式总结(递归&迭代)

    经过一周的学习,我了解到了二叉树的遍历是非常重要且容易出错的,所以对二叉树的遍历方式及实现方式做个总结 一. 遍历...

网友评论

      本文标题:二叉树的存储及遍历

      本文链接:https://www.haomeiwen.com/subject/ssbhwhtx.html