C语言丨不要阅读此文，除非你已掌握二叉树的这些操作

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

开始

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

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

#include

#include

#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请自行测试。