二叉树，每个结点⾄多只有2颗⼦树
结点的⾼度: 结点到叶⼦结点的最⻓路径(边数)， 结点 -> 叶子结点
结点的深度: 根结点到这个结点所经历的边的个数， 结点 -> 根节点
结点的层数: 结点的深度-1
树的⾼度 : 根结点的⾼度
层序遍历：根结点开始访问,从上⽽下逐层遍历,在同⼀层中, 按从左到右的顺序对结点逐个访问
完全⼆叉树：结点 从上⽽下逐层，从左到右的顺序 都存在
去掉3， 不是完全二叉树
去掉5， 不是满二叉树，是完全二叉树
完全二叉树，顺序结构储存具备下面特性， 结点从1开始编号
A.如果i>1，那么序号为i的结点的双亲结点序号为i/2；
B.如果i=1，那么序号为i的结点为根节点，无双亲结点；
C.如果2i<=n，那么序号为i的结点的左孩子结点序号为2i；
D.如果2i>n，那么序号为i的结点无左孩子；
E.如果2i+1<=n，那么序号为i的结点右孩子序号为2i+1；
F.如果2i+1>n，那么序号为i的结点无右孩子。
G 有n个结点的完全二叉树深度为(log2(n))+1
二叉树遍历
前序遍历：遍历顺序 根结点 -> 左⼦树 -> 右⼦树
中序遍历：遍历顺序 左⼦树 -> 根结点 -> 右⼦树
后序遍历：遍历顺序 左⼦树 -> 右⼦树 -> 根结点
遍历
二叉树创建代码实现
1.顺序结构
定义一个数组储存，长度是100
typedef CElemType SqBiTree[MAX_TREE_SIZE];
数据是根据 二叉树的层序遍历顺序得到的
Status CreateBiTree(SqBiTree T){
int i =0;
/*
1 -->1
2 3 -->2
4 5 6 7 -->3
8 9 10 -->4
1 2 3 4 5 6 7 8 9 10 Nil Nil Nil
*/
while(i <10) {
T[i] = i+1;
printf("%d ",T[i]);
//结点不为空,且无双亲结点
if(i !=0&& T[(i+1)/2-1] ==Nil&& T[i] !=Nil) {
printf("出现无双亲的非根结点%d\n",T[i]);
exit(ERROR);
}
i++;
}
//将空赋值给T的后面的结点
while (i < MAX_TREE_SIZE) {
T[i] =Nil;
i++;
}
return OK;
}
获取二叉树的深度, 是一个完全二叉树，深度为(log2(n))+1
int BiTreeDepth(SqBiTree T){
int j = -1;
int i;
//找到最后一个结点
//MAX_TREE_SIZE -> 100 -> 10 目的找到最后一个结点10的位置
for(i =MAX_TREE_SIZE-1; i>=0; i--) {
if(T[i] !=Nil)
break;
}
do {
j++;
} while (powl(2, j) <= i);//计算2的次幂
return j;
}
获取结点的双亲， 完全二叉树特性：i / 2
获取结点的左孩子：2i
获取结点的右孩子：2i + 1
获取结点的兄弟结点：i + 1 或 i - 1
前序遍历： 根结点 -> 左结点 -> 右结点
递归 完成
递归 入口
Status PreOrderTraverse(SqBiTree T){
//树不为空
if(!BiTreeEmpty(T)) {
PreTraverse(T,0);
}
printf("\n");
return OK;
}
void PreTraverse(SqBiTree T,int e){
//打印结点数据 根结点
visit(T[e]);
//先序遍历左子树
if(T[2* e +1] !=Nil) {
左结点
PreTraverse(T,2*e+1);
}
//最后先序遍历右子树
if(T[2* e +2] !=Nil) {
右结点
PreTraverse(T,2*e+2);
}
}
2. 链表结构
结点 结构体
typedef struct BiTNode /* 结点结构 */
{
CElemTypedata; /* 结点数据 */
structBiTNode*lchild,*rchild;/* 左右孩子指针 */
} BiTNode,*BiTree;
数据（前序遍历顺序） ABD##E#H#K##CFI###G#J##（# 空）
按前序输入二叉树中的结点值(字符),#表示空树
void CreateBiTree(BiTree *T){
CElemType ch;
//获取字符
ch =str[indexs++];
//判断当前字符是否为'#'
if(ch =='#') {
*T =NULL;
}else {
//创建新的结点
*T = (BiTree)malloc(sizeof(BiTNode));
//是否创建成功
if(!*T) {
exit(OVERFLOW);
}
/* 生成根结点 */
(*T)->data= ch;
/* 构造左子树 */
CreateBiTree(&(*T)->lchild);
/* 构造右子树 */
CreateBiTree(&(*T)->rchild);
}
}
二叉树T的深度 不懂（代码断点调试）
int BiTreeDepth(BiTree T){
int i,j;
if(!T)
return 0;
//计算左孩子的深度
if(T->lchild)
i=BiTreeDepth(T->lchild);
else
i=0;
//计算右孩子的深度
if(T->rchild)
j=BiTreeDepth(T->rchild);
else
j=0;
//比较i和j
return i>j?i+1:j+1;
}
前序遍历 递归完成
void PreOrderTraverse(BiTree T)
{
if(T==NULL)
return;
printf("%c",T->data);/* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
线索二叉树， 结点的左结点或右结点为空的话，赋值 当前结点的前驱或后继
创建一个虚拟头结点
中序遍历
Link==0表示指向左右孩子指针
Thread==1表示指向前驱或后继的线索
typedef enum {Link,Thread} PointerTag;
线索二叉树存储结点结构
typedef struct BiThrNode{
//数据
CElemType data;
//左右孩子指针
struct BiThrNode *lchild, *rchild;
//左右标记
PointerTag LTag;
PointerTag RTag;
} BiThrNode, *BiThrTree;
