二叉树的实现
二叉树都可以表示成如图所示的形式,npl代表堆,color为红黑色准备。
插入孩子节点
template<typename T> BinNodePosi(T) BinNode<T> :: insertAsLC (T const &e)
{ return lchild=new BinNode(e,this) ;} // 将e作为当前节点的左孩子插入二叉树
template<typename T> BinNodePosi(T) BinNode<T> :: insertAsLC (T const &e)
{ return rchild=new BinNode(e,this) ;} // 将e作为当前节点的右孩子插入二叉树
高度更新
template <typename T> int BinTree<T> :: updateHeight (BinNodePosi(T) x) // 更新节点x高度
{return x->height =1+max(stature (x->lc),stature (x->rc() ); } //具体规则,因树而异
template <typename T> void BinTree<T> ::updateHeightAbove (BinNodePosi(T) x)
{while(x) {updateHeight(x); x=x->parent; } }
子树接入
子树删除
子树分离
实现
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct node{
struct node *lchild;
struct node *rchild;
char date;
}bintree,*tree; //给 struct node*起了个别名,叫tree,故tree为指向节点的指针
void buildtree(tree &T) //&的意思是传进来节点指针的引用,括号内等价于 binNode(node)* &T,目的是让传递进来的指针发生改变
{
char c;
cin>>c;
if(c=='#'){
T=NULL;
return;
}
else{
T=new bintree; // 结构体指针变量赋值才可以用,将bintree分配的新的地址赋值到T
T->date=c;
buildtree(T->lchild);
buildtree(T->rchild);
}
}
//前序遍历二叉树并打印
void print(tree &T)
{
if(T){
cout<<T->date;
print(T->lchild);
print(T->rchild);
}
}
int main()
{
tree T;
buildtree(T);
print(T);
return 0;
}
相关链接 C++ ->(结构体指针变量)的介绍,typedef struct和struct的区别