基本操作

通常有：建立空二叉树、生成以X为根节点的数据域信息、将数据域信息为x的结点插入到二叉树bt中、删除某一个结点的左子树/右子树、查找某元素、遍历

给某结点插入一个左孩子

btnode
   
    *btTree::Insert(btTree bt,DataType x,BtTree parent){
   //在二叉树bt中的parent所指结点和其左子树中 插入数据元素为x的结点btTree p;if(parent==NULL){
   return NULL;//如果不存在parent结点，不能进行插入，返回空指针}p=new btnode;//申请结点空间if(p==NULL) return NULL;//如果没有存储空间，返回空指针p->data=x;p->lchild=NULL;P->rchild=NULL;//建立待插入结点if(parent->lchild==NULL)parent->lchild=p;//如果parent没有左孩子，直接插入else{
   p->lchild=parent->lchild;parent->lchild=p;//parent的左孩子作为p的左孩子插入}return bt;//返回根节点地址}

几个注意点：

1.要先判错，且多种情况都要考虑，parent为空的情况、p没有申请到空间的情况

2.对于parent有无子树也要分开写

3.建立待插入结点时p->data=x;

p->lchild=NULL;

P->rchild=NULL;注意左右指针域也要初始化

删除二叉树中某结点的左子树

btnode
   
    *btTree::DeleteL(btTree L,btTree parent){
   btTree p;if(parent==NULL||parent->lchild==NULL){
   return NULL;//如果不存在parent结点，不能进行插入，返回空指针}p=parent->lchild;parent->lchild=NULL;delete(p);//当p非叶子节点时，这样只释放了树根结点的空间，若要删除子树分支中的结点，还需要用到遍历return bt;}

注意：这里当parent为空或者没有左孩子都要返回空指针，不进行删除操作

根据先序与中序遍历建立二叉树

下面给出该算法描述。假设二叉树的先序序列和中序序列分别存放在一维数组preod[]与inod[]中，并假设二叉树各结点的数据值均不相同。

写法一：

void preInorder(char preod[],char inod[],int i,int j,int k,int h,btTree*t){
   int m;(*t)=new btNode;(*t)->data=preod[i];//根结点m=k;//中序遍历中的第一个索引while(inod[m]!=preod[i])m++;if(m==k)t->lchild=NULL;//此时左子树序列为空elsepreInorder(preod,inod,i+1,i+m-k,k,m-1,&((*t)->lchild)));if(m==h)//右子树序列为空preInorder(preod,inod,i+m-k+1,j,m+1,h,&((*t)->rchild));}

写法二：

//把in_order[L1..R1]和post_order[L2..R2]建成一棵二叉树，返回树根int build(int L1, int R1, int L2, int R2) {
       if (L1 > R1) return 0; //先判断特殊情况：是否为空树    int root = post_order[R2];    int p = L1;    while (in_order[p] != root) p++;    int cnt = p - L1; //左子树的结点个数    lch[root] = build(L1, p - 1, L2, L2 + cnt - 1);    rch[root] = build(p + 1, R1, L2 + cnt, R2 - 1);        return root;}

写法三：

void rebuild(char * preOrder,char* inOrder,int nTreeLen,Node** root){
   if(preOrder == NULL || inOrder == NULL){
   return;//先检查边界条件}Node*temp = new Node;//先获得前序遍历的第一个结点temp->data = *preOrder;temp->left = NULL;temp->right = NULL;if(*root == NULL) *root = temp;//如果此结点为空，则把当前结点复制到根节点if(nTreeLen == 1) return;//如果当前树长度为1，则已经是最后一个结点char *pOrgInorder = inOrder;char* pLeftEnd =inOrder;//寻找子树长度int templen = 0;//用于记录临时长度，避免溢出while( *preOrder != * pLeftEnd ){
   if(preOrder ==NULL||pLeftEnd ==NULL)return;templen ++;if(templen > nTreeLen)break;pLeftEnd++;}int LeftLen = (int)(pLeftEnd - pOrgInorder);int RightLen =  nTreeLen - LeftLen-1;//右子树长度if(LeftLen>0) rebuild(preOrder+1,inOrder,LeftLen;&((*root)->left));//递归重建左子树if(RightLen>0)rebuild(preOrder+1+LeftLen,Inorder+LeftLen+1,RightLen,&((*root)->right));}

应用举例

查找数据元素

Search(bt,x) 在bt为根结点指针的二叉树中查找数据元素x,查找成功时返回该结点的指针，失败时返回空指针

biTree Search(btNode*bt,DataType x){
     btNode*p;  if(bt)  {
       if(bt->dara==x) return bt;   if(bt->lchild){
         p=Search(bt->lchild,x);      if(p) return p;    }    if(bt->rchild){
         p=Search(bt->rchild,x);      if(p) return p;    }  }  return NULL;}

注意要验是否空指针：if(bt), if§return p;

二叉链表存储结构统计叶结点的数目

int CountLeaf(btNode*bt)  {
     if(!bt) return 0;  if(bt->lchild==NULL&&bt->rchild==NULL)   {
    return 1;}    return CountLeaf(bt->lchild)+CountLeaf(bt->rchild);    }

转载地址：http://dxten.baihongyu.com/

你可能感兴趣的文章