数据结构-树(3)

二叉树的存储结构

第一篇博客里已经大概讲述了一下连续存储和顺序存储,下面我们再来具体看一下

链式存储

对于二叉树来说,每个节点的度都小于等于二,所以我们在定义节点时并不会造成大量的浪费,我们完全可以用链式结构来存储,同时类比单链表和双向链表,我们可以添加一个指针域来指向它的父节点

//
typedef struct Node{
    char val;
    struct Node *lChid,*rChild;
}BiTreeNode,*BiTree;
//

 

同样类比静态链表,三叉链表也有静态形式

 

连续存储

第一篇博客里讲到了如果要连续存储一棵树需要把它转换成完全二叉树,可以是从普通二叉树转化而来,也可以是一颗普通的树通过孩子兄弟表示法转化成的二叉树转化而来

转化成完全二叉树的优点就是存储时可以保证数的的逻辑结构也就是每个节点之间的关系,不会丢失,也可以存储起来,可以看看第一篇博客。下面我们来介绍四种遍历方法,可以把非线性的树变成线性的来存储。

序遍历

从上到下从左到右一层层的访问节点,就是按照ABCDEFGHIJ的顺序,当然我们要先把它补充成完全二叉树,按照你的要求补充的节点可以用0或者-1,或者空格,或者任何你需要的数字或者符号来表示,这里我就用0来表示,上面的二叉树中我们只需要给D添加一个左孩子他就变成了一棵完全二叉树,所以这棵树我们可以表示为ABCDEFG0HIJ

前序遍历

先访问根节点
再前序遍历左子树
再前序遍历右子树

我们会发现这其实是一个递归的过程

  1. 对于这棵树我们先访问它的根节点A,然后前序遍历它的左子树,也就是图二(我们把它补充成了完全二叉树)
  2. 同样它的左子树也是一颗二叉树,我们先访问它的根节点B,再前序遍历它的左子树,也就是图三
  3. 我们同样先访问它的根节点D,再访问它的左子树0,由于0是叶子节点我们可以返回上一层
  4. 也就是去前序遍历D的右子树H,同样H也是叶子节点,所以图二中B的左子树我们已经访问完了,我们该前序遍历B的右子树E… …

以此类推最后这棵树我们可以表示为ABD0HECFIJG

中序遍历

先中序遍历左子树
再访问根节点
再中序遍历右子树

同样也是一个递归的过程

  1. 先中序遍历这棵树的左子树,也就是图二
  2. 图二也是一颗二叉树,中序遍历它需要先中序遍历它的左子树,也就图三
  3. 图三也是一颗二叉树,中序遍历它需要先中序遍历它的左子树,0,因为0是叶子节点,可以返回上一层,也就是说D的左子树中序遍历结束
  4. 中序遍历图三这棵树的第二步,访问它的根节点,D
  5. 中序遍历D的右子树,H,因为H是叶子节点,可以返回上一层,也就是说D的右子树中序遍历结束,到现在为止图二这棵树的左子树中序遍历结束
  6. 中序遍历图二这棵树的第二步,访问它的根节点B
  7. 中序遍历B的右子树… …

以此类推最后这棵树我们可以表示为0DHBEAIFJCG

如果你还不明白你可以形象的想象为一根垂直的激光从左向右扫描这棵树

后序遍历

先后序遍历左子树
再后序遍历右子树
再访问根节点

  1. 先后序遍历A的左子树也就是图二
  2. 图二也是一颗二叉树,对它进行后序遍历需要先后序遍历它的左子树,也就是图三
  3. 图三也是一颗二叉树,对它进行后序遍历需要先后序遍历它的左子树,0,因为0是叶子节点,可以返回上一层,也就是说D的左子树后序遍历结束
  4. 后序遍历图三这棵树的第二步,后序遍历它的右子树,也就是H,因为H是叶子节点,可以返回上一层,也就是说D的右子树后序遍历结束
  5. 后序遍历图三这棵树的第三步,访问根节点D,图三这棵树后序遍历结束,可以返回上一层,也就是说图二这棵树的左子树后序遍历结束
  6. 后序遍历图二这棵树的第二步,后序遍历它的右子树… …

以此类推最后这棵树我们可以表示为0HDEBIJFGCA

还原二叉树

对于一棵完全二叉树来说,无论是上面的哪中方法得到的结果我们都可以将他还原出来,因为完全二叉树我们可以用log2(n)向下取整+1来计算该树深度(这个在后面的性质中会讲到),知道深度后,我们就可以很简单的将这棵树还原出来了

但是假如我们没有把它转换成完全二叉树,进行前序遍历,我们得到的结果是ABDHECFIJG,我们知道前序遍历的结果,但是我们却无法还原,因为对于这样一个结果,如果按照不同的深度还原可以还原出不同的树,又比如AB,我们就可以还原出两种结果,B是A的左孩子或者右孩子

但是当我们知道一棵树的两种遍历结果的时候就可以还原出这棵树了

