1：二叉排序树，又称二叉树。其定义为：二叉排序树或者空树，或者是满足如下性质的二叉树。
（1）若它的左子树非空，则左子树上所有节点的值均小于根节点的值。
（2）若它的右子树非空，则右子树上所有节点的值均大于根节点的值。
（3）左、右子树本身又各是一颗二叉排序树。
上述性质简称二叉排序树性质（BST性质），故二叉排序树实际上是满足BST性质的二叉树。
2：代码如下：
#include "stdafx.h"#include#include #include using namespace std;//定义节点类class Node{public: int data;//数据 Node *parent;//父亲节点 Node *left;//左子节点 Node *right;//右子节点public: Node() :data(-1), parent(NULL), left(NULL), right(NULL) {}; Node(int num) :data(num), parent(NULL), left(NULL), right(NULL) {};};//二叉排序树类定义class Tree{public: Tree(int num[], int len);//插入num数组的前len个数据 void insertNode1(int data);//插入节点，递归方法 void insertNode(int data);//插入节点，非递归方法 //Node *searchNode(int data);//查找节点，递归方法 void deleteNode(int data);//删除节点及其子树，递归方法 void InOrderTree();//中序遍历，递归方法 void InOrderTree(Node* current);//用于中序遍历,递归方法 void PreOrderTreeUnRec();//中序遍历，非递归方法private: void insertNode(Node* current, int data);//递归插入方法 Node *searchNode(Node* current, int data);//递归查找方法 void deleteNode(Node* current);private: Node* root;//二叉树的根节点};//插入num数组的前len个数据Tree::Tree(int num[], int len){ root = new Node(num[0]);//建立root节点,为num[0]分配一个地址 //把数组中的其他数组插入到二叉树中 for (int i = 1; i < len; i++) { //insertNode(num[i]); insertNode1(num[i]); }}//插入数据为参数data的节点，非递归方法void Tree::insertNode1(int data)//插入节点{ Node *p, *par;//p用于遍历节点，par用于保存节点 Node *newNode = new Node(data);//创建节点 p = par = root; while (p != NULL)//查找插入在哪个节点下面 { par = p;//保存节点 if (data > p->data)//如果data大于当前节点的data，下一步到左子节点，否则进行到右子节点 p = p->right; else if (data < p->data) p = p->left; else if (data == p->data)//不能插入重复数据 { delete newNode; return; } } newNode->parent = par; if (par->data > newNode->data)//把新节点插入在目标节点的正确位置 par->left = newNode; else par->right = newNode;}//插入数据为参数data的节点，调用递归插入方法void Tree::insertNode(int data){ if (root != NULL) { insertNode(root, data);//调用递归插入方法 }}//递归插入方法void Tree::insertNode(Node * current, int data){ //如果data小于当前节点数据，则在当前节点的左子树插入 if (data < current->data) { if (current->left == NULL)//如果左节点不存在，则插入到左节点 { current->left = new Node(data); current->left->parent = current; } else insertNode(current->left, data);//否则对左节点进行递归调用 } //如果data大于当前节点数据，则在当前节点的右子树插入 else if (data > current->data) { if (current->right == NULL)//如果右节点不存在，则插入到右节点 { current->right = new Node(data); current->right->parent = current; } else insertNode(current->right, data);//否则对右节点进行递归调用 } return;//data等于当前节点数据时，不插入}//递归查找方法Node *Tree::searchNode(Node* current, int data){ //如果data小于当前节点数据，则递归搜索左子树 if (data < current->data) { if (current->left == NULL)//如果不存在左子树，则返回NULL return NULL; return searchNode(current->left, data); } //如果data大于当前节点数据，则递归搜索右子树 else if (data > current->data) { if (current->right == NULL)//如果不存在右子树，则返回NULL return NULL; return searchNode(current->right, data); } //如果相等，则返回current return current;}//删除数据为data的节点及其子树void Tree::deleteNode(int data){ Node *current = NULL; //current = searchNode(data);//查找节点 current = searchNode(current,data);//查找节点 if (current != NULL) { //deleteNode(current); deleteNode(data); }}//删除current节点及其子树的所有节点void Tree::deleteNode(Node *current){ if (current->left != NULL)//删除左子树 { deleteNode(current->left); } if (current->right != NULL)//删除右子树 { deleteNode(current->left); } if (current->parent == NULL)//如果current是根节点，把root置空 { delete current; root = NULL; return; } //将current父亲节点的相应指针置空 if (current->parent->data > current->data)//current为其父节点的左子节点 current->parent->left = NULL; else//current为parNode的右子节点 current->parent->right = NULL; //最后删除此节点 delete current;}//中序遍历,递归方法void Tree::InOrderTree(){ if (root == NULL) return; InOrderTree(root);}//用于中序遍历void Tree::InOrderTree(Node* current){ if (current != NULL) { InOrderTree(current->left);//遍历左子树 cout << current->data << " "; InOrderTree(current->right);//遍历右子树 }}int main(){ Node m_node(1); cout << "节点类的数据为："< << endl; int num[] = { 5,3,7,2,4,6,8,1 }; Tree tree(num, 8); cout << "InOrder:" << endl; tree.InOrderTree();//中序遍历，递归方法 return 0;}
