树是数据结构中一门很重要的数据结构，在很多地方都能经常见到他的面孔，比如数据通信，压缩数据等都能见到树的身影。但是最常见的还是相对简单的二叉树，二叉树和常规树都可以进行相互转换。所以，二叉树的操作必不可少。我这里来简单介绍一下。
在数据结构中给的树和图中，我们最好使用递归来进行各种操作，会让代码更清晰易懂，代码也会更简洁。
开始
添加适当的头文件，定义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请自行测试
- 上述文字皆为个人看法，如有错误或建议请及时联系我
