【C 数据结构】二叉树

ゝ一世哀愁。 2024-04-01 18:06 32阅读 0赞

将下图中的二叉树用二叉链表表示：

![e8a3ea38c87a4f899d05eedfb2c2ff84.jpeg][]

1.  用三种遍历算法遍历该二叉树，给出对应的输出结果；
2.  写一个函数对二叉树搜索，若给出一个结点，根据其是否属于该树，输出true 或者false。

实验步骤

1.  定义二叉树的结点类型及二叉树类型
2.  递归方式建立二叉树（算法参见课本）
3.  三种方式遍历二叉树（算法参见课本）

#include <stdio.h>
    #include <stdlib.h>
    
    #define ElemType char
    
    typedef int Status;
    typedef struct node //二叉树结点定义
    {
        ElemType data; //结点数据域
        struct node *lchild, *rchild; //左右孩子指针域
    } BTNode, *BiTree;
    
    
    BTNode *CreateBiTree()//按照前序遍历 序列建立二叉树
    {
        BTNode *root;
        char ch;
        scanf("%c", &ch);
        getchar();
        if (ch != '#') {
            root = (BTNode *) malloc(sizeof(BTNode));
            root->data = ch;
            printf("请输入%c的左子树：", ch);
            root->lchild = CreateBiTree();
            printf("请输入%c的右子树：", ch);
            root->rchild = CreateBiTree();
        } else
            root = NULL;
        return root;
    }
    
    void PreOrder(BTNode *r) {
        if (r != NULL) {
            printf("%6c", r->data);
            PreOrder(r->lchild);
            PreOrder(r->rchild);
        } else
            return;
    }
    
    void InOrder(BTNode *r) {
        if (r != NULL) {
            InOrder(r->lchild);
            printf("%6c", r->data);
            InOrder(r->rchild);
        } else
            return;
    }
    
    void PostOrder(BTNode *r) {
        if (r != NULL) {
            PostOrder(r->lchild);
            PostOrder(r->rchild);
            printf("%6c", r->data);
        } else
            return;
    }
    
    Status Search(BTNode *root, char ch) {
        int lable = 0;
        if (root != NULL) {
            if (ch == root->data) {
                lable = 1;
            } else {
                lable = Search(root->lchild, ch);
                if (lable == 0)
                    lable = Search(root->rchild, ch);
            }
        }
        return lable;
    }
    
    int main() {
    
        BTNode *root;
        int lable;
        char ch;
    
        printf("请输入二叉树的根节点:");
        root = CreateBiTree();
        printf("\n");
        printf("前序遍历二叉树的遍历序列为：");
        PreOrder(root);
        printf("\n");
        printf("中序遍历二叉树的遍历序列为：");
        InOrder(root);
        printf("\n");
        printf("后序遍历二叉树的遍历序列为：");
        PostOrder(root);
        printf("\n");
    
        printf("---------------------------\n");
        printf("输入要查找的字符：");
    
        scanf("%c", &ch);
        getchar();
        lable = Search(root, ch);
        if (lable == 1)
            printf("找到%c,查找成功，值为：%s\n", ch, "true");
        else
            printf("未找到%c,查找失败，值为：%s\n", ch, "false");
    
        return 0;
    }

[e8a3ea38c87a4f899d05eedfb2c2ff84.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/b0020e0a43c44745a3c98900863f1790.jpeg