二叉树的性质及例题分析（更新中）

目录

一、二叉树

1、相关术语

2、结构形式 

3、二叉树的遍历

二、二叉搜索树

1、定义与性质：  

 2、二叉搜索树的创建与插入

1、相关术语

• 结点的度：一个结点含有的子树的个数称为该结点的度
• 叶结点：度为0的结点称为叶结点（终端结点）
• 分支结点：度不为0的结点称为分支结点（非终端结点）
• 结点的层次：从根结点开始，根结点的层次为1，以此类推
• 树的度：树中所有结点的度的最大值
• 树的高度(深度)：树中结点的最大层次
• 森林：m个互不相交的树的集合，将一颗非空树的根结点删去，树就变成一个森林
• 子结点：一个结点的直接后继结点称为该结点的子结点
• 双亲结点(父结点)：一个结点的直接前驱称为该结点的双亲结点
• 兄弟结点：同一双亲结点的孩子结点间互称兄弟结点
• 满二叉树：如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树
• 完全二叉树：满二叉树删去右侧几个叶节点所得的树

2、结构形式 

class TreeNode {
private:
	int val;
	TreeNode *left;
	TreeNode *right;
public:
    TreeNode() : val(0), left(NULL), right(NULL) {}
	TreeNode(int x) : val(x), left(NULL), right(NULL) {}
}

3、二叉树的遍历

• 前序遍历：先访问根结点，再访问左子树，最后访问右子数（ABDECFG）
• 中序遍历：先访问左子树，再访问根节点，最后访问右子树（DBEAFCG）
• 后序遍历：先访问左子树，再访问右子树，最后访问根节点（DEBFGCA）
• 层序遍历：逐层访问二叉树（ABCDEFG）

二、二叉搜索树

1、定义与性质：  

        二叉搜索树是一棵二叉树，它可以为空；如果不为空，则满足以下性质：

• 根结点的键值 大于 非空左子树的所有键值，小于 非空右子树的所有键值
• 左、右子树都是二叉搜索树。

 2、二叉搜索树的创建与插入

• 创建：对于任意有序序列（不含重复元素），都有唯一的二叉搜索树与之对应；
• 插入：新元素与根节点比较，小则进入左子树，大则进入右子树；若子树为空，则插入。

	void Insert_Node(TreeNode* root,int val) {
		if (root == nullptr) {
            root = new TreeNode(val);
            return;
        }
		if (val < root->val)
			Insert_Node(root->left, val);
		else
			Insert_Node(root->right, val);
	}

3、二叉搜索树例题

（1）对于有 n 个元素的无序序列，能构造多少种不同的二叉搜索树？（动态规划，搜索）

          https://leetcode.cn/problems/unique-binary-search-trees/

          https://leetcode.cn/problems/unique-binary-search-trees-ii/submissions/