二叉树的几种运算方法

　2008-03-08 12:44:06　来源：WEB开发网　闂傚倷绶氬ḿ褍螞閹绢喖绠柨鐕傛嫹

闂傚倷绀侀幉锟犲垂閻㈠灚宕查柟鎵閸庡秵銇勯幒鎴濃偓鐢稿磻閹炬枼妲堟繛鍡楃С濞岊亞绱撻崒姘扁枌闁瑰嚖鎷�

婵犵數濮幏鍐川椤撴繄鎹曢梻渚€娼уú銈吤洪妸鈺佺劦妞ゆ帊鑳堕埊鏇㈡煏閸モ晛浠х紒杈╁仱閺佹捇鏁撻敓锟�闂傚倷绶氬ḿ褍螞閹绢喖绠柨鐕傛嫹　　闂傚倷鑳舵灙缂佺粯顨呴埢宥夊即閵忕姵鐎梺缁樺姈椤愮厧鈽夊Ο閿嬬€婚梺褰掑亰閸撴稑鈻斿鑸碘拺闁告稑饪村▓鏃€绻涚仦鍌氬闁崇粯鎹囬獮瀣攽閹邦剚顔傛俊鐐€栧濠氬储瑜忛幉鎾晸閿燂拷

核心提示：1.二叉树的前序遍历先访问根结点,再访问左子树,最后访问右子树的次序访问二叉树中所有的结点,且每个结点仅访问一次.void PReorder(BTree *p){if(p!=NULL){ printf("%d",p->data);preorder(p->left);preorder(p-

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);
　　}
}