二叉树.c

建立二叉树

#include<stdio.h>
#include<malloc.h>
typedef struct node
{int data;
 struct node *lc,*rc;
}Node,*bitreptr,*tpointer;
bitreptr create(bitreptr root) //建立二叉树
{int x;
 scanf("%d",&x);
 if(x>0)
  {root=(bitreptr)malloc(sizeof(Node));
   root->data=x;
   root->lc=create(root->lc);
   root->rc=create(root->rc);
  }
  else root=0;
  return root;
}
void inorder1(bitreptr root) //前根遍历
{if(root)
 {printf("%5d",root->data);
  inorder1(root->lc);
  inorder1(root->rc);
  }
}

void inorder2(bitreptr root) //中根遍历
{if(root)
 {
  inorder2(root->lc);
  printf("%5d",root->data);
  inorder2(root->rc);
  }
}
int  count1(bitreptr root) //求结点个数
{if(root==0)
   return 0;
 else if(root->lc==0&&root->rc==0)
	  return 1;
 else return count1(root->lc)+count1(root->rc)+1;
}

int depth(bitreptr root) //求树深度
{if(root==0) return 0;
 else if(root->lc==0&&root->rc==0)
	 return 1;
 else 
	 return depth(root->lc)+1>depth(root->rc)+1?depth(root->lc)+1:depth(root->rc)+1;
}
int count2(bitreptr root,int x) //求具有某种特征结点数
{if(root==0) return 0;
 else if(root->data==x)
	 return count2(root->lc,x)+count2(root->rc,x)+1;
 else return   count2(root->lc,x)+count2(root->rc,x);
}

bitreptr location(bitreptr root,int x)  //求值为X的结点的位置
{if(root==0) return 0;
 else if(root->data==x) return root;
 else 
   if(location(root->lc,x))
    return location(root->lc,x);
   else return location(root->rc,x);
}

int cout(bitreptr p) //求度为2的顶点个数
{if(p==0) return 0;
else if(p->lc&&p->rc)
 return 1+cout(p->lc)+cout(p->rc);
else return cout(p->lc)+cout(p->rc);
}
void main()
{bitreptr root;

 root=create(root);
 printf("\n\n");
 inorder1(root); //前根遍历
 printf("\n\n");
 inorder2(root); //中根遍历
 printf("\n%d",count1(root)); //求结点个数
 printf("\n%d",depth(root)); //求树深度
 printf("\n%d",count2(root,5)); //求具有某种特征结点数
 printf("\n%d",location(root,5)->data); //值为X的结点的位置
 printf("\n%d",cout(root));

}