:已知前序遍历结果ABDHECFIJG  和  中序遍历结果DHBEAIFJCG,求二叉树

前序遍历最先访问的一定是根节点,所以A是根节点

中序遍历先访问左子树,再访问根节点,所以A的左边DHBE是左子树,右边IFHJCG是右子树

前序遍历中DHBE这棵树先访问的是B,所以B是DHBE这棵树的根节点

中序遍历中B的左边DH是DHBE这棵树的左子树E是右子树

前序遍历中DH这棵树先访问的是D,所以D是DH这颗树的根节点

中序遍历中D的右边是H,所以H是D的右子树也就是右孩子

… …以此类推最后我们就可以还原出这棵树了

注意:知道前序和后序并不能求出原树

二叉树的建立

如果我们输入ABC来创建一棵二叉树,有人说我们并不能把它创建出来,因为我们并不知道它的遍历顺序!好,假如用户输入的ABC是前序遍历结果。有人说既然是前序遍历,那么A是根节点,B是左孩子,C是右孩子!其实这只适用于完全二叉树,从上一节的还原中我们也可以看出,如果你的遍历结果中只含有有效的节点,我们是无法成功的创建出这棵二叉树的。

这里我们可以用这样的办法,把一棵普通的二叉树变成这个样子

我们实际上是把每个节点不存在的孩子用空指针显式的表示出来了,在存储时并没有浪费空间,因为每个节点都有两个指针域,一个指向左孩子另一个指向右孩子,同时我们也会发现对于节点数为N的二叉树,它的NULL指针域为N+1。这个树叫扩展二叉树

有人可能会问,为什么不是把它转化成一棵完全二叉树呢,这样实际上我们只需要添加A的右孩子一个节点就可以了啊!

在这里必须要弄清楚一件事情,现在上图所示的方法中并没有添加任何新的节点,只是显式的把节点中指针域的NULL值显示的表示出来了,而如果是补充成一个完全二叉树,我们必须要先计算出二叉树的深度,而上面的方法却不需要。

下面我们来看一下根据前序遍历结果建立二叉树的代码

//
typedef struct Node
{
    char val;
    struct Node *lChild,*rChild;
} BiTreeNode,*BiTree;

void createBiTree(BiTree &T)
{
    char c;
    scanf("%c",&c);
    if(c == '#')
    {
        T = NULL;
    }
    else
    {
        T = (BiTree)malloc(sizeof(Node));
        T->val = c;
        preOrdCreateBiTree(T->lChild);//创建该节点的左子树
        preOrdCreateBiTree(T->rChild);//创建该节点的右子树
    }
}
//

这里用的是c++如果用c,需要用二级指针

前序遍历代码

//
void preOrderTraverse(BiTree T,int level)
{
    if(T == NULL) return;//空树返回

    int n = level;
    while(n--)
    cout << "   ";//根据层数缩进
    printf("第%d层,%c\n",level,T->val);
    if(T->lChild!=NULL)//存在左子树,就前序遍历左子树
    preOrderTraverse(T->lChild,level+1);
    if(T->rChild!=NULL)
    preOrderTraverse(T->rChild,level+1);
}
//

测试

//
/*
输入

ABC##D###
  
输出

   第1层,A
      第2层,B
         第3层,C
         第3层,D
*/
//

前序遍历(非递归实现)

//
void preOrderTraverseByStack(BiTree T)
{
    /*
    先访问自身,如果右子树不为空就将右子树压入栈
    如果左子树不为空,遍历左子树
    如果左子树为空,pop出父节点的右子树,遍历右子树
    如果pop出的结果为NULL说明没有可以遍历的右子树,遍历结束
    后入栈的右子树,先访问
    */
    stack<BiTree> s;
    s.push(NULL);
    while(T!=NULL)
    {
        visit(T);
        if(T->rChild!=NULL)
            s.push(T->rChild);
        if(T->lChild!= NULL)
            T = T->lChild;
        else T = s.top();
    }
}
//

 

注:扩展二叉树的中序遍历结果并不能确定唯一的二叉树,后序遍历结果可以通过栈辅助进行创建,类似于求逆波兰表达式,空指针是操作数,而非空节点是运算符。我们需要把操作数压栈,遇到运算符时,操作数出栈计算再入栈。

//
void postOrdCreateBiTree(BiTree &T)
{
    stack<BiTree> s;
    string str;
    cin >> str;
    for(int i = 0; i<str.length(); ++i)
    {

        char c = str[i];
        if(c == '#')
            s.push(NULL);
        else
        {
            BiTree newT = (BiTree)malloc(sizeof(Node));
            newT->val =c;
            newT->rChild = s.top();
            s.pop();
            newT->lChild= s.top();
            s.pop();
            s.push(newT);
        }
    }
    T = s.top();
    s.pop();
}
//

 

发表评论

邮箱地址不会被公开。 必填项已用*标注