目录

  • 二叉树的定义
  • 二叉树的性质
  • 二叉链表的基本操作
    • 二叉链表的结构定义
    • 前序遍历创建
    • 前序、中序、后序遍历
    • 中序遍历的非递归算法（栈）
    • 层次遍历（队列）
    • 复制二叉树
    • 计算深度
    • 计算总结点数与叶子结点数
    • 后序销毁

二叉树的定义

二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分 [1] 。
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个节点 [1]

来自百度百科。由“科普中国”科学百科词条编写与应用工作项目 审核 。

二叉树的性质

  1. 在二叉树的第 i 层最多有2i-1个结点（i>=1）.
  2. 深度为 k 的二叉树最多有 2k – 1 个结点（k>=1） .
  3. 如果二叉树的终端结点数为 n0 ，度为 2 的结点数为 n2 ,
    则 n0 = n2 + 1 .
  4. 具有 n 个结点的完全二叉树深度为 [ log2 n ] + 1 ( [x] 表示不大于x的最大整数) .
  5. 对一个有 n 个结点的完全二叉树按层序编号,
    对任一结点 i 有：
    （1） i = 1 ，则结点 i 是二叉树的根，无双亲; i > 1，其双亲是结点[i/2]
    （2） 2 * i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则左孩子是结点 2 * i .
    （3） 2 * i + 1 > n， 则结点 i 无右孩子，否则其右孩子是结点 2 * i + 1 .

二叉链表的基本操作

二叉树每个结点最多有两个孩子，为它设计一个数据域和两个指针域，即叫做二叉链表。

二叉链表的结构定义

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0typedef char BitreeElemType;
typedef struct BiNode {BitreeElemType data;struct BiNode* lchild, * rchild;
}BiNode;
typedef struct BiNode* BiTree;

前序遍历创建


/* 前序遍历创建 */
void CreateBiTree(BiTree* T)
{BitreeElemType ch;scanf(" %c", &ch);if (ch == '#') //我们用'#'表示空树*T = NULL;else {*T = (BiTree)malloc(sizeof(BiNode));(*T)->data = ch;       //生成根结点CreateBiTree(&(*T)->lchild); //构造左子树CreateBiTree(&(*T)->rchild); //构造右子树}
}

前序、中序、后序遍历

