哈工大数据结构实验二——二叉树的建立、遍历及其应用

目录

0.实验要求1.二叉树的存储2.递归创建二叉树3.非递归创建二叉树通过读取文件非递归创建二叉树 4.二叉树的遍历4.1先序递归遍历二叉树4.2非递归先序遍历二叉树4.3非递归中序遍历二叉树4.4递归中序遍历二叉树4.5非递归后序遍历二叉树4.6层序遍历二叉树4.7判断二叉树是否为完全二叉树4.8 显示二叉树4.9非递归求二叉树的宽度 5.实验代码如下

其他类似的博客

哈工大数据结构实验二——哈夫曼编码与译码方法 哈工大2019秋数据结构期末试题 哈工大数据结构实验一算术表达式求值 哈工大数据结构实验一 线性结构及其应用

0.实验要求

1.二叉树的存储

二叉树的存储相信不用多讲啥，直接使用最常见的动态二叉链结构存储即可。

typedef struct BTnode *Tnode; //使用链式结构表示二叉树， struct BTnode{//声明一个树的节点， //它包含这个节点的数据以及指向左儿子和右儿子的指针 char data;//节点存储的字符 Tnode lchild,rchild; //指向左右儿子的指针 } ;

2.递归创建二叉树

递归创建二叉树，我直接先序递归创建二叉树。和先序遍历思想几乎一样。先创建根节点，然后先序递归的创建左子树，然后先序递归的创建右子树。

我用’#'表示一个空节点

