树的 *** 作（构造，遍历，求高度，查找）非递归

概述树的 *** 作（构造，遍历，求高度，查找）非递归

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

    // BTree1.cpp : 定义控制台应用程序的入口点      //1.使用广义表构造二叉树      //2.程序默认数据为：a(b(c,d),e(,f))      //3.三种遍历使用非递归，求树的高度、查找节点使用递归                  #include "stdafx.h"      #include<iostream>      #include<stack>      using namespace std;                  #define ElemType char      #define Status int      #define OK 0      #define ERROR 1      #define MAX_LEN 100      typedef struct BTnode      {          ElemType date;          BTnode *lchild,*rchild;      }BTnode,*BTree;      typedef enum{L,R} tagtype;      typedef struct       {          BTree ptr;          tagtype tag;      }stacknode;                  Status creat(BTree &T,char *str);//根据str创建二叉树T      Status visit(BTree e);//访问节点，打印date      Status preorder(BTree T);//先序遍历，非递归      Status inorder(BTree T);//中序遍历，非递归      Status postorder(BTree T);//后序遍历，非递归      Status getTreeHeight(BTree T,int &H);//求树的高度，递归      Status findNode(BTree T,ElemType e,BTnode &bt);//求树中结点data值为e的节点，并返回此节点的引用                  int _tmain(int argc,_TCHAR* argv[])      {          int i,height,flag;          BTree T;          BTnode bt;          char *buffer,e;          printf("想输入自己的数据请输入--1or采用默认数据请输入--2：");          cin>>flag;          if(flag==1)          {              buffer=(char*)malloc(MAX_LEN*sizeof(char));              scanf("%s",buffer);          }          else if(flag==2)              buffer="a(b(c,f))";          T=NulL;          creat(T,buffer);//创建树          //先序遍历          printf("先序遍历:");          preorder(T);          //中序遍历          printf("\n中序遍历:");          inorder(T);          //后序遍历          printf("\n后序遍历:");          postorder(T);          //求树的高度          height=0;          getTreeHeight(T,height);          printf("\n此树的高度为：%d\n",height);          //查找date值为e的节点并返回节点的引用          printf("请输入要查找的字符值：");              cin>>e;          findNode(T,e,bt);          if(bt.date==NulL)              printf("未找到");          else              printf("找到他了：%c",bt.date);          printf("\n");          system("pause");          return 0;      }                  Status creat(BTree &T,char *str)//初始T=NulL      {          char *ch;          int flag=0;          BTree p;          stack<BTnode *> Stack; //实例化栈          p=NulL;          ch=str;          while((*ch)!='')          {              switch(*ch)              {              case'(':                  Stack.push(p);                  flag=1;                  break;              case',':                  flag=2;                  break;              case')':                  Stack.pop();                  break;              default://对字符的处理                  p=(BTree)malloc(sizeof(BTnode));                  p->date=*ch;                  p->lchild=p->rchild=NulL;                  if(T==NulL)                      T=p;                  else                  {                      if(flag==1)                          Stack.top()->lchild=p;                      if(flag==2)                          Stack.top()->rchild=p;                  }              }              ch++;          }          return OK;      }      Status visit(BTree e)      {          printf("%c",e->date);          return OK;      }      Status preorder(BTree T)      {          BTree p;          stack<BTnode *> Stack;           p=T;          Stack.push(NulL);          while(p!=NulL)          {              visit(p);//访问节点              if(p->rchild!=NulL)//如果有右孩子，此右孩子节点进栈，                  Stack.push(p->rchild);              if(p->lchild!=NulL)//向左移动                  p=p->lchild;              else//左孩子已访问过，p=根—>rchild              {                  p=Stack.top();                  Stack.pop();              }          }          return OK;      }      Status inorder(BTree T)      {          BTree p;          p=NulL;          stack<BTree> Stack;//实例化栈          Stack.push(T);//根节点进栈          while(!Stack.empty())          {              while(Stack.top()!=NulL)//一路向左，至最左                  Stack.push(Stack.top()->lchild);              Stack.pop();//空指针d出              if(!Stack.empty())              {                  p=Stack.top();                  Stack.pop();                  visit(p);                  Stack.push(p->rchild);//向右移动              }          }          return OK;      }      Status postorder(BTree T)      {          stack<stacknode> Stack;          stacknode S;          BTree p;          p=T;          do          {              while(p!=NulL)//一路向左，进栈，至最左              {                  S.ptr=p;                  S.tag=L;                  Stack.push(S);                  p=p->lchild;              }              while(!Stack.empty()&&Stack.top().tag==R)                {                  S=Stack.top();                  Stack.pop();                  p=S.ptr;                  visit(p);   //tag为R，表示右子树访问完毕，故访问根结点                     }              if(!Stack.empty())//向右移一个              {                  Stack.top().tag=R;                  p=Stack.top().ptr->rchild;              }                      }while(!Stack.empty());          return OK;      }      Status getTreeHeight(BTree T,int &H)      {          //递归，分别计算左、右子树的高度，后比较较大者，+1          int lchildH,rchildH;          lchildH=rchildH=0;//左右子树高度，初始化          if(T==NulL)              H=0;          else          {              getTreeHeight(T->lchild,lchildH);//计算左子树的高度              getTreeHeight(T->rchild,rchildH);//计算右子树的高度              if(lchildH>rchildH)                  H=lchildH+1;              else                   H=rchildH+1;          }          return OK;      }      Status findNode(BTree T,BTnode &bt)      {          if(T==NulL)//当前BTree为空          {              bt.date=NulL;              return ERROR;          }          else if(T->date==e)//找到，当前节点符合              bt=*T;          else          {              findNode(T->lchild,bt);//在左子树中寻找              if(bt.date==NulL)                  findNode(T->rchild,bt);//在右子树中寻找          }          return OK;      }  

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的树的 *** 作（构造，遍历，求高度，查找）非递归全部内容，希望文章能够帮你解决树的 *** 作（构造，遍历，求高度，查找）非递归所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。