二叉树的操作--简单

二叉树的操作--简单 

#include <iostream>
#include <stack>

using namespace std;

typedef struct bitreenode
{
  char data;
  struct bitreenode *lchild,*rchild;
}*Bitree;

//创建二叉树
void createbitree(Bitree &T)
{
  char data;
  data=getchar();
  if(data=='#')
  {
    T=NULL;
  }
  else
  {
    T=new bitreenode;
    T->data=data;
    createbitree(T->lchild);
    createbitree(T->rchild);
  }
};

//递归的先序遍历二叉树
void preordertraverse(Bitree T)
{
  if(T)
  {
    cout<<T->data<<" ";//输出根结点
    preordertraverse(T->lchild);
    preordertraverse(T->rchild);
  }
}

//递归的中序遍历二叉树
void inordertraverse(Bitree T)
{
  if(T)
  {
    inordertraverse(T->lchild);
    cout<<T->data<<" ";//输出根结点
    inordertraverse(T->rchild);
  }
}

//递归的后序遍历二叉树
void postordertraverse(Bitree T)
{
  if(T)
  {
    postordertraverse(T->lchild);
    postordertraverse(T->rchild);
    cout<<T->data<<" ";//输出根结点
  }
}

//求二叉树的深度
int depthofbitree(Bitree T)
{
  int ldepth;
  int rdepth;
  if(T==NULL) //空树
  {
    return 0;
  }

  ldepth=depthofbitree(T->lchild);
  rdepth=depthofbitree(T->rchild);

  if(ldepth>rdepth)
    return ldepth+1;
  else
    return rdepth+1;
}

//求二叉树的叶子结点
int leafcount(Bitree T)
{
  if(T==NULL)
  {
    return 0;
  }
  else if(T->lchild==NULL && T->rchild==NULL)
  {
    return 1;
  }
  else
  {
    int n=leafcount(T->lchild);//求左子树叶子的数目
    int m=leafcount(T->rchild);//求右子树叶子的数目
    return n+m;
  }
}

//求二叉树T中度为1的结点的数量
int onesoncount(Bitree T)
{
  if(T==NULL)
  {
    return 0;
  }
  else if((T->lchild==NULL && T->rchild!=NULL) ||(T->lchild!=NULL && T->rchild==NULL))
  {
    cout<<"度为1的结点的字母为:"<<T->data<<endl;
    return (onesoncount(T->lchild) +onesoncount(T->rchild) +1);
  }
  else
  {
    return (onesoncount(T->lchild) +onesoncount(T->rchild));
  }
}

//求非叶子结点的数目
int notleafcount(Bitree T)
{
  if(T==NULL)
  {
    return 0;
  }
  else if(T->lchild == NULL && T->rchild == NULL)
    return 0;
  else
  {
    cout<<T->data; //输出非终端结点的值
    int n=notleafcount(T->lchild); //左子树非终端结点的数目
    int m=notleafcount(T->rchild); //右子树非终端结点的数目
    return (m+n+1);
  }
}

//求二叉树的全部结点数目
int node_num(Bitree T)
{
  if(T==NULL)
    return 0;
  else
    return node_num(T->lchild)+node_num(T->rchild)+1;
}

///////////////主函数///////////////
void main()
{
  Bitree t=NULL;
  printf("请按以下两种序列输入二叉树的结点:\n");
  printf("AB#D##CE### 或 ABD##E##C#F##\n");
  createbitree(t);
  cout<<"先序遍历:";
  preordertraverse(t);
  cout<<endl;

  cout<<"中序遍历:";
  inordertraverse(t);
  cout<<endl;

  cout<<"后序遍历:";
  postordertraverse(t);
  cout<<endl;

  cout<<"二叉树的深度为:"<<depthofbitree(t)<<endl;

  int leaf=0; //叶子结点数目,初始化为0
  leaf=leafcount(t);
  cout<<"叶子结点数为:"<<leaf<<endl;

  int oneson=0; //度为1的结点数目
  oneson=onesoncount(t);
  cout<<"度为1的结点的数量为:"<<oneson<<endl;

  int notleafcount_=0; //非叶子结点的数目,初始化为0
  cout<<"非叶子结点为:";/////////////
  notleafcount_=notleafcount(t);//////////////????????
  cout<<endl;
  cout<<"非叶子结点的数量为:"<<notleafcount_<<endl;

  int node_number=0; //初始化全部结点的数目为0
  node_number=node_num(t);
  cout<<"二叉树全部结点的数量为:"<<node_number<<endl;

}

运行结果:

二叉树的操作--简单

 

上一篇:数据结构 七 二叉树的遍历


下一篇:A1043 Is It a Binary Search Tree (25分)