BiTree.h:顺序存储二叉树及其基本操作

enum {MAX_TREE=100,OK=0,WRONG=-1};
typedef int BTree[MAX_TREE];
typedef int Status;

struct position
{
 int level,order;
};

void InitBiTree(BTree &T)
{
 memset(T,0,sizeof(int)*MAX_TREE);
}

Status CreateBiTree(BTree &T)
{
 InitBiTree(T);
 int i=0,j;
 std::cout<<"按层顺序输入节点的值，0表示空节点，888退出:";
 while(1)
 {
  std::cin>>T[i];
  if(T[i]==888)
  {
   T[i]=0;
   break;
  }
  i++;
 }
 //j=1避开了根节点！
 for(j=1;j!=i;j++)
  if(T[j]!=0&&T[(j+1)/2-1]==0)
  {
   std::cout<<"出现了无双亲的子节点，退出！"<<std::endl;
   return WRONG;
  }
 return OK;
}

int BiTreeDepth(BTree T)
{
 //注意找最后一个节点时候MAX_TREE-1
 //不要完了2^层数-1，1不要忘了
 int i=0,j=0;
 for(i=MAX_TREE-1;T[i]==0;i--);

 
 while(pow(2,j)<=i+1)
  j++;
 
 return j;
}

bool BiTreeEmpty(BTree T)
{
 return T[0]==0;
}

Status Root(BTree T,int &e)
{
 if(BiTreeEmpty(T))
  return WRONG;
 e=T[0];
 return OK;
}

Status Assign(BTree T,position pos,int e)
{
 int i=pow(2,pos.level-1)+pos.order-2;
 if(e!=0 && T[(i+1)/2-1]==0)
 {
  std::cout<<"欲赋值的节点无双亲节点"<<std::endl;
  return WRONG;
 }
 if(e==0 && (T[2*i+1]!=0||T[2*i+2]!=0))
 {
  std::cout<<"无法给有孩子节点的双亲赋0值"<<std::endl;
  return WRONG;
 }
 T[i]=e;
 return OK;
}

int Parent(BTree T,int e)
{
 int i;
 for(i=1;i<MAX_TREE;i++)
 {
  if(T[i]==e)
   return T[(i+1)/2-1];
 }
 return 0;
}

int LeftChild(BTree T,int e)
{
 int i;
 if(T[0]==0)
  return 0;
 for(i=0;i<MAX_TREE;i++)
  if(T[i]==e)
   return T[2*i+1];
 return 0;
}

int RightChild(BTree T,int e)
{
 int i;
 if(T[0]==0)
  return 0;
 for(i=0;i<MAX_TREE;i++)
  if(T[i]==e)
   return T[2*i+2];
 return 0;
}

int LeftSibling(BTree T,int e)
{
 int i;

 if(T[0]==0)
  return 0;

 for(i=0;i<MAX_TREE;i++)
  if(T[i]==e)
  {
   if(i%2==0)
    return T[i-1];
  }
 return 0;
}

int RightSibling(BTree T,int e)
{
 int i;

 if(T[0]==0)
  return 0;

 for(i=0;i<MAX_TREE;i++)
  if(T[i]==e)
  {
   if(i%2==1)
    return T[i+1];
  }
 return 0;
}

void Move(BTree &Q,int j,BTree &T,int i)
{
 if(Q[j*2+1]!=0)
  Move(Q,j*2+1,T,i*2+1);
 if(Q[j*2+2]!=0)
  Move(Q,j*2+2,T,i*2+2);
 T[i]=Q[j];
 Q[j]=0;
}

void Insert(BTree &S,BTree&T,int t,int LR)
{
 int i,k;
 for(i=1;i<MAX_TREE;i++)
  if(T[i]==t)
   break;
 
 k=2*i+1+LR;
 if(T[k]!=0)
  Move(T,k,T,2*k+2);
 Move(S,0,T,k);
}

int GetValue(BTree T,position pos)
{
 int i=pow(2,pos.level-1)+pos.order-2;
 return T[i];
}

void BiTreePrint(BTree T)
{
 int i;
 for(i=1;i<=BiTreeDepth(T);i++)
 {
  std::cout<<"第"<<i<<"层：";
  for(int j=1;j<=pow(2,i-1);j++)
  {
   position p;
   p.level=i;
   p.order=j;
   int value=GetValue(T,p);
   if(value!=0)
    std::cout<<value<<" ";
  }
  std::cout<<std::endl;
 }
}

void PostTraverse(BTree T,int e,void(*visit)(int e))
{
 if(T[2*e+1]!=0)
  PostTraverse(T,2*e+1,visit);
 if(T[2*e+2]!=0)
  PostTraverse(T,2*e+2,visit);
 visit(T[e]);
}

void PostOrderTraverse(BTree T,void(*visit)(int e))
{
 std::cout<<"后序遍历输出：";
 if(T[0]!=0)
  PostTraverse(T,0,visit);
 std::cout<<std::endl;
}

void InTraverse(BTree T,int e,void(*visit)(int e))
{
 if(T[2*e+1]!=0)
  InTraverse(T,2*e+1,visit);
 visit(T[e]);
 if(T[2*e+2]!=0)
  InTraverse(T,2*e+2,visit);
}

void InOrderTraverse(BTree T,void(*visit)(int e))
{
 std::cout<<"中遍历输出：";
 if(T[0]!=0)
  InTraverse(T,0,visit);
 std::cout<<std::endl;
}

void PreTraverse(BTree T,int e,void(*visit)(int e))
{
 visit(T[e]);
 if(T[2*e+1]!=0)
  PreTraverse(T,2*e+1,visit);
 
 if(T[2*e+2]!=0)
  PreTraverse(T,2*e+2,visit);
}

void PreOrderTraverse(BTree T,void(*visit)(int e))
{
 std::cout<<"先遍历输出：";
 if(T[0]!=0)
  PreTraverse(T,0,visit);
 std::cout<<std::endl;
}

main.cpp:主程序

#include <iostream>
#include <cmath>
#include "BiTree.h"
using namespace std;
void visit(int e)
{
 cout<<e<<" ";
}

int main()
{
 BTree T,S;
 CreateBiTree(T);
 
 /*
 cout<<"请依次输入要更改的层 序 值";
 position pos;
 int e;
 cin>>pos.level>>pos.order>>e;
 Assign(T,pos,e);
 

 cout<<"1的双亲节点节点：(0代表不存在)"<<Parent(T,1)<<endl;
 cout<<"2的左孩子节点:"<<LeftChild(T,2)<<endl;
 cout<<"2的右兄弟节点(0代表不存在)："<<RightSibling(T,2)<<endl;
 cout<<"把第3个节点搬家到5的下面"<<endl;
 
 Move(T,2,T,4);
 cout<<"层序输出："<<endl;
 BiTreePrint(T);
 cout<<"2的右孩子节点:"<<RightChild(T,2)<<endl;
 
 CreateBiTree(S);
 Insert(S,T,2,1);
 cout<<"层序输出："<<endl;
 BiTreePrint(T);
 */
 PostOrderTraverse(T,visit);
 InOrderTraverse(T,visit);
 PreOrderTraverse(T,visit);
 return 0;
}