一、树的定义
? 1、树的定义：树是n个结点的有限集。当n=0时成为空树，在任意一颗非空树中：
- 有且只有一个特定的称为根结点
- 当n>1时，其余结点可分为m个互不相交的有限集，其中每一个集合又是一棵树，并且称为根的子树。
2、二叉树性质
- 第i层上至多有2^(i-1)个结点(i>=1)。
- 深度为k的二叉树至多有2k-1个结点(k>=1)。
- 如果i=1，则结点i是二叉树根；
- i>1,则其双亲结点为i/2；
- 2i>n,则结点i无左孩子，否则左孩子结点为2i；
- 2i+1>n,则结点i无右孩子，否则右孩子结点为2i+1;(i为叶子结点，n为结点总数)
3、二叉树链式结构
typedef struct BiTNode ?/* 结点结构 */
{
? ?TElemType data;?? ??? ?/* 结点数据 */
? ?struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
4、建立空二叉树
void InitBiTree(BiTree *T)
{?
?? ?*T=NULL;
}
5、建立一个二叉树
void CreateBiTree(BiTree *T)
{
?? ?char c;
?? ?scanf("%c",c);
?? ?if(' '==c)
?? ?{
?? ??? ?*T=NULL;
?? ?}
?? ?else
?? ?{
?? ??? ?*T=(BiTNode*)malloc(sizeof(BiTNode));
?? ??? ?(*T)->data=c;
?? ??? ?CreateBiTree(&(*T)->lchild);
?? ??? ?CreateBiTree(&(*T)->rchild);
?? ?}
}
二、二叉树的遍历
二叉树的遍历特点：从左到右
1、先序遍历：
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。
2、中序遍历
若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
3、后序遍历
若树为空，则空操作返回，否则从左到右叶子后结点的方式遍历访问左右子树，最后访问根结点
4、层序遍历
若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
- 代码：
//前序递归遍历T
void PreOrderTraverse(BiTree T)
{?
?? ?if(T==NULL)
?? ??? ?return;
?? ?printf("%c",T->data);
?? ?PreOrderTraverse(T->lchild);
?? ?PreOrderTraverse(T->rchild);
}
//中序递归遍历T
void InOrderTraverse(BiTree T)
{?
?? ?if(T==NULL)
?? ??? ?return;
?? ?InOrderTraverse(T->lchild);?
?? ?printf("%c",T->data);
?? ?InOrderTraverse(T->rchild);?
}
//后序递归遍历T
void PostOrderTraverse(BiTree T)
{
?? ?if(T==NULL)
?? ??? ?return;
?? ?PostOrderTraverse(T->lchild);
?? ?PostOrderTraverse(T->rchild);
?? ?printf("%c",T->data);
}三、线索二叉树
//二叉线索存储结点结构
typedef ?struct BiThrNode
{
?? ?TElemType data;
?? ?struct BiThrNode *lchild, *rchild;
?? ?PointerTag LTag;
?? ?PointerTag RTag;
} BiThrNode, *BiThrTree;
- Ltag为0时指向该结点的左孩子，为1时指向该结点的前驱
- Rtag为0时指向该结点的右孩子，为1时指向该结点的后继
- 枚举法 类型+enum+{}
例子：一次定义多个常量
#include<stdio.h>
Enum week{Mon=1,Tue,Wed,Thu,Fri,Sat,Sun};
Int main()
{
?? ?printf(“%d”,Tue);
?? ?return 0;
}
这样定义后，Mon的值为1，Tue的值为2，Wed为3，依次类推，如果开头不写Mon=1的话，Mon默认值为0，然后从0开始加。
- 树结点间的连线相关的树叫做权。
