C语言二叉树的基本操作

作者: EarthChen | 来源:发表于2017-08-06 18:03 被阅读500次

平衡二叉树的基本操作
C语言二叉树的基本操作
c语言数组基本操作
SQL C语言基本操作
C语言队列的基本操作
二叉树基本操作-C语言实现
顺序表的基本操作(C语言)
C语言基础教程之基本语法
Linux&C语言知识结构图
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);
}