void PreCreatTree(Tnode *T){ //先序创建一个二叉树 char x; cin>>x; if(x=='#'){//'#'表示空节点 *T=NULL; } else{ *T=new BTnode;//给节点分配存储空间 if(!*T){ cout<<"error"<<endl; } else{ //先序递归创建二叉树 (*T)->data =x;//创建根节点 PreCreatTree(&(*T)->lchild );//先序递归的创建左子树 PreCreatTree(&(*T)->rchild );//先序递归的创建右子树 } } }

3.非递归创建二叉树

怎么非递归的创建二叉树呢？我们可以用数组来存储一个二叉树，从数组下标1的位置存储根节点。数组的下标就隐含描述了节点的父子关系。

我们考虑两个节点，他们存储在数组中的下标分别为i , j ,不失一般性，设i < j如果 j = 2 * i ,那么j 是 i 的左儿子如果 j = 2 * i + 1 ,那么 j 是i 的右儿子

那么我们的思路就明了了，每次只要给出这个节点存储的下标，那么根据上述的关系式，我们可以知道这个节点的父节点下标，也能知道这个节点是父节点的左儿子还是右儿子，然后让根节点指向这个儿子节点即可。

Tnode s1[100]; //用来创建递归树所用的数组 Tnode CreatTree(){ //非递归创建二叉树 int i,j; char c; Tnode bt,p;//用于存放节点 cin>>i>>c;//给定存储某个字符的数组下标和该字符来创建二叉树 while(i!=0&&c!='#') { p=new BTnode; p->data =c; p->lchild =NULL; p->rchild =NULL; s1[i]=p; if(i==1) bt=p;//根节点 else if(i==2) bt->lchild =p; else{ j=i/2;//父节点 if(i%2==0) {//这个节点是父节点的左儿子 s1[j]->lchild=p; } if(i%2!=0)//这个节点是父节点的右儿子 s1[j]->rchild=p; } cin>>i>>c; } return bt; }

通过读取文件非递归创建二叉树

Tnode DuRuTree(){ //非递归创建二叉树 fstream in; in.open("erchashu.txt"); int i,j; char c; Tnode bt,p;//用于存放节点 in>>i>>c; while(i!=0&&c!='#') { p=new BTnode; p->data =c; p->lchild =NULL; p->rchild =NULL; s1[i]=p; if(i==1) bt=p; else if(i==2) bt->lchild =p; else{ j=i/2; if(i%2==0){ s1[j]->lchild=p; } if(i%2!=0) s1[j]->rchild=p; } in>>i>>c; } in.close() ; return bt; }

4.二叉树的遍历

4.1先序递归遍历二叉树

太简单了，不阐述了

void PreOrder(Tnode T){ //先序递归遍历二叉树 if(T==NULL){ return ; } cout<<T->data<<" "; PreOrder(T->lchild ); PreOrder(T->rchild ); }

4.2非递归先序遍历二叉树

非递归先序遍历我们需要借助栈来完成，我们对先序的理解就是一直往左儿子走，沿途输出遇到的所有左儿子，直到走到最左的儿子，然后我们再去先序遍历这个左儿子的兄弟

那么问题来了，你走到了最左儿子，怎么找到左儿子的兄弟呢？由于节点不存储指向兄弟的指针，因此，你必须通过父节点去找右儿子。

现在的问题就是你怎么去找父节点呢？由于节点不存储指向父亲的指针，因此你必须把父节点保留起来。没错，就是用栈。

栈有个特性：后进先出，先进后出，也就是说栈中相邻的两个节点就是父子关系。所以当我们碰到最左节点后，栈顶的那个节点就是我们这个最左节点的父亲，只要把这个节点弹出来，然后我们就可以去继续遍历父节点的右儿子啦。(这个时候不需要输出父节点，因为父节点在进栈的时候已经输出了)

void fPreOrder(Tnode root){ //非递归先序遍历二叉树 if(root==NULL){ return; } Tnode p=root; stack<Tnode>s; while(!s.empty()||p){ while(p){ //一直往左走 ， 先序遍历 cout<<p->data<<' ' ; s.push(p); p=p->lchild ; } //已经走到最左儿子 if(!s.empty() ){ p=s.top() ;//弹出父节点 s.pop() ; p=p->rchild ; //然后去父节点的右儿子先序遍历 } } }

4.3非递归中序遍历二叉树

非递归中序遍历和非递归先序遍历原理一样，只是输出节点的时间不同，先序遍历是把节点压栈的时候就输出节点，非递归中序遍历是把节点从栈中弹出的时候输出节点。

void fInOrder(Tnode root){ //非递归中序遍历二叉树 if(root==NULL) return ; Tnode p=root; stack<Tnode>s; while(!s.empty()||p){ while(p){ s.push(p); p=p->lchild ; } if(!s.empty()){ p=s.top(); s.pop(); cout<<p->data<<' ' ; p=p->rchild ; } } }

4.4递归中序遍历二叉树

void InOrder(Tnode T){ if(T==NULL){ return ; } InOrder(T->lchild ); cout<<T->data<<" "; InOrder(T->rchild ); }

4.5非递归后序遍历二叉树

二叉树的后序遍历是遍历中最难的，但是跟着我，你绝对能懂。 二叉树的后序遍历的难点无非在于何时输出节点。 使用一个变量plastvisit记录上一次访问的节点，这个辅助节点有什么用处？

我们使用plastvisit变量跟踪上一次访问的节点。假设栈顶元素是pcur。当plastvisit是pcur的父节点时，我们正在向下遍历树。此时，优先遍历curr的左孩子（将左孩子压入栈）。如果没有左孩子，再看右孩子。如果左右孩子都不存在（pcur是叶节点），就输出curr的值并弹出栈顶元素。如果plastvisit是pcur的左孩子，我们正在从左子树向上遍历。我们看一下pcur的右孩子。如果可以，就从右孩子向下遍历（将右孩子压入栈），否则打印pcur的值并弹出栈顶元素。如果plastvisit是pcur的右孩子，我们正在从右子树向上遍历。打印curr的值并弹出栈顶元素。 void fPostOrder(Tnode root){ //非递归后序遍历二叉树 if(root==NULL){ return; } stack<Tnode>s; Tnode pcur,plastvisit;//pcur是当前节点，plastxisit是上次访问的节点 pcur=root; plastvisit=NULL; while(pcur){ s.push(pcur); pcur=pcur->lchild ; } while(!s.empty() ){ pcur=s.top() ; s.pop() ; if(pcur->rchild ==NULL||pcur->rchild ==plastvisit){ cout<<pcur->data<<' ' ; plastvisit=pcur; } else{ s.push(pcur); pcur=pcur->rchild ; while(pcur){ s.push(pcur); pcur=pcur->lchild ; } } } }

4.6层序遍历二叉树

层序遍历很简单，我们需要借助队列

一开始，我们把根节点压入队列中循环直到队列为空 ①把队列首节点p弹出并且输出 ②把p的左右儿子依次压入队列(当然是在左右儿子存在的情况下) void CengOrder(Tnode T){ //层序遍历二叉树 if(!T) return; else{ Tnode p=T; Tnode q; queue<Tnode>s; s.push(p); while(!s.empty()){ q=s.front(); s.pop(); cout<<q->data<<' '; if(q->lchild ) s.push(q->lchild ); if(q->rchild ) s.push(q->rchild ); } } }

4.7判断二叉树是否为完全二叉树

完全二叉树:通俗的讲就是对于k层的二叉树来说，k-1层为满二叉树，k层所有叶子结点左边靠齐。

我们借助队列来进行层序遍历，遍历的时候考虑以下情况

存在某个节点，其左子树不存在而右子树存在，则返回false当遍历到k-1层时，对于k-1层的某个节点，如果其左子树不为空，而右子树为空，说明之后遍历的节点应该都为叶子节点，此时把isLeaf设置为true(对于k-1层和k层来说都是叶节点)如果isLeaf状态已经开启，而存在某个节点来说，它不是叶子节点(有儿子)，返回false

代码如下

bool panduanwanquan(Tnode root){//判断二叉树是否为完全二叉树 if (root) { queue<BTnode*>que; que.push(root); bool isLeaf = false; while (que.size()) { BTnode* p = que.front(); que.pop(); //如果左子树不存在 右子树存在 返回false if (!p->lchild && p->rchild) { return false; } //左子树不为空 而右子树为空 说明之后节点都为叶子节点 if (p->lchild && !p->rchild) { //若isLeaf状态已经开启 而该节点不是叶子节点 返回false if (isLeaf) { return false; } isLeaf = true; que.push(p->lchild); } //左右子树都为空 说明之后节点都为叶子节点 else if (!p->lchild && !p->rchild) { isLeaf = true; } //左右子树都不空 else { que.push(p->lchild); que.push(p->rchild); } } return true; } return false; }

4.8 显示二叉树

我采取显示二叉树的策略是，对于树根节点p ,以及左子树q和右子树k，我的显示为(p(q,k))。空节点用’#'显示。

void xianshi(Tnode T){ //显示二叉树 if(!T) cout<<"#"; else{ cout<<"("; cout<<T->data ; xianshi(T->lchild ); xianshi(T->rchild ); cout<<")"; } }

4.9非递归求二叉树的宽度

二叉树的宽度是指某一层最多的节点的个数。对于处理某一层的事件来说，我们一般都会借助队列来实现。 求二叉树的宽度的方法和层序遍历二叉树的方法很相似。 思路如下:

将根节点压入队列始终循环一下步骤 2.1 len = 当前队列的长度(表示的是当前某一层的节点个数) 2.2 当len == 0 ,退出循环(表示已经层序遍历至最底层) //为了统计下一层的节点个数，我们需要把当前层的节点都从对了pop出去 2.3 while(len > 0)//表示需要pop的节点的个数 2.3.1 pop队列的首节点q 2.3.2 len – 2.3.3 把节点q的左儿子和右儿子压入队列 (当把本层的所有节点pop完之后，我们队列中存储的都是下一层的节点，因此只要统计出len的最大值，就是我们想要的宽度) int fwidth(Tnode T){ //非递归求二叉树的宽度 if(T==NULL){ return 0; } int max=1; queue<Tnode>s; s.push(T); while(true){ int len=s.size() ; if(len==0) break; while(len>0){ Tnode t=s.front() ; s.pop() ; len--; if(t->lchild ) s.push(t->lchild ); if(t->rchild ) s.push(t->rchild ); } max=max>s.size() ? max:s.size(); } return max; }

5.实验代码如下

#include<iostream> #include<fstream> #include<stack> #include<queue> using namespace std; typedef struct BTnode *Tnode; //使用链式结构表示二叉树， struct BTnode{ //声明一个树的节点，它包含这个节点的数据以及指向左儿子和右儿子的指针 char data; Tnode lchild,rchild; //指向左右儿子的指针 } ; Tnode s1[100]; //用来创建递归树所用的数组 Tnode CreatTree(){ //非递归创建二叉树 int i,j; char c; Tnode bt,p;//用于存放节点 cin>>i>>c; while(i!=0&&c!='#') { p=new BTnode; p->data =c; p->lchild =NULL; p->rchild =NULL; s1[i]=p; if(i==1) bt=p; else if(i==2) bt->lchild =p; else{ j=i/2; if(i%2==0) { s1[j]->lchild=p; } if(i%2!=0) s1[j]->rchild=p; } cin>>i>>c; } return bt; } void PreCreatTree(Tnode *T){ //先序创建一个二叉树 char x; cin>>x; if(x=='#'){//'#'表示空节点 *T=NULL; } else{ *T=new BTnode;//给节点分配存储空间 if(!*T){ cout<<"error"<<endl; } else{ //先序递归创建二叉树 (*T)->data =x; PreCreatTree(&(*T)->lchild ); PreCreatTree(&(*T)->rchild ); } } } Tnode DuRuTree(){ //非递归创建二叉树 fstream in; in.open("erchashu.txt"); int i,j; char c; Tnode bt,p;//用于存放节点 in>>i>>c; while(i!=0&&c!='#') { p=new BTnode; p->data =c; p->lchild =NULL; p->rchild =NULL; s1[i]=p; if(i==1) bt=p; else if(i==2) bt->lchild =p; else{ j=i/2; if(i%2==0){ s1[j]->lchild=p; } if(i%2!=0) s1[j]->rchild=p; } in>>i>>c; } in.close() ; return bt; } void PreOrder(Tnode T){ //先序递归遍历二叉树 if(T==NULL){ return ; } cout<<T->data<<" "; PreOrder(T->lchild ); PreOrder(T->rchild ); } void InOrder(Tnode T){ //中序递归遍历二叉树 if(T==NULL){ return ; } InOrder(T->lchild ); cout<<T->data<<" "; InOrder(T->rchild ); } void PostOrder(Tnode T){ //后序递归遍历二叉树 if(T==NULL){ return ; } PostOrder(T->lchild ); PostOrder(T->rchild ); cout<<T->data<<" "; } void fPreOrder(Tnode root){ //非递归先序遍历二叉树 if(root==NULL){ return; } Tnode p=root; stack<Tnode>s; while(!s.empty()||p){ while(p){ cout<<p->data<<' ' ; s.push(p); p=p->lchild ; } if(!s.empty() ){ p=s.top() ; s.pop() ; p=p->rchild ; } } } void fInOrder(Tnode root){ //非递归中序遍历二叉树 if(root==NULL) return ; Tnode p=root; stack<Tnode>s; while(!s.empty()||p){ while(p){ s.push(p); p=p->lchild ; } if(!s.empty()){ p=s.top(); s.pop(); cout<<p->data<<' ' ; p=p->rchild ; } } } void fPostOrder(Tnode root){ //非递归后序遍历二叉树 if(root==NULL){ return; } stack<Tnode>s; Tnode pcur,plastvisit;//pcur是当前节点，plastxisit是上次访问的节点 pcur=root; plastvisit=NULL; while(pcur){ s.push(pcur); pcur=pcur->lchild ; } while(!s.empty() ){ pcur=s.top() ; s.pop() ; if(pcur->rchild ==NULL||pcur->rchild ==plastvisit){ cout<<pcur->data<<' ' ; plastvisit=pcur; } else{ s.push(pcur); pcur=pcur->rchild ; while(pcur){ s.push(pcur); pcur=pcur->lchild ; } } } } void CengOrder(Tnode T){ //层序遍历二叉树 if(!T) return; else{ Tnode p=T; Tnode q; queue<Tnode>s; s.push(p); while(!s.empty()){ q=s.front(); s.pop(); cout<<q->data<<' '; if(q->lchild ) s.push(q->lchild ); if(q->rchild ) s.push(q->rchild ); } } } bool panduanwanquan(Tnode root){//判断二叉树是否为完全二叉树 if (root) { queue<BTnode*>que; que.push(root); bool isLeaf = false; while (que.size()) { BTnode* p = que.front(); que.pop(); //如果左子树不存在 右子树存在 返回false if (!p->lchild && p->rchild) { return false; } //左子树不为空 而右子树为空 说明之后节点都为叶子节点 if (p->lchild && !p->rchild) { //若isLeaf状态已经开启 而该节点不是叶子节点 返回false if (isLeaf) { return false; } isLeaf = true; que.push(p->lchild); } //左右子树都为空 说明之后节点都为叶子节点 else if (!p->lchild && !p->rchild) { isLeaf = true; } //左右子树都不空 else { que.push(p->lchild); que.push(p->rchild); } } return true; } return false; } int fwidth(Tnode T){ //非递归求二叉树的宽度 if(T==NULL){ return 0; } int max=1; queue<Tnode>s; s.push(T); while(true){ int len=s.size() ; if(len==0) break; while(len>0){ Tnode t=s.front() ; s.pop() ; len--; if(t->lchild ) s.push(t->lchild ); if(t->rchild ) s.push(t->rchild ); } max=max>s.size() ? max:s.size(); } return max; } void xianshi(Tnode T){ //显示二叉树 if(!T) cout<<"#"; else{ cout<<"("; cout<<T->data ; xianshi(T->lchild ); xianshi(T->rchild ); cout<<")"; } } void zrh(){ //控制端函数 int n; Tnode t; t=DuRuTree(); cout<<"当前从文件中读入的二叉树为："<<endl; xianshi(t);//显示当前从文件读入的二叉树 cout<<endl; cout<<"0.退出"<<endl; cout<<"1.显示二叉树"<<endl; //实现 cout<<"2.先序递归建立二叉树"<<endl;//实现 cout<<"3.非递归建立二叉树"<<endl;//实现 cout<<"4.先序递归遍历二叉树"<<endl;//实现 cout<<"5.中序递归遍历二叉树"<<endl;//实现 cout<<"6.后序递归遍历二叉树"<<endl;//实现 cout<<"7.先序非递归遍历二叉树"<<endl;//实现 cout<<"8.中序非递归遍历二叉树"<<endl;//实现 cout<<"9.后序非递归遍历二叉树"<<endl;//实现 cout<<"10.层序遍历二叉树" <<endl;//实现 cout<<"11.判断二叉树是否为完全树"<<endl;//实现 cout<<"12.求二叉树的宽度"<<endl; //实现 cout<<"13.从文件读入并显示二叉树"<<endl; //实现 cin>>n; while(n!=0) { switch(n){ case 1: cout<<"当前二叉树为："; xianshi(t);//显示二叉树 cout<<endl; break; case 2: cout<<"2.先序递归建立二叉树(空节点用'#'表示)"<<endl;//实现 PreCreatTree(&t); break; case 3: cout<<"3.非递归建立二叉树(依次输入节点的标号和内容，输入0或#结束)："<<endl; t=CreatTree(); break; case 4: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"4.先序递归遍历二叉树的结果为："<<endl; PreOrder(t); cout<<endl; break; case 5: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"5.中序递归遍历二叉树的结果为："<<endl; InOrder(t); cout<<endl; break; case 6: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"6.后序递归遍历二叉树的结果为："<<endl; PostOrder(t); cout<<endl; break; case 7: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"7.先序非递归遍历二叉树的结果为："<<endl; fPreOrder(t); cout<<endl; break; case 8: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"8.中序递归遍历二叉树的结果为："<<endl; fInOrder(t); cout<<endl; break; case 9: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"9.后序递归遍历二叉树的结果为："<<endl; fPostOrder(t); cout<<endl; break; case 10: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"10.层序遍历二叉树的结果为："<<endl; CengOrder(t); cout<<endl; break; case 11: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"当前二叉树为完全二叉树？(1：是，2：不是)："<<panduanwanquan(t); cout<<endl; break; case 12: cout<<"当前二叉树为：";xianshi(t);cout<<endl; cout<<"当前二叉树的宽度为："<<fwidth(t); cout<<endl; break; case 13: cout<<"13.当前从文件读入的二叉树为："<<endl; t=DuRuTree(); xianshi(t); cout<<endl; break; case 0: n=0; break; default: cout<<"请输入0-13的数据："<<endl; break; } if(n==0) break; cout<<"0.退出"<<endl; cout<<"1.显示二叉树"<<endl; cout<<"2.先序递归建立二叉树"<<endl; cout<<"3.非递归建立二叉树"<<endl; cout<<"4.先序递归遍历二叉树"<<endl; cout<<"5.中序递归遍历二叉树"<<endl; cout<<"6.后序递归遍历二叉树"<<endl; cout<<"7.先序非递归遍历二叉树"<<endl; cout<<"8.中序非递归遍历二叉树"<<endl; cout<<"9.后序非递归遍历二叉树"<<endl; cout<<"10.层序遍历二叉树" <<endl; cout<<"11.判断二叉树是否为完全树"<<endl; cout<<"12.求二叉树的宽度"<<endl; cout<<"13.从文件读入二叉树"<<endl; cin>>n; } } int main(){ zrh();//调用控制端函数 }