★ 第四十七讲 二叉树的建立和遍历算法 |【代码实操】 ★

不二如是

                               
登录/注册后可看大图

  

索引帖

  

用一节课的时间，提高生活幸福感

------小甲鱼

欢乐与傻笑并存

智慧与邪恶同在

笔记内涵------

---

二叉树的建立和遍历算法

有童鞋会说，我们上节课研究这么多遍历的方法干啥呢？

聪明的鱼油们怎么看？！

对于二叉树，思路方面我们已经谈得够多了，是时候由小甲鱼带大家来上机操作。

题目要求：

        建议二叉树并输出每个字符所在的层数。如右图要求输出

        A在第一层

        B、C在第二层

        D、E在第三层

代码实现：

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;

typedef struct BiTNode
{
        char data;
        struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 创建一棵二叉树，约定用户遵照前序遍历的方式输入数据
CreateBiTree(BiTree *T)
{
        char c;

        scanf("%c", &c);
//空格代表没有
        if( ' ' == c )
        {
                *T = NULL;
        }
        else
        {
                *T = (BiTNode *)malloc(sizeof(BiTNode));
                (*T)->data = c;
                CreateBiTree(&(*T)->lchild);
                CreateBiTree(&(*T)->rchild);
        }
}

// 访问二叉树结点的具体操作，你想干嘛？！
visit(char c, int level)
{
        printf("%c 位于第 %d 层\n", c, level);
}

// 前序遍历二叉树
PreOrderTraverse(BiTree T, int level)
{
        if( T )
        {
                visit(T->data, level);
                PreOrderTraverse(T->lchild, level+1);
                PreOrderTraverse(T->rchild, level+1);
        }
}

int main()
{
        int level = 1;
        BiTree T = NULL;

        CreateBiTree(&T);
        PreOrderTraverse(T, level);

        return 0;
}

最终结果：

---

高进阶（提示）：

//前序遍历  
void preorderTraverse(BiTree T) {  
    if(T==NULL)  
        return;  
    printf("%c",T->data);  
    preorderTraverse(T->lchild);  
    preorderTraverse(T->rchild);  
}  
  
//中序遍历  
void InorderTraverse(BiTree T) {  
   if(T){  
    InorderTraverse(T->lchild);  
    printf("%c",T->data);  
    InorderTraverse(T->rchild);  
   }  
}  
  
//后序遍历  
void PostorderTraverse(BiTree T) {  
    if(T) {  
        PostorderTraverse(T->lchild);  
        PostorderTraverse(T->rchild);  
        printf("%c",T->data);  
    }  
}  

这位鱼油，如果喜欢本系列笔记，请订阅 专辑☞（传送门）（不喜欢更要订阅 ）

菠萝人

1

刘某人哦

感谢

littleming

我炸了