本文共 4629 字，大约阅读时间需要 15 分钟。
二叉搜索树/二叉排序树（Binary Search Tree）：
1：它或者是一棵空树。
2：具有下列性质的：
(1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
(2)若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
(3)它的左、右子树也分别为；
(4)没有键值相等的结点。
以下代码实现了BST的插入，删除，查找，前序、中序、后序遍历的递归和非递归，层序遍历。
#include #include #include #include #include #include #include using namespace std;struct Node{ int data; //数据域 Node* lchild; //左子树 Node* rchild; //右子树 }; Node* Create_BST(int key) //创建结点 { Node* p=(Node*)malloc(sizeof(Node)); p->data=key; p->rchild=NULL; p->lchild=NULL; return p;} Node* Insert_BST(Node* T , int key) //插入结点 { if(T==NULL) //如果T为空，那么创建新结点。 { T=Create_BST(key); } else if(T->data>key) //如果要插入的值小于T结点的值，那么往T的左子树上查找位置插入 { T->lchild=Insert_BST(T->lchild,key); } else if(T->data rchild=Insert_BST(T->rchild,key); } return T;}Node* Find(Node* T,int key) //查找值为key的结点 { if(T==NULL) { return NULL; } else if(T->data>key) { return Find(T->lchild,key); } else if(T->data rchild,key); } else { return T; }}Node* FindMax(Node* T) //查找值最大的结点 { if(T==NULL) { return NULL; } else if(T->rchild!=NULL) { T = FindMax(T->rchild); } return T;}Node* FindMin(Node* T) //查找值最小的结点 { if(T==NULL) { return T; } else if(T->lchild!=NULL) { T = FindMin(T->lchild); } return T;}Node* Delete_BST(Node* T , int key) //删除值为key的结点 { if(T==NULL) { return NULL; } else if(T->data>key) { T->lchild = Delete_BST(T->lchild,key); } else if(T->data rchild = Delete_BST(T->rchild,key); } else //当T就是要删除的那个结点时 { if(T->lchild && T->rchild)//如果T的左右子树都不为空 { //要找左子树的最大值，或者是右子树的最小值来替代这个位置 Node* tmp = FindMin(T->rchild); T->data=tmp->data; T->rchild=Delete_BST(T->rchild,tmp->data); } else if(T->rchild==NULL&&T->lchild==NULL) { delete T; T=NULL; } else //左子树和右子树中有一个为空 { if(T->lchild) { Node* tmp=T; T=T->lchild; delete tmp; } else { Node* tmp=T; T=T->rchild; delete tmp; } } } return T;} void PreOrder(Node* T) //前序遍历 递归 { if(T==NULL)return; else { printf("%d ",T->data); PreOrder(T->lchild); PreOrder(T->rchild); }}void MidOrder(Node* T) //中序遍历 递归 { if(T==NULL)return; else { MidOrder(T->lchild); printf("%d ",T->data); MidOrder(T->rchild); }} void PostOrder(Node* T) //后序遍历 递归 { if(T==NULL)return; else { PostOrder(T->lchild); PostOrder(T->rchild); printf("%d ",T->data); }} void LevelOrder(Node* T) //层序遍历 队列 { if(T==NULL)return; queue q; Node* p; q.push(T); while(!q.empty()) { p=q.front(); q.pop(); if(p->lchild!=NULL) { q.push(p->lchild); } if(p->rchild!=NULL) { q.push(p->rchild); } printf("%d ",p->data); }}void PrintPre(Node* T) //前序遍历 栈（非递归） { if(T==NULL)return ; stack s; Node* p=T; Node* q; while(p!=NULL||!s.empty()) //结点不为空||栈中有元素 { if(p) { printf("%d ",p->data); //先访问根节点 s.push(p); //根节点入栈 p=p->lchild; //访问左子树 } else //当p结点为空时 代表没有左右节点了 即p现在是叶子结点 { q=s.top(); //使p的根节点出栈 s.pop(); p=q->rchild; //访问右子树 } }} void PrintMid(Node* T) //中序遍历 栈（非递归） { if(T==NULL)return ; stack s; Node* p=T; Node* q; while(p!=NULL||!s.empty()) { if(p) { s.push(p); //先访问左子树，使左子树根节点进栈 p=p->lchild; //找到左子树的最底层 } else { q=s.top(); s.pop(); printf("%d ",q->data); //输出根节点 p=q->rchild; //右子树入栈 } } } void PrintPost(Node* T) //后序遍历 栈（非递归） 左右根 { if(T==NULL)return; stack s; Node* p=T; //p存放当前访问结点 Node* q=NULL; //q存放上次访问的结点 while(p!=NULL) //首先要访问左子树，所以不断的将根入栈，找到左子树的最底层 { s.push(p); p=p->lchild; } while(!s.empty()) { p=s.top(); //将栈顶元素出栈 s.pop(); //结点能够被访问的前提是：没有右子树，或者是右子树刚被访问过 if(p->rchild==NULL||p->rchild==q) { printf("%d ",p->data); q=p; //更新访问过的结点 } else //有右子树且右子树未被访问 { s.push(p); //此结点再次入栈 p=p->rchild;//进入右子树进行访问，而且右子树一定不为空 while(p) //到达右子树中左子树的最低层 { s.push(p); p=p->lchild; } } } } int Height_BST(Node* T) //BST的高度 { if(T==NULL)return 0; else { return max(Height_BST(T->rchild),Height_BST(T->lchild))+1; }}int main(){ int n; //n个结点 int num; Node* Tree = NULL; scanf("%d",&n); for(int i=0;i data); //最小值 printf("MaxKey: %d\n",FindMax(Tree)->data); //最大值 printf("\n\n----------------------------\n"); printf("前序遍历（递归）：\n"); PreOrder(Tree); printf("\n\n"); printf("前序遍历（非递归）：\n"); PrintPre(Tree); printf("\n\n"); printf("中序遍历（递归）：\n"); MidOrder(Tree); printf("\n\n"); printf("中序遍历（非递归）：\n"); PrintMid(Tree); printf("\n\n"); printf("后序遍历（递归）：\n"); PostOrder(Tree); printf("\n\n"); printf("后序遍历（非递归）：\n"); PrintPost(Tree); printf("\n\n"); printf("层序遍历 ：\n"); LevelOrder(Tree); printf("\n\n"); printf("\n\n----------------------------\n"); printf("BST的高度： %d\n",Height_BST(Tree)); printf("\n\n----------------------------\n"); printf("请输入要查找的数字：\n"); int x; scanf("%d",&x); if(Find(Tree,x)!=NULL) printf("存在！\n"); else printf("不存在！\n"); printf("\n\n----------------------------\n"); printf("请输入要删除的数字：\n"); scanf("%d",&x); Tree=Delete_BST(Tree,x); printf("删除后的序列（中序）：\n"); MidOrder(Tree); return 0;}
转载地址：http://gvzci.baihongyu.com/