/* 前序遍历 */
void PreOrderTraverse(BiTree T)
{if (!T) return;printf("%cn", T->data);PreOrderTraverse(T->lchild); //先序遍历左子树PreOrderTraverse(T->rchild); //先序遍历右子树
}/* 中序遍历 */
void InOrderTraverse(BiTree T)
{if (!T) return;InOrderTraverse(T->lchild); //先序遍历左子树printf("%cn", T->data);InOrderTraverse(T->rchild); //先序遍历右子树
}/* 后序遍历 */
void PostOrderTraverse(BiTree T)
{if (!T) return;PostOrderTraverse(T->lchild); //先序遍历左子树PostOrderTraverse(T->rchild); //先序遍历右子树printf("%cn", T->data);}

中序遍历的非递归算法（栈）

基本思路：
1.建立栈
2.根结点入栈 ，遍历左左子树
3.根结点出栈，输出根结点,遍历右子树

/* 中序遍历的非递归算法 */void InOrderTraverse_Stack(BiTree T)
{SqStack S;InitStack(&S);BiTree p = T;while (p || !IsEmpty(S)){if (p){Push(&S, p);//根结点入栈(顺序入栈一定要同类型呀，注意SElemType为Bitree)p = p->lchild;}else{Pop(&S,&p);//原栈顶元素给p(顺序处栈也要同类型，注意SElemType为Bitree)//输出根结点,遍历右子树printf("%cn", p->data);p = p->rchild;}}
}
/*-------------------- ↓所需其它操作↓------------------------ */
//栈结构
#define MAXSIZE 100
typedef BiTree SElemType;
typedef struct {SElemType* top;  //顺序栈顶指针SElemType* base; //顺序栈底指针int stacksize;   //顺序栈最大容量
}SqStack;/* 初始化顺序栈 */
int InitStack(SqStack* S)
{S->base = (SElemType*)malloc(MAXSIZE * sizeof(SElemType));if (!S->base) exit(-1);  //失败S->top = S->base;  //栈顶指针 = 栈底指针S->stacksize = MAXSIZE;return OK;
}
/* 判断空栈*/
int IsEmpty(SqStack S)
{if (S.base == S.top)return OK;elsereturn ERROR;
}
/* 顺序栈的入栈 */
int Push(SqStack* S, BiTree Tree)
{if (S->top - S->base == S->stacksize)  //栈满了return ERROR;*++S->top = Tree;  // S->top++; *S->top = Tree;return OK;
}
/* 顺序栈的出栈 */
int Pop(SqStack* S,BiTree *Tree)
{if (S->top == S->base)   //空栈return ERROR;*Tree = *S->top--;  // *Tree = *S->top; S->top--; return OK;
}

层次遍历（队列）

/* 层次遍历 */
void LevelOder(BiTree T)
{BiTree p = NULL;SqQueue Q;InitQueue(&Q);EnQueue(&Q, T);   //根结点入队while (Q.front != Q.rear)  //队不为空，循环{DeQueue(&Q, &p);   //出队结点pprintf("%cn", p->data);if (p->lchild)    //有左孩子,入队EnQueue(&Q, p->lchild);if (p->rchild)    //有右孩子,入队EnQueue(&Q, p->rchild);}
}
/*-------------------- ↓所需其它操作↓------------------------ */
//队列结构
typedef BiTree QElemType;
typedef struct {QElemType* base;  //动态分配存储空间int front;     //头指针int rear;      //尾指针
}SqQueue;/* 初始化循环队列 */
int InitQueue(SqQueue* Q)
{Q->base = (QElemType*)malloc(MAXSIZE * sizeof(QElemType));if (!Q->base) exit(-1);Q->front = Q->rear = 0; //头指针与尾指针都为0return OK;
}
/* 循环队列入队 */
int EnQueue(SqQueue* Q, QElemType Tree)
{if ((Q->rear + 1) % MAXSIZE == Q->front)  //队满return ERROR;Q->base[Q->rear] = Tree;Q->rear = (Q->rear + 1) % MAXSIZE;  //队尾指针 + 1return OK;
}
/* 循环队列出队 */
int DeQueue(SqQueue* Q, QElemType* Tree)
{if (Q->front == Q->rear) return ERROR;*Tree = Q->base[Q->front];Q->front = (Q->front + 1) % MAXSIZE;  //队头指针 + 1return OK;
}

复制二叉树

/* 复制二叉树 */
void Copy(BiTree T, BiTree* NewT)
{if (!T){*NewT = NULL;return;}else{*NewT = (BiTree)malloc(sizeof(BiTree));(*NewT)->data = T->data;Copy(T->lchild, &(*NewT)->lchild);Copy(T->rchild, &(*NewT)->rchild);}
}

计算深度

递归计算左右子树的深度，二叉树的深度为二者的较大值加 1 .

/* 计算深度 */
int Depth(BiTree T)
{if (!T) return 0;return Depth(T->lchild) > Depth(T->rchild) ? Depth(T->lchild) + 1 : Depth(T->rchild) + 1;}

计算总结点数与叶子结点数

/* 计算总结点数 */
int Nodes(BiTree T)
{if (!T) return 0; //空树elsereturn Nodes(T->lchild) + Nodes(T->rchild) + 1;
}/* 计算叶子结点数 */
int LeafNodes(BiTree T)
{if (!T)    //空树return 0;if (!T->lchild && !T->rchild) //叶子结点return 1;elsereturn LeafNodes(T->lchild) + LeafNodes(T->rchild);
}

后序销毁


/* 后序销毁二叉树 */
void Destroy(BiTree* T)
{if (!(*T)) return;else{Destroy(&(*T)->lchild);Destroy(&(*T)->rchild);free(*T);*T = NULL;}}