树

树是结点的有限集合,必须符合条件

当n=0时，为空树

当n>0时，除根结点外，其他结点为m(m>0)个不相交的非空集合

树的度：所有结点的度的最大值。

树的深度：所有结点层次的最大值

二叉树

是在树的结构上建立的，比树的定义更要严密。

区别在于：二叉树只有左，右子树我们先来对比下

A)为有右子树为空的二叉树 B)为左子树为空的二叉树 C）是一颗子树的树

二叉树的遍历：

深度遍历

广度遍历

非递归遍历

共同点：

都具有先序遍历。访问根结点，遍历左子树，遍历右子树

不同点：

深度遍历

也称为内部遍历，采用栈的形式，根据二叉树自身构成，访问节点和子树的不同顺序，分别先序，中序和后序遍历

实例：

如上图，它的先序遍历是怎样被访问的

A的左子树有BDGEH，根据，根，左，右的访问顺序，依次访问，最后的顺序为 ABDGEHCF

广度遍历

采用队列的形式，逐层向下遍历，每层从左到右顺序访问

如下图：

访问的次序为A,B,C,D,EF,G,H

非递归遍历：

也称为外部遍历，是栈和队列的结合，和递归的不同点在于，非递归运用循环的特点，如果一测子树是否为空，直到循环为空为止才肯结束。

非递归也是分为先，中，后序遍历的。

具体的一些算法结构如下

先序遍历

对于任一结点P：

1)访问结点P，并将结点P入栈;

2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;

3)直到P为NULL并且栈为空，则遍历结束。

具体的C算法如下

void preOrder2(BinTree*root)     //非递归前序遍历{    stack
    
      s;    BinTree *p=root;    while(p!=NULL||!s.empty())    {        while(p!=NULL)        {           cout<
     
      data<<" ";            s.push(p);            p=p->lchild;        }        if(!s.empty())        {            p=s.top();            s.pop();            p=p->rchild;        }    }}

后序与中序的遍历顺序与递归的访问基本也是相同的这里不在累述。

小结

二叉树的遍历，有深度，广度和非递归的遍历。

它们的相同点：都是按照某种顺序，访问根，左右子树

不同点：深度遍历是运用栈的特点，广度遍历是运用队列特点，而非递归是结合以上两种方式（比较繁琐）。二叉树的遍历为数据的查询提供了很大的遍历。

转载于:https://www.cnblogs.com/james1207/p/3283337.html

你可能感兴趣的文章