二叉树的递归遍历和性质

二叉树

1.结点结构

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

二叉树的性质

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

揭示了度为2的节点和叶子节点的关系

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

3.高度为H的二叉树至多有 个结点
是性质2的等比数列求和
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;