二叉树知识点最详细最全讲解

typedef int Type;


typedef struct BSTreeNode{
    Type   key;//关键字（键值）
    struct BSTreeNode *left;//左孩子
    struct BSTreeNode *right;//右孩子
    struct BSTreeNode *parent;//父节点
}Node ,*BSTree;

二叉查找树的节点包含的基本信息：

1、key——关键值，是用来对二叉查找树的节点进行排序的。

2、left——指向当前节点的左孩子。

3、right——指向当前孩子的右节点。

4、parent——指向当前节点的父节点。

3.3.3.2创建节点

struct Node* create_bstree_node(Type key,Node *parent,Node *left, Node* right)
{
    Node* p;
    if ((p = (Node *)malloc(sizeof(Node))) == NULL)
        return NULL;
    p->key = key;
    p->left = left;
    p->right = right;
    p->parent = parent;

    return p;
}

我这里只是写了一部分，本篇文章的重点不在这里，想继续研究或者想更深入了解的可以转一下博主：https://www.cnblogs.com/skywang12345/p/3576328.html#a2

3.4平衡二叉搜索树

3.4.1定义

平衡二叉树搜索树：又被称为AVL(Adelson-Velsky and Landis)树，且具有以下性质：它是一颗空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一颗平衡二叉树。如图：

4.二叉树的存储方式

4.1链式存储

通过指针把分布在散落在各个地址的节点串联在一起，链式存储如图所示：

4.2顺序存储

其实就是用数组来存储二叉树，顺序存储的方式如图：

4.2.1数组存储的遍历

如果父节点的数组下标是i,那么它的左孩子就是2 * i + 1,右孩子就是i * 2 + 2。（但是用链式表示的二叉树更有利于我们理解，一般都是用链式存储二叉树）

5.二叉树的遍历方式

5. 1、深度优先遍历

①前序遍历（递归法，迭代法）中左右

②中序遍历（递归法，迭代法）左中右

③后序遍历（递归法，迭代法）左右中

5. 2、广度优先遍历

①层次遍历（迭代法）

6.遍历的实现（递归实现）

6.1递归算法三要素

1、确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。

2、确定终止条件：写完了递归算法, 运行的时候，经常会遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。

3、确定单层递归的逻辑：确定每一层递归需要处理的信息。在这里也就会重复调用自己来实现递归的过程。

以前序遍历为例：

1、「确定递归函数的参数和返回值」：因为要打印出前序遍历节点的数值，所以参数里需要传入vector在放节点的数值，除了这一点就不需要在处理什么数据了也不需要有返回值，所以递归函数返回类型就是void，代码如下：

void traversal(TreeNode* cur, vector<int>& vec)

2、「确定终止条件」：在递归的过程中，如何算是递归结束了呢，当然是当前遍历的节点是空了，那么本层递归就要要结束了，所以如果当前遍历的这个节点是空，就直接return，代码如下：

if (cur == NULL) return;

3、「确定单层递归的逻辑」：前序遍历是中左右的循序，所以在单层递归的逻辑，是要先取中节点的数值，代码如下：

vec.push_back(cur->val);    // 中
traversal(cur->left, vec);  // 左
traversal(cur->right, vec); // 右

6.2代码实现（递归）

前序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        vec.push_back(cur->val);    // 中
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

中序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        vec.push_back(cur->val);    // 中
        traversal(cur->right, vec); // 右
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

后序遍历：

class Solution {
public:
    void traversal(TreeNode* cur, vector<int>& vec) {
        if (cur == NULL) return;
        traversal(cur->left, vec);  // 左
        traversal(cur->right, vec); // 右
        vec.push_back(cur->val);    // 中
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int> result;
        traversal(root, result);
        return result;
    }
};

此时可以做一做leetcode上三道题目练练手，分别是：

144.二叉树的前序遍历
145.二叉树的后序遍历
94.二叉树的中序遍历

此处是二叉树的遍历，此前我还有一篇文章是表达式的遍历，也可以看看

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

[转载]在Windows环境下安装GNU Radio

转自：在Windows环境下安装GNURadio_恐弱智_新浪博客GNU Radio是用Python开发的，大部分开源的工程能够在Linux环境下运行良好，而Windows下却运行的很勉强，而且安装配置都很复杂。GNU Radio算是个例外了，不光提供了Windows的二进制安装，还有比较详细的说明。我是Python小白，所以折腾了好久才弄好，特意记录下来，免得以后再装还折腾。GNU Radio的

GitCode 开源社区

centOS 8 使用dnf安装Docker

DNF是什么？CentOS 8使用YUM软件包管理器版本v4.0.4。现在，该版本使用DNF(已删除YUM)。DNF是软件包管理器。它会在Linux发行版上安装，执行更新并删除软件包。使用DNF安装Docker跳过具有损坏依赖性的程序包一个有效的解决方案是使您的CentOS 8系统使用以下--nobest命令安装最符合条件的版本：sudo dnf install docker...

GitCode 开源社区

定时同步数据库表(mysql+linux+crontab)

sync.sh里面的参数需要改变，ip/username/password/database/tablesync.sh#!/bin/sh# Please change the IP and password of the data source db.# Then change the table name.filename=/home/nington/db/$(date +%Y-%m