【数据结构】二叉树的链式结构

文章目录

• • 二叉树的链式存储方式
  • 二叉树的节点
  • 二叉树的遍历
  • • • 深度优先遍历(DFS)
      • • 前序遍历
        • 中序遍历
        • 后序遍历
      • 广度优先遍历(BFS)

二叉树的链式存储方式

二叉树的链式存储结构是指：用链表来表示元素间的逻辑关系

通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左右孩子的结点存储地址。

二叉树的节点

template <class T>
class BinaryTreeNode{
private:
    T val;
    BinaryTreeNode* _letf;
    BinaryTreeNode* _right;
public:
    BinaryTreeNode()
    :val(T())
    ,_letf(nullptr)
    ,_right(nullptr)
    {}
};

二叉树的遍历

所谓遍历（Traversal）是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所作的 *** 作依赖于具体的应用问题。遍历是二叉树最重要的运算之一，是二叉树进行其他运算的基础

深度优先遍历(DFS)

简单来说就是沿着二叉的一条路径走到尾从根结点到叶子结点遍历

任何一颗二叉树都可以看作根结点（N）、左子树(L)、右子树®。那么根据访问根节点的先后顺序可以把深度优先遍历二叉树分为这三种顺序。

前序遍历

前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的 *** 作发生在遍历其左右子树之前

比如上面的图片，前序遍历的顺序就为 A->B->D->NULL->NULL->NULL->C->E->NULL->NULL->F->NULL->NULL

先序遍历代码实现

void PreOrder(BTNode* root){
    if(root == nullptr){
        return;
    }
    std::cout<< root->val <<std::endl;
    PreOrder(root->_left);
    PreOrder(root->_right);
}

---

中序遍历

中序遍历(Inorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之中（间）

比如上面的图片，中序遍历的顺序为 NULL->D->NULL->B->NULL->A->NULL->E->NULL->C->NULL->F->NULL

中序遍历代码实现

void PreOrder(BTNode* root){
    if(root == nullptr){
        return;
    }
    PreOrder(root->_left);
    std::cout<< root->val <<std::endl;
    PreOrder(root->_right);
}

---

后序遍历

后序遍历(Postorder Traversal)——访问根结点的 *** 作发生在遍历其左右子树之后

比如上面的图片，后序遍历的顺序为 NULL->NULL->D->NULL->B->NULL->NULL->E->NULL->NULL->F->C->A

后序遍历代码实现

void PreOrder(BTNode* root){
    if(root == nullptr){
        return;
    }
    PreOrder(root->_left);
    PreOrder(root->_right);
    std::cout<< root->val <<std::endl;
}

---

广度优先遍历(BFS)

除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

层序遍历不需要递归，需要用其他的基本数据结构作为辅助，要用到队列

实现代码，对二叉树进行层序遍历

• 首先把根入进队列
• 队列不为空，出对头数据，同时把出掉的节点的左右孩子入进节点
• 直到队列为空

void BinaryTreeLevelOrder(BinaryTreeNode* root){
    if(root == nullptr)
        return;
    //如果不为空，把根入队列
    std::queue<BinaryTreeNode*> q;
    q.push(root);
    //对队列轮询检查
    while(!q.empty()){
        BinaryTreeNode* front = q.front();
        //出队头数据
        q.pop();
        std::cout<< front->val <<std::endl;
        //把队头节点的左右孩子入进队列
        if(front->_letf){
            q.push(front->_letf);
        }
        if(front->_right){
            q.push(front->_right);
        }
    }
}