二叉树的几种运算方法

【 tulaoshi.com - 编程语言 】

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(dep1dep2)return(dep1+1);
　　        else return(dep2+1);
　　    }
　　}