二叉树的遍历源代码.docx
二叉树的遍历源代码二叉树就是每个结点最多有两个子树的树形存储结构，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被且只被访问一次。 程序的流程图如下： 程序代码如下： #include<iostream.h> #include<stdlib.h> #include<stdio.h> #include<stdlib.h> typedef char ElemType; struct BTreeNode ElemType data; BTreeNode*left; BTreeNode*right; ; void InitBTree(BTreeNode*& BT) /初始化二叉树 BT=NULL; void CreateBTree(BTreeNode*& BT,char*a) /根据广义表表示的二叉树建立对应的存储结构 const int MaxSize=10; BTreeNode*sMaxSize; int top=-1; BT=NULL; BTreeNode*p; int k; int i=0; while(ai) switch(ai) case ' ': break; case '(': if(top=MaxSize-1) printf("栈的空间太小，请增加MaxSize的值n"); exit(1); top+; stop=p; k=1; break; case ')': if(top=-1) printf("二叉树广义表字符串错！n"); exit(1); top-; break; case ',': k=2; break; default: p=new BTreeNode; p->data=ai; p->left=p->right=NULL; if(BT=NULL) BT=p; else if(k=1) stop->left=p; else stop->right=p; i+; bool EmptyBTree(BTreeNode*BT) /判断一棵二叉树是否为空，若是则返回ture，否则返回false return BT=NULL; int DepthBTree(BTreeNode*BT) if(BT=NULL) return 0; else int dep1=DepthBTree(BT->left); int dep2=DepthBTree(BT->right); if(dep1>dep2) return dep1+1; else return dep2+1; bool FindBTree(BTreeNode*BT,ElemType&x) /从二叉树中查找值为x的结点，若存在该结点则由x带回它的完整值 if(BT=NULL) return false; else if(BT->data=x) x=BT->data; return true; else if(FindBTree(BT->left,x) return true; if(FindBTree(BT->right,x) return true; return false; void PrintBTree(BTreeNode*BT) /按照树的一种表示方法输出一棵二叉树 if(BT!=NULL) cout<<BT->data; if(BT->left!=NULL|BT->right!=NULL) cout<<'(' PrintBTree(BT->left); if(BT->right!=NULL) cout<<',' PrintBTree(BT->right); cout<<')' void ClearBTree(BTreeNode*&BT) /清除二叉树中的所有结点，使之变为一棵空 if(BT!=NULL) ClearBTree(BT->left); ClearBTree(BT->right); delete BT; BT=NULL; void PreOrder(BTreeNode*BT) if(BT!=NULL) cout<<BT->data<<' ' PreOrder(BT->left); PreOrder(BT->right); void InOrder(BTreeNode*BT) if(BT!=NULL) InOrder(BT->left); cout<<BT->data<<' ' InOrder(BT->right); void PostOrder(BTreeNode*BT) if(BT!=NULL) PostOrder(BT->left); PostOrder(BT->right); cout<<BT->data<<' ' void LevelOrder(BTreeNode*BT) / const int MaxSize=30; / BTreeNode*qMaxSize; / int front=0, rear=0; / BTreeNode*p; if(BT!=NULL) / rear=(rear+1)%MaxSize; qrear=BT; 按层遍历由BT指针所指向的二叉树 定义用于存储队列的数组长度 定义队列所使用的数组空间 定义队首指针和队尾指针，初始为空队 将树根指针进队 树 while(front!=rear) /当队列非空时执行循环 front=(front+1)%MaxSize; /使队首指针指向队首元素 p=qfront; /删除队首元素 cout<<p->data<<' ' /输出队首元素所指结点的值 if(p->left!=NULL) rear=(rear+1)%MaxSize; qrear=p->left; if(p->right!=NULL) rear=(rear+1)%MaxSize; qrear=p->right; /while end/ void main system("color 75"); /设置颜色以美观 BTreeNode*bt; InitBTree(bt); char b999; printf("输入二叉树广义表字符串:n"); cin.getline(b,sizeof(b); CreateBTree(bt,b); PrintBTree(bt); cout<<endl; printf("递归算法遍历：n"); cout<<"前序遍历为：" PreOrder(bt); cout<<endl; cout<<"中序遍历为：" InOrder(bt); cout<<endl; cout<<"后序遍历为：" PostOrder(bt); cout<<endl; printf("非递归算法遍历：n"); cout<<"按层遍历为：" LevelOrder(bt); cout<<endl; ElemType x; printf("请输入待查字符:"); scanf("%c",&x); if(FindBTree(bt,x) printf("查找字符%c成功",x); else printf("查找字符%c失败",x); printf("n"); cout<<" 树的深度为:" cout<<DepthBTree(bt)<<endl; ClearBTree(bt); 程序的运行结果如右图：
