开发者社区> 问答> 正文

树的非递归算法

知与谁同 2018-07-16 16:23:12 381
急求树的非递归算法不是二叉树:比如树的度为3或更大请用c写谢谢感激不尽
算法
分享到
取消 提交回答
全部回答(2)
  • 聚小编
    2019-07-17 22:55:39
    参考一下
    非递归递归都有

    #include "iostream.h"
    #include "stdlib.h"
    #include "stdio.h"

    typedef char ElemType;//定义二叉树结点值的类型为字符型
    const int MaxLength=10;//结点个数不超过10个

    typedef struct BTNode{
    ElemType data;
    struct BTNode *lchild,*rchild;
    }BTNode,* BiTree;

    void CreateBiTree(BiTree &T){//按先序次序输入,构造二叉链表表示的二叉树T,空格表示空树
    // if(T) return;
    char ch;
    ch=getchar(); //不能用cin来输入,在cin中不能识别空格。
    if(ch==' ') T=NULL;
    else{
    if(!(T=(BTNode *)malloc(sizeof(BTNode)))) cout<<"malloc fail!";
    T->data=ch;
    CreateBiTree(T->lchild);
    CreateBiTree(T->rchild);
    }
    }

    void PreOrderTraverse(BiTree T){//先序遍历
    if(T){
    cout<<T->data<<' ';
    PreOrderTraverse(T->lchild);
    PreOrderTraverse(T->rchild);
    }
    }
    void InOrderTraverse(BiTree T){//中序遍历
    if(T){
    InOrderTraverse(T->lchild);
    cout<<T->data<<' ';
    InOrderTraverse(T->rchild);
    }
    }
    void PostOrderTraverse(BiTree T){//后序遍历
    if(T){
    PostOrderTraverse(T->lchild);
    PostOrderTraverse(T->rchild);
    cout<<T->data<<' ';
    }
    }
    void LevelOrderTraverse(BiTree T){//层序遍历

    BiTree Q[MaxLength];
    int front=0,rear=0;
    BiTree p;
    if(T){ //根结点入队
    Q[rear]=T;
    rear=(rear+1)%MaxLength;
    }
    while(front!=rear){
    p=Q[front]; //队头元素出队
    front=(front+1)%MaxLength;
    cout<<p->data<<' ';
    if(p->lchild){ //左孩子不为空,入队
    Q[rear]=p->lchild;
    rear=(rear+1)%MaxLength;
    }
    if(p->rchild){ //右孩子不为空,入队
    Q[rear]=p->rchild;
    rear=(rear+1)%MaxLength;
    }
    }

    }
    //非递归的先序遍历算法
    void NRPreOrder(BiTree bt)
    { BiTree stack[MaxLength],p;
    int top;
    if (bt!=NULL){
    top=0;p=bt;
    while(p!=NULL||top>0)
    { while(p!=NULL)
    {
    cout<<p->data;
    stack[top]=p;
    top++;
    p=p->lchild;
    }
    if (top>0)
    { top--; p=stack[top]; p=p->rchild; }
    }
    }
    }
    //非递归的中序遍历算法
    void NRInOrder(BiTree bt)
    { BiTree stack[MaxLength],p;
    int top;
    if (bt!=NULL){
    top=0;p=bt;
    while(p!=NULL||top>0)
    { while(p!=NULL)
    {

    stack[top]=p;
    top++;
    p=p->lchild;
    }
    if (top>0)
    { top--; p=stack[top];cout<<p->data; p=p->rchild; }
    }
    }
    }
    //非递归的后序遍历算法
    /*bt是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。
    需要判断根结点的左右子树是否均遍历过。
    可采用标记法,结点入栈时,配一个标志tag一同入栈
    (1:遍历左子树前的现场保护,2:遍历右子树前的现场保护)。
    首先将bt和tag(为1)入栈,遍历左子树;
    返回后,修改栈顶tag为2,遍历右子树;最后访问根结点。*/

    typedef struct
    {
    BiTree ptr;
    int tag;
    }stacknode;

    void NRPostOrder(BiTree bt)
    {
    stacknode s[MaxLength],x;
    BiTree p=bt;
    int top;
    if(bt!=NULL){
    top=0;p=bt;
    do
    {
    while (p!=NULL) //遍历左子树
    {
    s[top].ptr = p;
    s[top].tag = 1; //标记为左子树
    top++;
    p=p->lchild;
    }

    while (top>0 && s[top-1].tag==2)
    {
    x = s[--top];
    p = x.ptr;
    cout<<p->data; //tag为R,表示右子树访问完毕,故访问根结点
    }

    if (top>0)
    {
    s[top-1].tag =2; //遍历右子树
    p=s[top-1].ptr->rchild;
    }
    }while (top>0);}
    }//PostOrderUnrec

    int BTDepth(BiTree T){//求二叉树的深度
    if(!T) return 0;
    else{
    int h1=BTDepth(T->lchild);
    int h2=BTDepth(T->rchild);
    if(h1>h2) return h1+1;
    else return h2+1;
    }
    }

    int Leaf(BiTree T){//求二叉树的叶子数
    if(!T) return 0;
    else if(!T->lchild&&!T->rchild) return 1;
    else return(Leaf(T->lchild)+Leaf(T->rchild));
    }

    int NodeCount(BiTree T){//求二叉树的结点总数
    if(!T) return 0;
    else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    }

    void main(){
    BiTree T;
    T=NULL;
    int select;
    //cout<<"请按先序次序输入各结点的值,以空格表示空树(输入时可连续输入):"<<endl;
    // CreateBiTree(T);
    while(1){
    cout<<"\n\n请选择要执行的操作:\n";
    cout<<"1.创建二叉树\n";
    cout<<"2.二叉树的递归遍历算法(前、中、后)\n";
    cout<<"3.二叉树的层次遍历算法\n";
    cout<<"4.求二叉树的深度\n";
    cout<<"5.求二叉树的叶子结点\n";
    cout<<"6.求二叉树的结点总数\n";
    cout<<"7.二叉树的非递归遍历算法(前、中、后)\n"; //此项可选做
    cout<<"0.退出\n";
    cin>>select;
    switch(select){
    case 0:return;
    case 1:
    cout<<"请按先序次序输入各结点的值,以空格表示空树(输入时可连续输入):"<<endl;
    CreateBiTree(T);
    break;
    case 2:
    if(!T) cout<<"未建立树,请先建树。";
    else{
    cout<<"\n先序遍历:\n";
    PreOrderTraverse(T);
    cout<<"\n中序遍历:\n";
    InOrderTraverse(T);
    cout<<"\n后序遍历:\n";
    PostOrderTraverse(T);
    }
    break;
    case 3:
    cout<<"\n层序遍历:\n";
    LevelOrderTraverse(T);
    break;
    case 4:
    cout<<"二叉树的深度为:\n";
    cout<<BTDepth(T);
    break;
    case 5:
    cout<<"\n叶子节点数:\n";
    cout<<Leaf(T);
    break;
    case 6:
    cout<<"总节点数:\n";
    cout<<NodeCount(T);
    break;
    case 7:
    if(!T) cout<<"未建立树,请先建树。";
    else{
    cout<<"\n先序遍历:\n";
    NRPreOrder(T);
    cout<<"\n中序遍历:\n";
    NRInOrder(T);
    cout<<"\n后序遍历:\n";
    NRPostOrder(T);
    }
    break;
    default:
    cout<<"请确认选择项:\n";
    }//end switch
    }//end while

    }

    先输入1
    然后输入回车
    再输入123
    再输入一个空格
    再输入4
    再输入三个空格
    再输入56
    再输入三个空格
    再输入输入回车
    一定要照这循序输这输不要乱敲回车和其他键
    0 0
  • 管理贝贝
    2019-07-17 22:55:39
    呵呵,人家不是要二叉树的。
    虽然树也能转换成二叉树,但既然人家要求了,还是没必要这样乱来吧
    0 0
添加回答
+ 订阅

了解行业+人工智能最先进的技术和实践,参与行业+人工智能实践项目

推荐文章
相似问题