#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=https://bbs.csdn.net/topics/ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); }}void PreOrderTraverse(BiTree T){//先序遍歷 if(T){ cout<
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; } } }}//非遞回的后序遍歷演算法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);}}//PostOrderUnrecvoid 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<<"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: 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
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/82342.html
標籤：新技術前沿
上一篇：掌握這21個Java的核心技術點，漲薪5K起步，告別上班復制粘貼！
下一篇：用excle往db里插入多條資料
