平衡二叉排序树的建立，删除，增加的Ｃ语言程序源码

广大楼主请多多着力啊！

有没》

[个人日记]
设置置顶  转载到我空间  复制本文网址 隐藏签名档 大字体选用该信纸 上一篇|下一篇|编辑|删除|返回
C++
发表时间：2007年11月28日 22时47分53秒        本文链接：[url]http://user.qzone.[/url]评论/阅读(0/4)

C++
//功能：中序遍历非递归算法
//时间：2006.11.3
//作者：lwh
//二叉树四种遍历方法：前序、中序、后序、层次
#include<fstream>
using namespace std;
typedef char TElemType;
ifstream in("input.txt");
ofstream out("output.txt");
//二叉树的二叉链表存储表示
typedef struct BiTNode
{
   TElemType data;
   BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
//功能：由先序次序序列创建二叉树
//参数：引用指针
//说明：可应付空树 参见bitree.cpp中的同名函数
//结论：建立链式二叉树最好的方法
void CreateBiTree(BiTree &t)//按先序次序输入二叉树中结点的值，"#"表示空子树,"@"表示输入结束标志！
{     //t为指针引用传递
  char ch;
  ch=in.get(); //读取先序次序二叉树中的结点值
  if(ch=='@')return;//结尾
  if(ch=='#') t=NULL;//空子树
  else{
   t=new BiTNode;
   t->data=ch;t->lchild=NULL;t->rchild=NULL;
   CreateBiTree(t->lchild);
   CreateBiTree(t->rchild);
  }
}//CreateBiTree
void PreOrderTraverse(BiTree t)
{
   if(t) {
   out<<t->data;
   PreOrderTraverse(t->lchild);
   PreOrderTraverse(t->rchild);
  }
}
void InOrderTraverse(BiTree t)
{
   if(t) {
   InOrderTraverse(t->lchild);
   out<<t->data;
   InOrderTraverse(t->rchild);
  }
}
void PostOrderTraverse(BiTree t)
{
   if(t) {
   PostOrderTraverse(t->lchild);
   PostOrderTraverse(t->rchild);
   out<<t->data;
  }
}

void LevelTraverse(BiTree t)
{
  BiTNode Qu[100];
  int front=-1,rear=-1;
  if(t) Qu[++rear]=*t;
  while(front!=rear)
  {
   out<<Qu[++front].data;
   if(Qu[front].lchild)
    Qu[++rear]=*Qu[front].lchild;
   if(Qu[front].rchild)
    Qu[++rear]=*Qu[front].rchild;
  }
}
void InorderStackTraverse(BiTree t)//中序非递归算法
{
  BiTree p,stack[100];//假设的最大栈空间数
  int top=-1;
  p=t;
  while((p!=NULL)||top!=-1)
  {
   while(p!=NULL)
   { top++;stack[top]=p;p=p->lchild;}
   if(top!=-1)
   { p=stack[top];top--;out<<p->data<<' ';p=p->rchild;}
  }
}
void main()
{
  BiTree tt=NULL;
  CreateBiTree(tt);
  PreOrderTraverse(tt);
  out<<endl;
  InOrderTraverse(tt);
  out<<endl;
  PostOrderTraverse(tt);
  out<<endl;
  LevelTraverse(tt);
  out<<endl;
  InorderStackTraverse(tt);
  out<<endl;
  in.close();
  out.close();
}

如何平衡？AVL？RBT？SBT？Treap？