1.二叉樹的前序遍歷
先訪問根結點,再訪問左子樹,最後訪問右子樹的次序訪問二叉樹中所有的結點,且每個結點僅訪問一次.
void preorder(BTree *p)
{
if(p!=NULL)
{ printf("%d",p->data);
preorder(p->left);
preorder(p->right);
}
}
2.二叉樹的中序遍歷
先訪問左子樹,再訪問根結點,最後訪問右子樹的次序訪問二叉樹的所有結點,且每個結點僅訪問一次.
void inorder(btree *p)
{
if(p!=NULL)
{ inorder(p->left);
printf("%d",p->data);
inorder(p->right);
}
}
3.後序遍歷
先訪問左子樹,再訪問右子樹,最後訪問根結點的次序訪問二叉樹中所有的結點,且每個結點僅訪問一次
void postorder(btree *p)
{
if(p!=NULL)
{ postorder(p->left);
postorder(p->right);
printf("%d",p->data);
}
}
4.輸出二叉樹
首先輸出根結點,然後再輸出它的左子樹和右子樹.依次輸出的左,右子樹要至少有一個不能為空.
void print(btree *b)
{
if(b!=NULL)
{ printf("%d",b->data);
if(b->left!=NULLb->right!=NULL)
{ printf("(");
printf(b->left);
if(b->right!=NULL)printf(",");
printf(b->right);
printf(")");
}
}
}
5.求二叉樹的深度
若一棵二叉樹為空,則其深度為0,否則其深度等於左子樹和右子樹的最大深度加1,即有如下遞歸模型:
depth(b)=0 /*假如b=NULL*/
depth(b)=max(depth(b->left,b->right)+1 /*其它*/
因此求二叉樹深度的遞歸函數如下:
int depth(btree *b)
{
int dep1,dep2;
if(b==NULL)return(0);
else
{ dep1=depth(b->left);
dep2=depth(b->right);
if(dep1>dep2)return(dep1+1);
else return(dep2+1);
}
}
