⼆叉树C 语⾔基本定义+操作代码+注释详解（⼆叉树的递归⾮递归遍历⽅法）⼆叉树C 语⾔基本定义+操作代码+注释详解
1.树的基本特点
1. ⼦树不相交
2. j结点的度：结点的⼦树个数
3. 叶节点：度为0的结点
4. 除根节点，每个结点有且仅有⼀个⽗结点
5. ⼀颗N个结点的树有N-1条边
6. 查成功时查次数不会超过判定树的深度（n个结点的判定树深度为
7. 结点的层次：规定根结点在1层，其他任⼀结点的层数是其⽗结点层数+1；
8. 树的深度：所有结点的最⼤层次是树的深度 9.
1.1.⼉⼦兄弟表⽰法
对于⼀般的树，可以设计⼀个基本结构体，包含⼀个数据两个指针，分别指向第⼀个孩⼦树和下⼀个兄弟树。
将⽤⼉⼦兄弟表⽰法的树旋转45°，即可得到⼀种特殊的树——⼆叉树！
2.⼆叉树定义性质即储存
2.1.⼆叉树的基本性质
log n +21
1. ⼀个⼆叉树第i层的最⼤结点数为
2. 深度为k的⼆叉树有最⼤结点总数为
3. 对于任何⾮空⼆叉树T，若  表⽰叶节点个数， 表⽰有两个⼦结点的结点数，那么两者关系为  。（结论证明：从下
往上看，所有边数为 【为只有⼀个孩⼦的结点，每个结点贡献⼀条向上的边，唯⼀个根节点除外】从上往下看，三种结点分别贡献和⾃⼰⼦树个数相等的边数即：,⽤两种⽅法分别表⽰边数相等，得证）
操作集1.创建⼀颗⼆叉树BinTree CreatBinTree();
2.⼆叉树的遍历void Traversal(BTTree BT);
3.判断⼆叉树是否为空int Isempty(BinTree BT);
2.2.数组表⽰⽅法
数组适合表⽰完全⼆叉树，⽽对于⼀般的⼆叉树，需要补充为完全⼆叉树，会导致空间浪费。
完全⼆叉树：按从上⾄下，从左⾄右的顺序储存n个结点的完全⼆叉树的结点⽗⼦关系。
1. ⾮根结点（i>1）的⽗结点的序号是.（上图序号为5的结点的⽗结点为整数相除结果取整即为2。
2. 序号为 的结点的左孩⼦结点序号是，若则没有左孩⼦（上图序号为6的结点左孩⼦序号为12>总结点数10，即序号6没有左
孩⼦）
3.
2. 序号为 的结点的右孩⼦结点序号是，若则没有右孩⼦（上图序号为6的结点右孩⼦序号为13>总结点数10，
即序号6没有右孩⼦）
2.3.链表的表⽰⽅法
结构体
2i −1
2−k 1
n 0n 2n =0n +21n +0n +1n −21n 10∗n +01∗n +12∗n =2n +0n +1n −21i /25/2=2.5i 2i 2i >n i 2i +12i +1>n
typedef struct TreeNode *BinTree; struct TreeNode{
ElementType Data;
BinTree left;
BinTree right;
};
3.⼆叉树的递归遍历
3.1.先序遍历
1. 访问根结点
2. 先序遍历左⼦树
3. 先序遍历右⼦树
void PreOrderTraversal(BinTree BT) {
if(BT)
{
printf("%d",BT->Data);
PreOrderTraversal(BT->left);
PreOrderTraversal(BT->right); }
}
3.2.中序遍历
1. 中序遍历左⼦树
2. 访问根结点
3. 中序遍历右⼦树
void inOrderTraversal(BinTree BT) {
if(BT)
{
PreOrderTraversal(BT->left);
printf("%d",BT->Data);
PreOrderTraversal(BT->right); }
}
3.2.后序遍历
1. 后序遍历左⼦树
2. 后序遍历右⼦树
3. 访问根结点
void PostOrderTraversal(BinTree BT);
{
if(BT)
{
PreOrderTraversal(BT->left);
PreOrderTraversal(BT->right);
printf("%d",BT->Data);
}
}
上述三种遍历过程经过结点的路线⼀样，只是访问各结点的时机不同4.⼆叉树遍历⾮递归算法（利⽤堆栈）
4.1先序遍历
1.遇到⼀个结点，就把它压栈，并访问这个结点
2.当左⼦树遍历结束后，从栈顶弹出这个结点
3.按其右指针再去先序遍历该节点的右⼦树
void InorderTraversal(BinTree BT)
{
BinTree T=BT;
stack S=gen();//创建并初始化栈
while( T ||!IsEmpty(S))
{二叉树的基本性质
while(T)//⼀直向左并将沿途结点压⼊栈内
{
Push(S,T);//第⼀次遇到该结点
printf("%d",T->Data);//访问结点
T=T->left;
}
if(!IsEmpty(S))//程序进⾏到此左树已遍历结束
{
T=Pop(S);//结点弹出堆栈
T=T->right;//转向右⼦树
}
}
}
4.2中序遍历
和先序遍历相⽐，仅仅改变了printf("%d",T->Data);//访问结点语句的位置