
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.二叉树的中序遍历

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

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小丑西瓜9/article/detail/531360