数据结构:非完全二叉树(递归实现)

发布时间:2024年01月21日

? 非完全二叉树是指在二叉树中,除了叶子节点(无子节点)外,其他节点的子节点个数可以不同,即不一定是每个节点都有两个子节点,有右孩子时也不一定有左孩子。

tree.h

/*===============================================
*   文件名称:tree.h
*   创 建 者:cxy     
*   创建日期:2024年01月21日
*   描    述:
================================================*/
#ifndef _TREE_H
#define _TREE_H

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

typedef struct node{
    char data;
    struct node *lchild; //左孩子
    struct node *rchild; //右孩子
}Tree,*Ptree;

Ptree init();   //创建树
int preorder(Ptree root);  //先序遍历
int inorder(Ptree root);   //中序遍历
int postorder(Ptree root); //后序遍历

#endif

tree.c

/*===============================================
*   文件名称:tree.c
*   创 建 者:cxy     
*   创建日期:2024年01月21日
*   描    述:
================================================*/
#include "tree.h"

Ptree init()  //递归与回归 先根
{
    char ch;
    scanf("%c",&ch);
    Ptree root = NULL;
    if('#' == ch)
        return NULL;
    else
    {
        root = malloc(sizeof(Tree));
        root->data = ch;
        root->lchild = init();
        root->rchild = init();
    }

    return root;
}

int preorder(Ptree root)
{
    if(NULL == root)
        return 0;
    printf("%c",root->data);
    preorder(root->lchild);
    preorder(root->rchild);
   
    return 0;
}

int inorder(Ptree root)
{
    if(NULL == root)
        return 0;
    inorder(root->lchild);
    printf("%c",root->data);
    inorder(root->rchild);

    return 0;
}

int postorder(Ptree root)
{
    if(NULL == root)
        return 0;
    postorder(root->lchild);
    postorder(root->rchild);
    printf("%c",root->data);

    return 0;
}

main.c

/*===============================================
*   文件名称:mian.c
*   创 建 者:cxy     
*   创建日期:2024年01月21日
*   描    述:
================================================*/
#include "tree.h"

int main(int argc, char *argv[])
{ 
    Ptree root = NULL;
    root = init();

    printf("-----先序遍历-----\n");
    preorder(root);
    puts("");
    printf("-----中序遍历-----\n");
    inorder(root);
    puts("");
    printf("-----后序遍历-----\n");
    postorder(root);
    puts("");

    return 0;
} 

结果

文章来源:https://blog.csdn.net/cxy255256/article/details/135732466
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。