C++编程练习(8)----“二叉树的建立以及二叉树的三种遍历方式“(前序遍历、中序遍历、后续遍历)

时间:2022-01-12 06:17:57

利用顺序存储和链式存储的特点,可以实现树的存储结构的表示,具体表示法有很多种。

1)双亲表示法:在每个结点中,附设一个指示器指示其双亲结点在数组中的位置。

2)孩子表示法:把每个结点的孩子排列起来,以单链表作存储结构,则n个结点有n个孩子链表,如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表,采用顺序存储结构,存放进一个一维数组中。

3)孩子兄弟表示法:任意一棵树,它的结点的第一个孩子如果存在就是唯一的,它的右兄弟如果存在也是唯一的。因此,可以设置两个指针,分别指向该结点的第一个孩子和此结点的右兄弟。--------------该表示法的一大好处就是它把一棵复杂的树变成了一棵二叉树。

二叉树

二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成  -------------------文字描述里面已含有递归的思想。

特殊二叉树:

1)斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

2)满二叉树:在一棵二叉树中,如果所有分支节点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

3)完全二叉树:对一棵具有 n 个结点的二叉树按层序编号,如果编号为 i(1<=i<=n)的结点与同样深度的满二叉树中编号为 i 的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

遍历二叉树

二叉树的遍历(traversing bianry tree)是指从根结点出发,按照某种次序依次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。

1)前序遍历:规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树----------------------递归思想

2)中序遍历:规则是若树为空,则空操作返回,否则从根结点开始(仅仅是开始,先不访问该结点),中序遍历根结点的左子树,然后是访问根结点(访问),最后中序遍历右子树--------------------递归思想

3)后序遍历:规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后是访问根结点。

4)层序遍历:规则是若树为空,则空操作返回,否则从树的第一层,也就是根结点开始访问,从上而下逐层遍历,在同一层中,按从左到右的顺序对结点逐个访问。

遍历性质:

1、已知前序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

2、已知后序遍历序列和中序遍历序列,可以唯一确定一棵二叉树。

但注意:已知前序和后序遍历,是不能确定一棵二叉树的。

具体实现代码如下:

/* BiTree.h头文件 */
#include<iostream>
typedef char TElemType; class BiTNode{ /*创建结点类,使用的是左右孩子表示法*/
public:
BiTNode():data(0),lchild(NULL),rchild(NULL){}
TElemType data;
BiTNode *lchild,*rchild;
}; void CreateBiTree(BiTNode **T) /*二叉树的建立,这里形参用的是双指针,需要注意*/
{
std::cout<<"请前序遍历输入各节点:"; /*这里输入的是一个扩展二叉树,每个结点若有空指针,*/
TElemType ch; /*则将其值设为一个特定值,本代码中是'#'*/
std::cin>>ch;
std::cin.clear();
if(ch=='#')
*T=NULL;
else
{
*T=new BiTNode;
if(!*T)
exit(1);
(*T)->data=ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
} void PreOrderTraverse(BiTNode *T) /*前序遍历*/
{
if (T==NULL)
return;
std::cout<<T->data<<"\t";
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
} void InOrderTraverse(BiTNode *T) /*中序遍历*/
{
if (T==NULL)
return;
InOrderTraverse(T->lchild);
std::cout<<T->data<<"\t";
InOrderTraverse(T->rchild);
} void PostOrderTraverse(BiTNode *T) /*后序遍历*/
{
if(T==NULL)
return;
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
std::cout<<T->data<<"\t";
}

运行结果如下:

C++编程练习(8)----“二叉树的建立以及二叉树的三种遍历方式“(前序遍历、中序遍历、后续遍历)