二叉树
二叉树的顺序存储
#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
#define max 16
typedef struct BinaryNode{
ElemType data[max]; //创建存储数组
int size; //数组的大小
}binarytree;
//初始化二叉树
void init(binarytree *T)
{
for (int i = 0; i < max; i++){
T->data[i] = NULL; //将数组全部置为空并设置长度为0
}
T->size = 0;
}
//层次遍历创建二叉树
void creattree(binarytree *T)
{
ElemType n;
printf("当前为第%d个结点，请输入结点的值：", T->size);
n = getchar();
T->data[T->size] = n;
T->size++;
if (T->size == 20)
return;
if (n == '*')
return;
else{
n = getchar(); //吸收回车符
creattree(T);
}
}
//层次遍历打印
void Cprintftree(binarytree *T, int n)
{
for (; n<T->size; n++)
{
if (T->data[n] == NULL || T->data[n] == '*')
return;
else{
if (T->data[n] != '#')
printf("%c", T->data[n]);
}
}
}
//先序打印二叉树
void Rprintftree(binarytree *T, int n)
{
if (T->data[n] == NULL || T->data[n] == '*' || T->data[n] == '#')
return;
printf("%c", T->data[n]);
Rprintftree(T, 2 * n + 1);
Rprintftree(T, 2 * (n + 1));
}
//中序打印二叉树
void Zprintftree(binarytree *T, int n)
{
if (T->data[n] == NULL || T->data[n] == '*' || T->data[n] == '#')
return;
Zprintftree(T, 2 * n + 1);
printf("%c", T->data[n]);
Zprintftree(T, 2 * (n + 1));
}
//后序打印二叉树
void Hprintftree(binarytree *T, int n)
{
if (T->data[n] == NULL || T->data[n] == '*' || T->data[n] == '#')
return;
Hprintftree(T, 2 * n + 1);
Hprintftree(T, 2 * (n + 1));
printf("%c", T->data[n]);
}
//求结点数
int node(binarytree *T)
{
int num = 0;
for (int n = 0; n<T->size; n++)
{
if ((T->data[n] != NULL) && (T->data[n] != '#') && (T->data[n] != '*'))
{
num++;
}
}
return num;
}
//计算叶子结点数
int leaf(binarytree *T)
{
int num = 0;
for (int n = 0; n<T->size; n++)
{
if ((T->data[n] != NULL) && (T->data[n] != '#') && (T->data[n] != '*') && (T->data[2 * n + 1] == NULL) && (T->data[2 * (n + 1)] == NULL))
{
num++;
}
}
return num + 1;
}
int main()
{
binarytree T;
int n = 0;
init(&T);
printf("请从上到下从左往右输入结点的值，空结点用#代替当结束时用*，你最多可以输入%d个:\n", max);
creattree(&T);
printf("树得结点数为%d\n", node(&T));
printf("树得叶子结点数为%d\n", leaf(&T));
printf("树层次遍历结构的是：");
Cprintftree(&T, n);
printf("\n树先序遍历结构的是：");
Rprintftree(&T, n);
printf("\n树中序遍历结构的是：");
Zprintftree(&T, n);
printf("\n树后序遍历结构的是：");
Hprintftree(&T, n);
return 0;
}
二叉树的链式存储
#include<stdio.h>
#include<stdlib.h>
typedef int ElemType;
typedef struct BinaryTreeNode{
ElemType Date;
struct BinaryTreeNode *lChild, *rChild;
}BinaryTreeNode,*BiTree;
//先序遍历（PLR）：依次访问根结点，左子树，右子树
void PreOrderTransverse(BiTree t)
{
if (t == NULL)
return;
printf("%c", t->Date); //打印输出根结点
PreOrderTransverse(t->lChild); //然后先序遍历左子树
PreOrderTransverse(t->rChild); //最后先序遍历右子树
}
//中序遍历（LPR):依次访问左子树，根结点，右子树
void InOrderTransverse(BiTree t)
{
if (t == NULL)
return;
InOrderTransverse(t->lChild); //中序遍历根结点的左子树
printf("%c", t->Date); //打印输出根结点
InOrderTransverse(t->rChild); //最后中序遍历右子树
}
//后序遍历（LRP）:依次访问左子树，右子树，根结点
void PostOrderTransverse(BiTree t)
{
if (t == NULL)
return;
PostOrderTransverse(t->lChild); //后序遍历根结点的左子树
PostOrderTransverse(t->rChild); //然后后序遍历根结点的右子树
printf("%c", t->Date); //打印输出根结点
}
//先序遍历方法构建二叉树
BinaryTreeNode *PreCreateBt(BinaryTreeNode *t)
{
char ch;
ch = getchar();
if (ch == '#') //输入为#表示这里建立空二叉树，即遍历算法的空操作
t = NULL;
else
{
t = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
t->Date = ch; //构造根结点
t->lChild = PreCreateBt(t->lChild); //构造左子树
t->rChild = PreCreateBt(t->rChild); //构造右子树
}
return t;
}
//计算叶子数(度为0的结点)
int leaf(BiTree t)
{
int num1 = 0, num2 = 0;
if (t == NULL)
return 0;
if (t->lChild == NULL && t->rChild == NULL)
return 1;
else
{
num1++;
leaf(t->lChild);
num2++;
leaf(t->rChild);
}
return num1 + num2 + 1;
}
//结点数（树中的元素）
int node(BiTree t)
{
int num1, num2;
if (!t)
return 0;
if (t->lChild == NULL && t->rChild == NULL)
return 1;
else
{
num1 = node(t->lChild);
num2 = node(t->rChild);
}
return num1 + num2 + 1;
}
//复制二叉树
BiTree copy(BiTree t)
{
BiTree t1;
if (!t)
return NULL;
else
{
t1 = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
t1->Date = t->Date;
t1->lChild = t->lChild = copy(t->lChild);
t1->rChild = t->rChild = copy(t->rChild);
return t1;
}
}
//左右子树交换
void chage(BiTree t)
{
BiTree p;
if (!t)
return;
else
{
chage(t->lChild);
chage(t->rChild);
p = t->lChild;
t->lChild = t->rChild;
t->rChild = p;
}
}
int main()
{
BiTree t = NULL,t2;
printf("请输入树的数据：\n");
t = PreCreateBt(t);
printf("该树先序遍历：");
PreOrderTransverse(t);
printf("\n该树中序遍历：");
InOrderTransverse(t);
printf("\n该树后序遍历：");
PostOrderTransverse(t);
printf("\n");
printf("叶子数：%d\n", leaf(t));
printf("结点数：%d\n", node(t));
t2 = copy(t);
printf("复制树先序遍历：");
PreOrderTransverse(t2);
printf("\n左右子树交换后树的先序遍历");
chage(t);
PreOrderTransverse(t);
printf("\n");
}
