实用数据结构之二叉排序树小结
实用数据结构之二叉排序树小结：
定义：
满足以下条件的二叉树：
对于树上任意一个结点，其上的数值必大于等于其左子树上任意结点的数值
必小于等于其右子树上任意结点的数值
故二叉排序树的插入：
1.若当前树为空，则x为其根结点
2.若当前结点大于x，则x插入其左子树, 若当前结点小于x,则x插入其右子树
若当前结点等于x,则根据具体情况选择插入左子树或者右子树或者直接忽略
例如： 输入一系列整数，建立二叉排序树，并进行前序，中序，后序遍历
输入：
5
1 6 5 9 8
输出：
1 6 5 9 8
1 5 6 8 9
5 8 9 6 1
#include <iostream>#include <cstring>using namespace std;struct Node//二叉树结点结构体{Node *lchild;//左儿子指针Node *rchild;//右儿子指针int c;//结点字符信息}Tree[110];//静态内存分配数组int loc;//静态数组中已经分配的结点个数Node *create()//申请一个结点空间，返回指向其的指针{Tree[loc].lchild = Tree[loc].rchild = NULL;//初始化左右儿子为空return &Tree[loc++];//返回指针，loc自增}void preOrder(Node *T)//先序遍历{cout<<T->c<<" ";if (T->lchild!=NULL)preOrder(T->lchild);if (T->rchild!=NULL)preOrder(T->rchild);}void inOrder(Node *T)//中序遍历{if (T->lchild!=NULL)inOrder(T->lchild);cout<<T->c<<" ";if (T->rchild!=NULL)inOrder(T->rchild);}void postOrder(Node *T)//后序遍历{if (T->lchild!=NULL)postOrder(T->lchild);if (T->rchild!=NULL)postOrder(T->rchild); cout<<T->c<<" ";}Node* insert(Node* root,int value){if (root==NULL)//若当前树为空{root = create();root->c = value;return root;}elseif (root->c <value){root->rchild = insert(root->rchild,value);}else if(root->c > value){root->lchild = insert(root->lchild,value);}return root;}int main(){int n;while(cin>>n){loc = 0; Node *root = NULL; for (int i=0;i<n;i++) { int value; cin>>value; root = insert(root,value); }preOrder(root);cout<<endl;inOrder(root);cout<<endl;postOrder(root);cout<<endl;} // system("pause");return 0;}