C语言二叉树的基本操作

树是数据结构中一门很重要的数据结构,在很多地方都能经常见到他的面孔,比如数据通信,压缩数据等都能见到树的身影。但是最常见的还是相对简单的二叉树,二叉树和常规树都可以进行相互转换。所以,二叉树的操作必不可少。我这里来简单介绍一下。
在数据结构中给的树和图中,我们最好使用递归来进行各种操作,会让代码更清晰易懂,代码也会更简洁。

开始

添加适当的头文件,定义hex一个栈数据结构,

首先我们定义一个二叉树的数据结构

#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef char ElemType;
typedef struct BiTNode
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

创建一个二叉树(前序)

这里以前序作为例子,前中后序遍历的不同之在于递归的顺序

void creatBiTree(BiTree *T) {
    ElemType c;
    scanf("%c", &c);
    if ('#' == c)
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTNode *)malloc(sizeof(BiTNode));
        (*T)->data = c;
        creatBiTree(&(*T)->lchild);
        creatBiTree(&(*T)->rchild);
    }
}

遍历二叉树(前序遍历)

这里依然以前序作为例子,前中后序遍历的不同之在于递归的顺序

void preorder(BiTree T) {
    if (T) {
        printf("%c\n", T->data);
        preorder(T->lchild);
        preorder(T->rchild);
    }
}

层次遍历二叉树

void levelorder(BiTree T) {
    //用一个队列保存结点信息,这里的队列采用的是顺序队列中的数组实现
    int front = 0;
    int rear = 0;
    BiTree BiQueue[MAXSIZE];
    BiTree tempNode;
    if (!IsEmpty_BiTree(&T)) {
        //将根结点加入到队列中 
        BiQueue[rear++] = T;

        while (front != rear) {
            //取出队头元素,并使队头指针向后移动一位 
            tempNode = BiQueue[front++];
            //判断左右子树是否为空,若为空,则加入队列 
            if (!IsEmpty_BiTree(&(tempNode->lchild)))
                BiQueue[rear++] = tempNode->lchild;

            if (!IsEmpty_BiTree(&(tempNode->rchild)))
                BiQueue[rear++] = tempNode->rchild;

            //输出队头结点元素 
            //Vist_BiTreeNode(tempNode->data);
            printf("%c\n", tempNode->data);

        }
    }
}

复制树

将二叉树复制给另一个二叉树

void copybitree(BiTree T, BiTree *newT) {
    if (T == NULL)
    {
        *newT = NULL;
        return;
    }
    else
    {
        *newT = (BiTNode *)malloc(sizeof(BiTNode));
        ((*newT)->data) = (T->data);
        copybitree(T->lchild, &(*newT)->lchild);
        copybitree(T->rchild, &(*newT)->rchild);
    }
}

计算结点个数

计算二叉树的结点个数

int countleaf(BiTree T) {
    if (T == NULL)
    {
        return 0;
    }
    else {
        return countleaf(T->lchild) + countleaf(T->rchild) + 1;
    }
}

左、右子树交换

交换一颗二叉树的左右子树

void exchange(BiTree T) 
{
    BiTree p;
    if (T != NULL)
    {
        p = T->lchild;
        T->lchild = T->rchild;
        T->rchild = p;
        exchange(T->lchild);
        exchange(T->rchild);
    }
}

主函数

void main() {
    BiTree T=NULL,newT=NULL;
    creatBiTree(&T);
    printf("前序遍历\n");
    preorder(T);
    printf("中序遍历\n");
    inorder(T);
    printf("中后遍历\n");
    postorder(T);
    printf("层序遍历\n");
    levelorder(T);
    printf("节点个数为%d\n", countleaf(T));
    copybitree(T, &newT);
    printf("newT前序遍历\n");
    preorder(newT);
    exchange(T);
    printf("交换左右子树之后前序遍历为");
    preorder(T);
}

运行结果

二叉树运行结果

以上就是二叉树的一些基本操作,大量运用的递归的思想,希望读者能好好研读

注:

  • 上述代码在visual studio 2015中编译成功运行,其他ide请自行测试
  • 上述文字皆为个人看法,如有错误或建议请及时联系我
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 数据结构和算法--二叉树的实现 几种二叉树 1、二叉树 和普通的树相比,二叉树有如下特点: 每个结点最多只有两棵子...
    sunhaiyu阅读 6,534评论 0 14
  • 四、树与二叉树 1. 二叉树的顺序存储结构 二叉树的顺序存储就是用数组存储二叉树。二叉树的每个结点在顺序存储中都有...
    MinoyJet阅读 1,597评论 0 7
  • B树的定义 一棵m阶的B树满足下列条件: 树中每个结点至多有m个孩子。 除根结点和叶子结点外,其它每个结点至少有m...
    文档随手记阅读 13,370评论 0 25
  • 树和二叉树 1、树的定义 树(Tree)是由一个 或 多个结点 组成的有限集合T,且满足: ①有且仅有一个称为根的...
    利伊奥克儿阅读 1,399评论 0 1
  • 1.树(Tree): 树是 n(n>=0) 个结点的有限集。当 n=0 时称为空树。在任意一颗非空树中:有且仅有一...
    ql2012jz阅读 1,059评论 0 3