c++ - 将节点插入二叉树时要遵守什么规则？

Question

我知道在二叉搜索树中，元素是根据不等式的属性插入的，即:

 if(n->val > val) insert(n->left, val);  // root node greater then val insert to left 
 else if(n->val < val) insert(n->right, val);  // root node less then val insert to left 

 // I am ignoring the case when n->val == val here

我很好奇我应该在什么基础上将节点插入纯( Vanilla )二叉树，如果有一个或所有二叉树都带有一些额外的属性(二叉搜索树及其不等式)。

Answer 1

General二叉树由节点组成，其中每个节点包含一个“左”引用、一个“右”引用和一个数据元素。树中最顶端的节点称为根。数据顺序没有其他限制。

但是二叉树有很多种。在文献中，您可以看到完整、完整、平衡等。它们都有自己的树结构规则。例如 full binary tree 是一棵树，其中除叶子之外的每个节点都有两个 child 。 平衡二叉树 的叶节点具有最小可能的最大高度。这些特定的树类型引入了额外的属性。