数据结构中的二叉树

喜欢ヅ旅行 2022-08-05 08:29 162阅读 0赞

二叉树：  
使用范围最广，且最有规律可循，容易维护处理

使用二叉链表来表示二叉树的存储结构

typedef struct BiTNode
    {
        ElemType data;                  //存放节点数据
        struct BiTNode *lchild,*rchild; //指向左孩子和右孩子节点的指针
    }BiTNode,*BiTree;

二叉树的遍历：  
从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个节点被访问一次且仅被访问一次  
遍历方法：  
a).前序遍历(先序遍历)  
b).中序遍历  
c).后序遍历  
d).层序遍历

代码如下，包括二叉树的建立及其遍历

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    
    typedef struct BiTNode
    {
        ElemType data;
        struct BiTNode *lchild,*rchild;
    }BiTNode,*BiTree;
    //创建一棵二叉树，约定用户按照前序遍历的方式输入数据
    void createBiTree(BiTree *T)
    {
        char c;
        scanf("%c",&c);
        if(' '==c)
        {
            *T=NULL;
        }else
        {
            *T=(BiTNode *)malloc(sizeof(BiTNode));
            (*T)->data=c;
            createBiTree(&(*T)->lchild);
            createBiTree(&(*T)->rchild);
        }
    }
    //访问二叉树的具体操作
    
    void visit(char c,int level)
    {
        printf("%c 位于第 %d 层\n",c,level);
    }
    //前序遍历二叉树
    void preOrderTraverse(BiTree T,int level)
    {
        if(T)
        {
            visit(T->data,level);
            preOrderTraverse(T->lchild,level+1);
            preOrderTraverse(T->rchild,level+1);
            /*
            中序遍历
            preOrderTraverse(T->lchild,level+1);
            visit(T->data,level);
            preOrderTraverse(T->rchild,level+1);
    
            后序遍历
            preOrderTraverse(T->lchild,level+1);
            preOrderTraverse(T->rchild,level+1);
            visit(T->data,level);
            */
        }
    }
    int main()
    {
        int level =1;
        BiTree T=NULL;
    
        createBiTree(&T);
        preOrderTraverse(T,level);
    
        return 0;
    }

二叉树在实现的时候会浪费很多的空间，因为叶子节点的两个孩子指针必为空，而且一般的二叉树的非叶子节点也可能为空；同时如果已知某节点，访问其后继节点很简单，但是 如果想访问其前驱节点就需要遍历整个树结构，时间复杂度高  
于是我们想到是否有一种方式可以节省"^"所浪费的空间呢？  
答案是肯定的，在中序遍历的基础上，利用"^"来记录该节点的前驱和后继-----这就是线索二叉树  
将原来定义好的结构进行"扩容"，记录前驱和后继的节点  
  
Po图 简单明了~  
![Center][]

下面写代码实现：

#include <stdio.h>
    #include <stdlib.h>
    
    typedef char ElemType;
    
    //线索存储标志位
    //Link(0):表示指向左右孩子的指针
    //Thread(1):表示指向前驱后继的线索
    typedef enum {Link,Thread} PointerTag;
    
    typedef struct BiThrNode
    {
        ElemType data;
        struct BiThrNode *lchild,*rchild;
        PointerTag ltag;
        PointerTag rtag;
    }BiThrNode,*BiThrTree;
    
    
    //全局变量，始终指向刚刚访问过的节点
    BiThrNode *pre;
    
    //创建一棵二叉树，要求用户按照先序顺序输入数据
    void creatBiThrTree(BiThrTree *T)
    {
        char c;
        scanf("%c",&c);
        if(' '==c)
        {
            *T=NULL;
        }else
        {
            *T=(BiThrNode *)malloc(sizeof(BiThrNode));
            (*T)->data=c;
            (*T)->ltag=Link;
            (*T)->rtag=Link;  //先假定全部节点均有孩子节点
    
            creatBiThrTree(&(*T)->lchild);
            creatBiThrTree(&(*T)->rchild);
        }
    }
    
    //中序遍历实现线索化
    void inThreading(BiThrTree T)
    {
        if(T)
        {
            inThreading(T->lchild);//递归左子树线索化
            //处理当前节点
            if(!T->lchild)    //如果没有左孩子
            {
                T->ltag=Thread;  //修改当前节点的ltag，表示指向前驱或者后继的索引
                T->lchild=pre;   //左孩子指针指向刚刚访问过的节点
            }
             if(!pre->rchild)
             {
                 pre->rtag=Thread;
                 pre->rchild=T;
             }
             pre=T;  //pre总是指向刚刚访问过的节点
    
             inThreading(T->rchild);//递归右子树线索化
        }
    }
    
    void inOrderThreading(BiThrTree *p,BiThrTree T)
    {
        *p=(BiThrNode *)malloc(sizeof(BiThrNode));  //创建"头结点"
        (*p)->ltag=Link;
        (*p)->rtag=Thread;
        (*p)->rchild=*p;    //初始化该节点，左指针指向树的根节点，右指针指向前驱，最终也就是指向树遍历的最后一个节点
    
        if( !T ) //如果是空树，左指针指向自己
        {
            (*p)->lchild=*p;
        }
        else   //非空树，则指向根节点
        {
            (*p)->lchild=T;
            pre=*p;           //指向刚刚访问过的节点的指针----初始化指向头结点
            inThreading(T);  //中序遍历索引完成后，pre指向树最后遍历的节点
            pre->rchild=*p;
            pre->rtag=Thread;
            (*p)->rchild=pre;  //实现树的最后一个节点与头指针首尾相连
        }
    }
    
    void visit(char c)
    {
        printf("%c",c);
    }
    //中序遍历二叉树，非递归
    void inorderTraverse(BiThrTree P)
    {
        BiThrTree p;  //p相当于一个头指针，左孩子节点指向根节点如果树非空
        p=P->lchild;  //p指向根节点
    
        while(p!=P)   //当树非空或者树未遍历结束
        {
            while(p->ltag==Link)  //如果一直有左孩子
            {
                p=p->lchild;
            }
            visit(p->data);   //先找到第一个访问的节点
    
            //此后就根据节点的后继节点访问
            while(p->rtag==Thread && p->rchild!=P) //如果该节点有后继节点而且整棵树未遍历完
            {
                p=p->rchild;    //右指针指向了后继
                visit(p->data);
            }
            p=p->rchild;   //去访问右子树
        }
        //其实中序遍历索引二叉树，根节点的遍历均是根据节点的后继指针来访问的
    }
    int main()
    {
        BiThrTree P,T=NULL;
    
        creatBiThrTree(&T);
    
        inOrderThreading(&P,T);
        printf("中序遍历输出结果为:");
        inorderTraverse(P);
    	printf("\n");
        return 0;
    }

树、森林及二叉树的相互转换  
  
对于树和森林这样的不具有规律的数据结构，对它的处理显然要复杂得多，所以对结构进行限定形成了有规律可循的二叉树  
那么在遇到一般树形结构或者森林的时候，只需要按照一定的规则转换为二叉树，然后进行数据的处理或者遍历  
  
树有两种遍历方式：  
先根遍历  
后根遍历  
  
森林也有两种遍历方式：其实就是按照树的先根遍历和后根遍历依次访问森林的每一棵树  
先序遍历  
后序遍历  
  
  
而且我们发现：树、森林的前根（序）遍历和二叉树的前序遍历相同，树、森林的后根（后序）遍历和二叉树的中序遍历结果相同！！！更加确定了我们转换为二叉树处理的合理性

[Center]: /images/20220731/b723dd4009cd447486109146df8cd34a.png