#include "stdio.h"typedef int Datatype#define MAXNODE 100
//二叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild;//左右孩子指针}BiTreeNode,*BiTree;
//三叉链表的存储typedef struct BiTNode { Datatype data; struct BiTNode *lchild,*rchild,*parent;}BiTreeNode,*BiTree;
//算法3.1：二叉树的先序遍历递归算法void PreOrder(BiTree bt){ if(bt!=NULL){ visit(bt->data);//访问根结点 PreOrder(bt->lchild); PreOrder(bt->rchild); }}
//算法3.2：二叉树的中序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); visit(bt->data); InOrder(bt->rchild); }}
//算法3.3：二叉树的后序遍历递归算法void InOrder(BiTree bt){ if(bt!=NULL){ InOrder(bt->lchild); InOrder(bt->rchild); visit(bt->data); }}
//算法3.4：二叉树的层次遍历算法void LevelOrder(BiTree bt){ BiTreeNode Queue[MAXNODE]; //定义队列 int front,rear; if(bt==NULL) return //空二叉树，遍历结束 front=-1; rear=0; Queue[rear]=bt; //根结点入队 while(rear!=front){ //队列不空，继续遍历；否则，遍历结束 front++; //出队 visit(Queue[front]->data); //访问刚出队的元素 if(Queue[front]->lchild!=NULL){ //如果有左孩子，左孩子入队 rear++; Queue[rear]=Queue[front]->lchild; } if(Queue[front]->rchild!=NULL){ //如果有右孩子，右孩子入队 rear++; Queue[rear]=Queue[front]->rchild; } }}
//算法3.5：中序遍历的非递归算法void NRInOrder(BiTree bt){ BiTree S[MAXNODE],p=bt;//定义栈 int top=-1; if(bt==NULL) return;//空二叉树，遍历结束 while(!(p==NULL&&top==0)){ while(p!=NULL){ if(toplchild;//指针指向p的左孩子结点 } if(top==-1) return //栈空，结束 else{ p=S[--top];//弹出栈顶元素 visit(p->data);//访问结点的数据域 p=p->rchild;//指向p的右孩子结点 } }}
//算法3.6：根据先序与中序遍历结果建立二叉树void PreInOrd(char preord[],char inord[],int i,int j,int k,int h,BiTree *t)//先序序列从i到j,中序序列从k到h，建立一个二叉树放到t中{ int m; (*t)=new BTNode; (*t)->data=preord;//二叉树的根 m=k; while (i[m]!=preord)m++;//在中序序列中定位树根 /********递归调用建立左子树******/ if(m==k)(*t)->left=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*t)->left); /********递归调用建立左子树******/ if(m==k)(*t)->right=NULL; else PreInOrd(preord,inord,i+1,i+m-k,k,m-1,&(*))->right);}BTree * createBT(char preord[],char inord[],int n,BTree root)//n为二叉树接点的个数，建立的二叉树放在root中{ if(nleft==NULL & bt->right==NULL) return 1; return (BitreeLeaf(bt->left)+BirLeaf(bt->right));}
//算法3.8：求二叉树深度算法int BitreeDepth (BiTree bt){ if(bt==NULL) return 0; if(bt->lchild==NULL & bt->rchild==NULL) return1; depthL=BitreeDepth(bt->lchild); depthR=BitreeDepth(bt->rchild); return 1+max(depthL,depthR);}
//算法3.12：二叉树的查找算法BiTree SearchBST(BiTree bt,KeyType key){ if(bt==NULL || key==bt->data.key) return bt; if(keydata.key) return SearchBST(bt->lchild,key); else return SearchBST(bt->rchild,key);}
//算法3.13：在二叉树中插入结点int InseartBST(BiTreeNode **bt,Datatype e){ BiTreeNode *qq=new BiTreeNode(),*pp=new BiTreeNode(); BiTreeNode **qq=&qq,*s,**p=&pp; *q=OxO; *p=OxO; if(SearchBST(*bt,e.key,p,q)==0)//待查结点是否在二叉排序树中 { s=new BiTreeNode(); s->data=e;s->lchild=s->rchild=OxO;//待查结点 if(!(*q)) *bt=s;//二叉树的根 else if(e.keydata.key) (*q)->lchild=s;//作为左儿子插入 else(*q)->rchild=s;//作为右儿子插入 return 1; } else return 0;}
//算法3.14：在二叉排序树中删除结点int DeleteNode(BitreeNode **t,int key){ BiTreeNode *pp=new BiTreeNode(),*ff=new BiTreeNode; BiTreeNode **p=&pp,*s,*q,**f=&ff; *p=OxO;*f=OxO; int flag=0; if(SearchBST(*t,key,f,p)!=0){ flag=1;//查找成功，置删除标记，待删除结点为p if(!((*p)->rchild)){//结点无右儿子，结点只有一个分支或为叶子结点 if((*f)->lchild==*p) (*f)->lchild=(*P)->lchild; else (*f)->rchild=(*p)->lchild; } else{//结点有右儿子 if(!((*p)->lchild)){//结点无左儿子，一个分支 if((*f)->lchild==*p) (*f)->lchild=(*P)->rchild; else (*f)->rchild=(*p)->rchild; } else {//结点有左二子，两个分支 q=*p; s=(*p)->lchild; while(s->rchild){q=s;s=s->rchild;}//在结点p的左分支上沿右指针域往下找，直到右指针域为空时为止 (*p)->data=s->data; if(q!=*p){(q)->rchild=s->lchild;} else(q)->lcild=s->lchild; } } } return flag;} |
转播
