数据结构之二叉树的实现（二）

爱被打了一巴掌 2022-05-25 09:38 123阅读 0赞

### 1.0 顺序存储结构 ###

这个很简单的 就是给二叉树按完全二叉树编号，及时没有左子树也要给他编号，然后编号就是数组的下标

为了避免麻烦 我们浪费数组的第.0号存储单元 这样找他的双亲和孩子节点的时候就可以按照[性质5][5] 进行查找

这样遇到右斜树会造成大量的存储空间的浪费，所以仅仅适合用于存储完全二叉树

### 2.0 二叉链表 ###

节点结构如下

struct Node{
        int data;
        Node* lchild;//指向左孩子
        Node* rchild;//指向右孩子
    }

即每个二叉树节点的结构如上 如果左孩子或者右孩子不存在则指向空

再次重温一下二叉树的几个遍历操作

1.  前序遍历 访问顺序 中左右
2.  中序遍历 左中右
3.  后序遍历 左右中
4.  程序遍历 一层一层来

代码实现（递归）

//前序遍历
    
    void preOrder(Node* bt){
        if(bt == NULL)return;//递归出口
        cout<<bt->data;          //中
        preOrder(bt->lchild);    //左
        preOrder(bt->rchild);    //右
    }
    
    //后序遍历
    //左右中
    void PostOrder(Node* bt){
        if(bt == NULL)return;//递归出口
        PostOrder(bt->lchild);//左
        PostOrder(bt->rchild);//右
        cout<<bt->data;       //中 
    }
    
    //中序遍历
    //左中右
    void InOrder(Node* bt){
        if(bt == NULL)return;//递归出口
        InOrder(bt->lchild);//左
        cout<<bt->data;       //中
        InOrder(bt->rchild);//右
    }
    
    //层序遍历
    /* 层序遍历是用队列实现的 首先初始化队列 然后跟结点入队 读取队首结点后该结点的孩子节点入队 知道队列全部读完 理解不了的拿个二叉树看一下就知道了 下面看具体实现 */
    void LeverOrder(){
        //初始化队列
        Node* Q[100];
        int  rear,front ;
        rear = front = -1;
        Q(++rear) = root;
        while(rear != front){
            Node* p = Q(++front);
            cout<<p->data;
            if(p->lchild != NULL) Q(++rear)=p->lchild;
            if(p->rchild != NULL) Q(++rear)=p->rchild;  
        }
    }
    
    //二叉树的初始化
    /* 二叉树的三种遍历情况都不能唯一确定一颗二叉树 因为二叉树没有建立 不能确定左右子树的情况 也就是说不知道还有没有左右子树 也就是不能确定是否为空 为了解决这个问题 我们在建立二叉树的时候为每个空结点从新指向一个新的结点并且给他的值设为特定的 值 例如 -1000 或者是其他的字符 */
    
    Node* creat(Node* bt){
        int ch;
        cin>>ch;
        if(ch == -1000){
            bt = NULL;
        }else{
            bt = new Node;
            bt->data = ch;
            bt->lchild = creat(bt->lchild);
            bt->rchild = creat(bt->rchild);
        }
        return bt;
    }
    
    //释放 析构函数
    
    void  Release(Node* p){
        if(p != NULL){
             Release(p->lchild);
             Release(p->rchild);
             delete p;
        }
    
    }

### 3.0 三叉链表 ###

就是增加一个指向双亲结点的指针

struct Node{
        int data;
        Node* lchild;
        Node* rchild;
        Node* parent;
    }

这种结构便于查找双亲和孩子节点 但是增加了空间开销

### 4.0 线索链表\* 略写 ###

结构

struct Node{
        int data;
        Node* lchild;
        Node* rchild;
        int lch;
        int rch;
    }

也就是新增了 lch 与 rch  
lch 值为0 表示指向对应的左孩子节点 1表示指向其前驱  
rch 值为0 表示指向对应的右孩子节点 1表示指向其后继

这里的前序和后继对不同的遍历次序所表示的各不相同 本节暂不详细介绍

线索链表我暂时的了解就是他不是遍历 而是遍历后记录了响应的遍历信息在原来的结点上

### 5.0 二叉树的非递归实现伪代码 ###

#### 5.1 前序遍历的非递归算法 ####

主要用到的数据结构是栈  
伪代码

1.0 栈s初始化
    2.0 对根结点bt  循环直到bt为空 并且 栈也为空
        2.1  当bt不空是循环
            2.1.1 输出bt->data
            2.1.2 把 bt 压入栈
            2.1.3 bt = bt->lchild
        2.2 如果栈s不是空 则
            2.2.1 将栈顶元素弹出赋值给bt
            2.2.2 准备遍历bt的右子树 即 bt = bt->rchild;

#### 5.2 中序遍历的非递归算法 ####

1.0 栈s的初始化
    2.0 对根结点bt 循环直到他为空  并且栈也是空
        2.1  当bt不空是循环
            2.1.1 bt 压栈
            2.1.2 bt = bt->lchild; 就是访问左子树
    
        2.2 如果栈s不是空 则
            2.2.1 将栈顶元素弹出赋值给bt 
            2.2.2 输出bt->data;
            2.2.3 bt = bt->rchild;

#### 5.3 后续遍历的非递归算法 ####

后续遍历和其他的额都不一样  
结点要入栈两次 出栈两次 这时栈的元素类型要有标示为 标志他是第几次出栈

1.0 栈的初始化
    2.0 循环直到bt是空 并且栈也是空
        2.1 当bt不是空的时候循环
            2.1.1 bt 入栈 标识为设置为1
            2.1.2 bt = bt->lchild;
        2.2 栈不空并且标志是2时候  出栈并且输出栈顶数据
        2.3  如果栈不是空的  酒吧标志设为2  准备准备遍历右子树即  bt = bt->rchild

### 6.0 树转换为二叉树 ###

1.  加线 左右相邻的兄弟节点之间加线
2.  去线 对于每个节点 只保留其与第一个孩子之间的连线 其余去掉 注意新加的线不去
3.  调整 调整其层次结构

之后便有如下关系

树的前序遍历 == 二叉树的前序遍历  
树的后续遍历 == 二叉树的中序遍历

[5]: https://blog.csdn.net/qq_35794278/article/details/80242273