一、实验目的
掌握二叉树的链式存储结构的建立方法和对二叉树的各种操作算法。利用二叉树的基本操作，构造哈夫曼树。
二、实验内容1
-
问题描述
(1)、按照前序次序建立一棵二叉树；
(2)、用前、中、后序递归遍历的方法遍历二叉树；
(3)、求二叉树的深度； -
数据结构及算法设计
首先，使用结构体建立树的基本结构BTNode，包括data，lchild，rchild。
再按照前序次序建立一颗二叉树，第一个元素是根节点，遇到‘#’将该结点定为空结点，遍历字符串，就按照前序次序建立了一颗树。
然后按照前序递归遍历（先输出根节点，再前序递归遍历左子女，最后前序递归遍历右子女）、中序递归遍历（先中序递归遍历左子女，再输出根节点，最后中序递归遍历右子女）、后序递归遍历（先后序递归遍历左子女，再前序递归遍历右子女，最后输出根节点）的特点分别写出对应函数，采用递归的思想。
最后设计函数求二叉树的深度。让检查到该节点下还存在左子树或右子树，计数并递归进入，当检查到没有左右子女时返回，最后返回计数+1，即二叉树的深度。
时间复杂度Ω(n)。效果图 -
程序实现
#include<bits/stdc++.h>
using namespace std;
typedef char ElemType;
typedef struct node //定义二叉树结构
{
ElemType data;
struct node *lchild;
struct node *rchild;
}BTNode;
void createBTree(BTNode * &b) //先序创建二叉树
{
char ch;
cin>>ch;
if(ch=='#') b=NULL; //遇到#时该节点为空
else{
b=new BTNode;
b->data=ch;
createBTree(b->lchild);
createBTree(b->rchild);
}
}
void preorder(BTNode *b) //先序遍历
{
if(b!=NULL)
{
printf("%c ",b->data); //访问根节点
preorder(b->lchild); //先序遍历左子树
preorder(b->rchild); //先序遍历右子树
}
}
void inorder(BTNode *b) //中序遍历
{
if(b!=NULL)
{
inorder(b->lchild); //中序遍历左子树
printf("%c ",b->data); //访问根节点
inorder(b->rchild); //中序遍历右子树
}
}
void postorder(BTNode *b) //后序遍历
{
if(b!=NULL)
{
postorder(b->lchild); //后序遍历左子树
postorder(b->rchild); //后序遍历右子树
printf("%c ",b->data); //访问根节点
}
}
int btheight(BTNode *b) //求二叉树的深度
{
int lchildh,rchildh;
if(b==NULL) return 0;
else
{
lchildh=btheight(b->lchild); //求左子树的高度为lchildh
rchildh=btheight(b->rchild); //求右子树的高度为rchildh
return (lchildh>rchildh)?(lchildh+1):(rchildh+1);
}
}
int main()
{
BTNode *b;
cout<<"先序创建二叉树："; //输入数据：AB#CD##E##F#GH###
createBTree(b);
cout<<"先序遍历输出：";
preorder(b);
cout<<endl<<"中序遍历输出：";
inorder(b);
cout<<endl<<"后序遍历输出：";
postorder(b);
cout<<endl<<"二叉树的深度："<<btheight(b);
btheight(b);
return 0;
}
- 测试
总结
本题采用二叉链表存储二叉树，二叉链表由数据元素，左孩子指针，右孩子指针组成。本次实验难度不大，对于初次接触树的概念的我来说是一次很好的锻炼机会，让我熟悉了建立二叉树的方法、先序递归遍历过程和方法、中序递归遍历过程和方法、后序递归遍历过程和方法、求二叉树的高度的函数，以及加深了对哈夫曼树的理解，同时，增强了我对于二叉树孩子与双亲的关系的理解，有助于更好的了解二叉树的结构。本次实验我还采用了递归算法，这也在一定程度上增强了我对递归的理解。