数据结构-二叉树以及遍历代码

二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

一棵深度为k，且有2^k-1个结点的二叉树，称为满二叉树。这种树的特点是每一层上的结点数都是最大结点数。而在一棵二叉树中，除最后一层外，若其余层都是满的，并且或者最后一层是满的，或者是在右边缺少连续若干结点，则此二叉树为完全二叉树。具有n个结点的完全二叉树的深度为floor(log2n)+1。深度为k的完全二叉树，至少有2k-1个叶子结点，至多有2k-1个结点。

二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。

一、特殊的二叉树及特点

1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少

左斜树

右斜树

2、满二叉树

所有的分支结点都存在左子树和右子树，并且所有的叶子结点都在同一层上，这样就是满二叉树。

满二叉树

根据满二叉树的定义，其特点为：

1. 叶子只能出现在最下一层。
2. 非叶子结点度一定是2.
3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。

3、完全二叉树

完全二叉树：对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。

完全二叉树最重要的性质：如果n个节点的完全二叉树的节点按照层次并按从左到右的顺序从0开始编号，特点有：

• 序号为0的节点是根

• 对于i>0，其父节点的编号为(i-1)/2。

• 若2·i+1

• 若2·i+2

4、二叉树遍历

遍历二叉树：就是按照系统化的方式访问二叉树里的每一个节点。

• 这是二叉树的一个重要性质：每棵二叉树都有唯一的根节点，可以将其看做这棵二叉树的唯一标识，是基于树结构的处理入口。

深度优先遍历：按照一条路径尽可能的向前探索， 直至检查完一个叶节点。

遍历实例

1.先根序遍历(前序遍历)：先访问根节点，而后以同样的方式顺序遍历左子树和右子树。就是先访问根结点，再先序遍历左子树，最后再先序遍历右子树即根—左—右。结果：A -> B -> D -> H -> E -> I -> C -> F -> J -> K ->G

前序递归遍历的代码实现：

<code>//前序递归遍历
void PreOrderTraverse(BiTree *root)
{
  //注意跳出条件
    if(root != NULL)
    {
       //注意访问语句顺序
        printf("%c ", root->data);
        PreOrderTraverse(root->lchild);
        PreOrderTraverse(root->rchild);
    }
}/<code>

非递归实现：

根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：

对于任一结点P：

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

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

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

<code>//前序非递归遍历
void preOrder2(BinTree *root)     //非递归前序遍历 
{
    stack<bintree> 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;
        }
    }
}/<bintree>/<code>

2.后根序遍历(后序遍历)：先以同样的方式遍历左右子树，最后遍历根节点。 结果：H -> D -> I -> E -> B -> J -> K -> F -> G -> C -> A

1）后序递归遍历

<code>1）中序递归遍历void postOrder1(BinTree *root)    //递归后序遍历
{
    if(root!=NULL)
    {
        postOrder1(root->lchild);
        postOrder1(root->rchild);
        cout<<root->data<    }    
}/<root->/<code>

2）后序非递归遍历

后序遍历：需要判断上次访问的节点是位于左子树，还是右子树。若是位于左子树，则需跳过根节点，先进入右子树，再回头访问根节点；若是位于右子树，则直接访问根节点。

<code>void postOrder1(BinTree *root){
        if (root == NULL)
          return;
        stack<bintree> s;
        //pCur:当前访问节点，pLastVisit:上次访问节点
        BinTree* pCur, *pLastVisit;
        //pCur = root;
        pCur = root;
        pLastVisit = NULL;
        //先把pCur移动到左子树最下边
        while (pCur)
        {
          s.push(pCur);
          pCur = pCur->lchild;
        }
        while (!s.empty())
        {
          //走到这里，pCur都是空，并已经遍历到左子树底端(看成扩充二叉树，则空，亦是某棵树的左孩子)
          pCur = s.top();
          s.pop();
          //一个根节点被访问的前提是：无右子树或右子树已被访问过
          if (pCur->rchild == NULL || pCur->rchild == pLastVisit)
          {
            cout  << pCur->data;
            //修改最近被访问的节点
            pLastVisit = pCur;
          }
          /*这里的else语句可换成带条件的else if:
          else if (pCur->lchild == pLastVisit)//若左子树刚被访问过，则需先进入右子树(根节点需再次入栈)
          因为：上面的条件没通过就一定是下面的条件满足。仔细想想！
          */
          else
          { 

            //根节点再次入栈
            s.push(pCur);
            //进入右子树，且可肯定右子树一定不为空
            pCur = pCur->rchild;
            while (pCur)
            {
              s.push(pCur);
              pCur = pCur->lchild;
            }
          }
        }
}\t/<bintree>/<code>

3.中根序遍历(中序遍历)：先以同样的方式遍历左子树，然后访问根节点，最后以同样的方式遍历右子树。 结果： D -> H ->B -> E -> I -> A -> J -> F -> K -> C -> G

1）中序递归遍历

<code>void InOrderTraverse(BiTree *root)
{
    if(root != NULL)
    {
        InOrderTraverse(root->lchild);
        printf("%c ", root->data);
        InOrderTraverse(root->rchild);
    }
}/<code>

2）中序非递归遍历

根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一个根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才停止访问，然后按相同的规则访问其右子树。其处理过程如下：

对于任一结点：

a. 若其左孩子不为空，则将p入栈，并将p的左孩子设置为当前的p，然后对当前结点再进行相同的操作；

b. 若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的p置为栈顶结点的右孩子；

c. 直到p为空并且栈为空，则遍历结束。

<code>//中序非递归遍历
void InOrderTraverse(BiTree* root)
{
\t//空树
\tif (root == NULL)
\t\treturn;
\t//树非空
\tBiTree* p = root;
\tstack<bitree> s;
\twhile (!s.empty() || p)
    {
      //一直遍历到左子树最下边，边遍历边保存根节点到栈中
      while (p)
      {
          s.push(p);
          p = p->lchild;
      }
      //当p为空时，说明已经到达左子树最下边，这时需要出栈了
      if (!s.empty())
      {
          p = s.top();
          s.pop();
          cout<data<          //进入右子树，开始新的一轮左子树遍历(这是递归的自我实现) 

          p = p->rchild;
      }
    }
}/<bitree>/<code>

五、二叉树的建立

其实而二叉树的建立就是二叉树的遍历，只不过将输入内容改为建立结点而已，比如，利用前序遍历建立二叉树

<code>//创建树
//按先后次序输入二叉树中结点的值(一个字符),#表示空树
//构造二叉链表表示的二叉树
BiTree CreateTree(BiTree t)
{
    char ch;
    scanf("%c", &ch);
 
    if(ch == '#')
    {
        t = NULL;
    }
    else
    {
        t = (BitNode *)malloc(sizeof(BitNode));
        if(t == NULL)
        {
            return;
        }
 
        t->data = ch;                        //生成根结点
        t->lchild = CreateTree(t->lchild);    //构造左子树
        t->rchild = CreateTree(t->rchild);    //构造右子树
    }
    return t;
}/<code>

閱讀更多 嘎嘎皮皮來了 的文章

關鍵字: 斜树 数据结构 不完美妈妈