二叉树的递归遍历和性质

##二叉树 1.结点结构

typedef struct BiTNode{
ElemType data;                             //数据域
struct BiTNode *lchild,*rchild;             //指向该结点的左、右孩子指针
}BiTNode,*BiTree;                         //二叉树结点结构
复制代码

##二叉树的性质

1. 非空二叉树上的叶子结点树等于度为2的结点树加1

<figcaption> 图片标题 </figcaption>

<figcaption> 图片标题 </figcaption>

2.非空二叉树上第k层至多有

<figcaption> 图片标题 </figcaption>

3.高度为H的二叉树至多有

<figcaption> 图片标题 </figcaption>

4.具有N个结点的完全二叉树的高度为

##二叉树的遍历 ###先序遍历

void PreOrder(BiTree T){
if(T!=NULL){
printf(“%c”,T->data) //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
复制代码

###后序遍历和中序顺序相反。 ###层序遍历

void LevelOrder(BiTree b){
InitQueue(Q);
BiTree p;
EnQueue(Q,b); //根结点进队
while(!IsEmpty(Q)){ //队列不空循环
DeQueue(Q，p) //队头元素出队
printf(“%c”,p->data);
if(p->lchild!=NULL)
EnQueue(Q,p->lchild);
if(p->rchild!=NULL)
EnQueue(Q,p->rchild);
}
}
复制代码

##二叉树的线索化 对二叉树以某种次序遍历使其变为线索二叉树的过程就叫做线索化 指向前驱和后继，增加标识符，标识是指向孩子还是前驱和后继

ypedef struct ThreadNode{
ElemType data;
struct ThreadNode *lchild,*rchild;
int ltag,rtag;
}ThreadNode,*ThreadTree; 
复制代码