一、二叉树的定义
二叉树是n(n≥0)个结点组成的有限集合。当n=0时，称为空二叉树；当n>0时，该集合由一个根节点及两颗互不相交的，被分别成为左子树和右子树的二叉树组成。
二叉树可以理解为满足以下条件的树形结构。
- 每个结点的度不大于2
- 结点每颗子树的位置是明确区分左右的，不能随意改变。
由上述定义可看出：二叉树中的每个结点只能有0、1、2个孩子，而且孩子有左右之分，即使仅有一个孩子，也必须区分左右。位于左边的孩子（或子树）叫左孩子(左子树)，位于右边的孩子（或子树）叫右孩子（右子树）
二、二叉树的性质
-
在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。
-
深度为k的二叉树至多有2^k -1个结点(k≥1).
-
对任意一颗二叉树T,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1.
-
具有n个结点的完全二叉树的深度为⌊logn⌋+1.
-
对于具有n个结点的完全二叉树，如果按照对满二叉树结点进行连续编号的方式，对所有结点从1开始顺序编号，则对任意序号为i的结点有：
1.如果i=1,则结点i为根，其无双亲结点；如果i>1，则结点i的双亲结点序号为⌊i/2⌋.
2.如果2i ≤n,否则，结点I无左孩子。
3.如果2i+1≤n,则结点i的右孩子结点序号为2I+1,否则，结点i无右孩子。
三、二叉树的存储
二叉树的存储结构主要有三种:顺序存储结构、链式存储结构和仿真指针存储结构。
这里主要介绍链式存储结构。
二叉树的链式存储结构就是用指针建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个指针域，分别是：数据域data、左孩子指针域letfchild和右孩子指针域rightChild.
四、二叉树的操作实现
所有操作都针对下面这个二叉树
头文件:BiTree.h
#pragma once
#include<malloc.h>
typedef struct Node {
DataType data;//数据域
struct Node *leftchild;//左子树指针
struct Node *rightchild;//右子树指针
}BiTreeNode;
//初始化
void Initiate(BiTreeNode **root) {
*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
(*root)->leftchild = NULL;
(*root)->rightchild = NULL;
}
//做插入结点
//若当前结点curr非空，则在curr的左子树插入元素值为x的新节点
//原curr所指结点的左子树成为新插入结点的左子树
//若插入成功，则返回新插入结点的指针，否则返回空指针
BiTreeNode* InsertLeftNode(BiTreeNode *curr, DataType x) {
BiTreeNode *s, *t;
if (curr == NULL) {
return NULL;
}
else {
t = curr->leftchild;//保存原来curr所指结点的左子树指针
s = (BiTreeNode*)malloc(sizeof(BiTreeNode));
s->data = x;
s->leftchild = t;//新插入结点的左子树成为为原来curr所指结点的左子树
s->rightchild = NULL;
curr->leftchild = s;//新结点成为curr的左子树
return curr->leftchild;//返回新插入结点的指针
}
}
//右插入结点
//若当前结点curr为空，则在curr的右子树插入元素值为x的新结点
//原curr所指结点的右子树成为新插入结点的右子树
//若插入成功，则返回新插入结点的指针，否则放回空指针
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {
BiTreeNode *s, *t;
if (curr == NULL) {
return NULL;
}
else {
t = curr->rightchild;//保存原curr所指结点的右子树指针
s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
s->data = x;
s->rightchild = t;//新插入结点的右子树为原curr的右子树
s->leftchild = NULL;
curr->rightchild = s;//新结点成为curr的右子树
return curr->rightchild;//返回新插入结点的指针
}
}
//撤销二叉树操作设计
void Destroy(BiTreeNode **root) {
if ((*root) != NULL && (*root)->leftchild != NULL) {
Destroy(&(*root)->leftchild);
}
if ((*root) != NULL && (*root)->rightchild != NULL) {
Destroy(&(*root)->rightchild);
}
free(*root);
}
//左删除子树
//若左子树非空，则删除curr所指结点的左子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteLeftTree(BiTreeNode *curr) {
if (curr == NULL || curr->leftchild == NULL) {
return NULL;
}
else {
Destroy(&curr->leftchild);
curr->leftchild = NULL;
return curr;
}
}
//右删除子树
//若curr非空，则删除curr所指结点的右子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteRightTree(BiTreeNode *curr) {
if (curr == NULL || curr->rightchild == NULL) {
return NULL;
}
else {
Destroy(&curr->rightchild);
curr->rightchild = NULL;
return curr;
}
}
void Visit(DataType item) {
printf("%c ", item);
}
//前序遍历二叉树，访问操作为Visit()函数
void PreOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
Visit(root->data);
PreOrder(root->leftchild, Visit);
PreOrder(root->rightchild,Visit);
}
}
//中序遍历二叉树，访问操作为Visit()函数
void InOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
InOrder(root->leftchild, Visit);
Visit(root->data);
InOrder(root->rightchild, Visit);
}
}
//后续遍历二叉树，访问操作为Visit()函数
void PostOrder(BiTreeNode *root, void Visit(DataType item)) {
if (root != NULL) {
PostOrder(root->leftchild, Visit);
PostOrder(root->rightchild, Visit);
Visit(root->data);
}
}
//打印二叉树
void PrintBiTree(BiTreeNode *root, int n) {
//逆时针旋转90度打印二叉树root,n为缩进层数，初始值为0
int i;
if (root == NULL) {//递归出口
return;
}
PrintBiTree(root->rightchild, n + 1);//遍历打印右子树
//访问根节点
for (i = 0; i < n - 1; i++) {
printf(" ");
}
if (n > 0) {
printf("---");
printf("%c\n", root->data);
}
PrintBiTree(root->leftchild, n + 1);//遍历打印左子树
}
//查找数据元素
BiTreeNode *Search(BiTreeNode *root, DataType x) {
//查找数据元素x是否再二叉树root中
//查找到则返回该结点指针，未找到则返回空指针
BiTreeNode *find = NULL; //初始标记为查找失败
if (root != NULL) {
if (root->data == x) {
find = root;
}
else {
find = Search(root->leftchild, x);//在左子树中查找
if (find == NULL) {
find = Search(root->rightchild, x);//在右子树中找
}
}
}
return find;//返回查找标记
}
//统计二叉树结点总数
int Count(BiTreeNode *T)
{
if (T == NULL) {
return 0;
}
else {
return Count(T->leftchild) + Count(T->rightchild) + 1;
}
}
//输出二叉树中的叶子结点
void InOrder(BiTreeNode *T)//实际上是root->leftchild,root是头节点
{
if (T) {
InOrder(T->leftchild);
if (T->leftchild == NULL && T->rightchild == NULL) {
printf("%c ",T->data);
}
InOrder(T->rightchild);
}
}
//统计二叉树中的叶子节点数目
int Leaf(BiTreeNode *T)
{
int nl, nr;
if (T == NULL)
return 0;
if ((T->leftchild == NULL) && (T->rightchild == NULL)) {
return 1;
}
nl = Leaf(T->leftchild);//递归求左子树的叶子树
nr = Leaf(T->rightchild);//递归求右子树的叶子树
return (nl + nr);
}
//统计二叉树中度为2的结点数目
int leaf_2(BiTreeNode *T) {
if (T ==NULL){
return 0;
}
if((T->leftchild != NULL) && (T->rightchild != NULL)) {
return (leaf_2(T->leftchild) + leaf_2(T->rightchild) + 1);
}
else{
return 0;
}
}
//交换二叉树中各个节点得左右子树
void swap( BiTreeNode *T) {
BiTreeNode *temp;
if (T == NULL) {
return;
}
else {
temp = T->leftchild;
T->leftchild = T->rightchild;
T->rightchild = temp;
swap(T->leftchild);
swap(T->rightchild);
}
}
源文件：
#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
#include"BiTree.h"
int main() {
BiTreeNode *root, *p, *find;
char x = 'E';
Initiate(&root);
p = InsertLeftNode(root, 'A');
p = InsertLeftNode(p, 'B');
p = InsertLeftNode(p, 'D');
p = InsertRightNode(p, 'G');
p = InsertRightNode(root->leftchild, 'C');
InsertLeftNode(p, 'E');
InsertRightNode(p, 'F');
printf("打印二叉树:\n");
PrintBiTree(root, 0);
printf("前序遍历: ");
PreOrder(root->leftchild, Visit);
printf("\n中序遍历: ");
InOrder(root->leftchild, Visit);
printf("\n后序遍历: ");
PostOrder(root->leftchild, Visit);
find = Search(root, x);
if (find != NULL) {
printf("\n数据元素%c在二叉树中", x);
}
else {
printf("\n数据元素%c不在二叉树中", x);
}
int count = Count(root->leftchild);
printf("\n二叉树中的结点总数为%d\n", count);
printf("二叉树的叶子结点为:");
InOrder(root->leftchild);
printf("\n");
int leaf = Leaf(root->leftchild);
printf("二叉树中的叶子节点数目为:%d\n", leaf);
int leaf2 = leaf_2(root->leftchild);
printf("二叉树中度为2的结点数目为:%d\n", leaf2);
/*交换二叉树各结的左右子树*/
swap(root->leftchild);
printf("前序遍历: ");
PreOrder(root->leftchild, Visit);
Destroy(&root);
printf("\n");
return 0;
system("pause");
}
运行结果: