二叉排序树

定义

二叉排序树是一棵特殊的二叉树,它是一棵二叉树但同时满足如下条件:
对于树上任意一个结点,其上的数值
必大于等于其左子树上任意结点数值,
必小于等于其右子树上任意结点的数值。

中序遍历二叉排序树得到的就是递增的序列

二叉排序树的插入

1.若当前树为空,则 x 为其根结点。
2.若当前结点大于 x,则 x 插入其左子树;若当前结点小于 x,则 x 插入其
右子树;若当前结点等于 x,则根据具体情况选择插入左右子树或者直接忽略。
所以可以通过递归来实现

1
2
3
4
5
6
7
8
9
10
11
12
Node* insert_node(int data,Node *node){
if (node==NULL){
return new Node(data);

}
if (data<node->data){
node->left = insert_node(data,node->left);
} else if (data>node->data){
node->right = insert_node(data,node->right);
}
return node;
}

比较两棵树是否完全一样

如果两个树的中序和先序(或后序)遍历完全相同,则这两颗树完全相同。
也可以直接递归的进行比较

1
2
3
4
5
6
7
8
9
10
11
12
bool compare_two_tree(Node *root_1 , Node *root_2){
if (root_1==NULL&&root_2==NULL){
return true;
}
else if (root_1&&root_2){
if (root_1->data==root_2->data){
return compare_two_tree(root_1->left,root_2->left)&&compare_two_tree(root_1->right,root_2->right);
} else
return false;
} else
return false;
}