二叉树相关操作代码实现（先序、中序、后序遍历，递归及非递归算法实现，深度，结点数，叶子结点数等代码实现）

二叉树相关操作的实现（先序、中序、后序遍历，递归及非递归算法实现，深度，结点数，叶子结点数等代码实现）

以下是源代码：

#include
#include
#include
#include
using namespace std;
#define MAX 20
typedef struct BTNode{       /*节点结构声明*/char data ;               /*节点数据*/struct BTNode *lchild;struct BTNode *rchild ;  /*指针*/
}*BiTree;void createBiTree(BiTree &t){ /* 先序遍历创建二叉树*/char s;BiTree q;//printf("\nplease input data:(exit for #)");s=getchar();if(s=='#'){t=NULL; return;}q=(BiTree)malloc(sizeof(struct BTNode));if(q==NULL){cout<<"Memory alloc failure!"; exit(0);}q->data=s;t=q;createBiTree(q->lchild); /*递归建立左子树*/createBiTree(q->rchild); /*递归建立右子树*/
}void PreOrder(BiTree p){  /* 先序遍历二叉树*/if (p) {cout<data;PreOrder( p->lchild ) ;PreOrder( p->rchild) ;}
}
void InOrder(BiTree p){  /* 中序遍历二叉树*/if(p) {InOrder( p->lchild ) ;cout<data;InOrder( p->rchild) ;}
}
void PostOrder(BiTree p){  /* 后序遍历二叉树*/if (p) {PostOrder( p->lchild ) ;PostOrder( p->rchild) ;cout<data;}
}void Preorder_n(BiTree p){ /*先序遍历的非递归算法*/BiTree stack[MAX],q;int top=0,i;for(i=0;idata;if(q->rchild) stack[top++]=q->rchild;if(q->lchild) q=q->lchild;elseif(top>0) q=stack[--top];else q=NULL;}
}void Inorder_n(BiTree t)   // 中序遍历的非递归
{if(!t)return ;BiTree curr = t;    // 指向当前要检查的节点stack s;while(curr != NULL || !s.empty()){while(curr != NULL){s.push(curr);curr = curr->lchild;}//whileif(!s.empty()){curr = s.top();s.pop();cout<data<<"  ";curr = curr->rchild;}}
}void Postorder_n(BiTree t)  // 后序遍历的非递归
{stack S;BiTree curr = t ;           // 指向当前要检查的节点BiTree previsited = NULL;    // 指向前一个被访问的节点while(curr != NULL || !S.empty())  // 栈空时结束{while(curr != NULL)            // 一直向左走直到为空{S.push(curr);curr = curr->lchild;}curr = S.top();// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点if(curr->rchild == NULL || curr->rchild == previsited){cout<data<<"  ";previsited = curr;S.pop();curr = NULL;}elsecurr = curr->rchild;      // 否则访问右孩子}
}void Copy(BiTree t,BiTree &Newt)
{if(t==NULL){Newt=NULL;return;}else{//Newt=new BiTree;Newt=(BiTree)malloc(sizeof(struct BTNode));Newt-> data=t-> data;Copy(t->lchild,Newt->lchild);Copy(t->rchild,Newt->rchild);}
}void LevelOrder(BiTree t)     //非递归层次遍历二叉树
{BiTree queue[MAX];//定义队列有十个空间if (t==NULL)return;int front,rear;front=rear=0;queue[rear++]=t;while(front!=rear)//如果队尾指针不等于对头指针时{cout<data<<"  ";  //输出遍历结果if(queue[front]->lchild!=NULL)  //将队首结点的左孩子指针入队列{queue[rear]=queue[front]->lchild;rear++;    //队尾指针后移一位}if(queue[front]->rchild!=NULL){queue[rear]=queue[front]->rchild;    //将队首结点的右孩子指针入队列rear++;   //队尾指针后移一位}front++;    //对头指针后移一位}
}void release(BiTree t){ /*释放二叉树空间*/if(t){release(t->lchild);release(t->rchild);free(t);}
}int Depth(BiTree t)     //计算二叉树的深度
{int m,n;if(t==NULL)   return 0;else{m=Depth(t->lchild);n=Depth(t->rchild);if(m>n) return(m+1);else return(n+1);}
}int NodeCount(BiTree t)     //统计二叉树中结点的个数
{if(t==NULL) return 0;else  return NodeCount(t->lchild)+NodeCount(t->rchild)+1;
}int NodeCount_leaf(BiTree t)     //统计二叉树中叶子结点的个数
{int l,r;if(t==NULL) return 0;else  if(t->lchild==NULL&&t->rchild==NULL)return 1;else{l=NodeCount_leaf(t->lchild);r=NodeCount_leaf(t->rchild);return (l+r);}
}int main(){BiTree t;BiTree Newt;printf("创建二叉树：\n");createBiTree(t);cout<<"***  ***  ***  ***  ***  ***\n";cout<<"请选择：\n";cout<<"1.先序遍历二叉树 \n";cout<<"2.中序遍历二叉树 \n";cout<<"3.后序遍历二叉树 \n";cout<<"4.先序遍历二叉树(非递归算法) \n";cout<<"5.中序遍历二叉树(非递归算法) \n";cout<<"6.后序遍历二叉树(非递归算法) \n";cout<<"7.层次遍历二叉树(非递归算法) \n";cout<<"8.复制二叉树 \n";cout<<"9.计算二叉树的深度 \n";cout<<"10.统计二叉树中结点的个数 \n";cout<<"11.统计二叉树中叶子结点的个数 \n";cout<<"***  ***  ***  ***  ***  ***\n";int a;cin>>a;cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！