排序二叉树的性质如下：
若他的左子树不空，则左子树上所有的结点均小于它的根结点的值。
若他的右子树不空，则右子树上所有的结点均大于它的根结点的值。
他的左右子树也是排序二叉树。
深度为k的完全二叉树至少有2^(k - 1)个结点；
最多有2^k - 1个结点。
#include<iostream> using namespace std; struct Node { int data; Node *lchild; Node *rchild; }; Node *Tree_Insert(Node *T, int key); // 二叉排序的树的插入 Node *Create(); // 二叉树的创建 void inOrder(Node *T); // 二叉排序树的中序遍历 int Tree_Min(Node *T); // 二叉树中的最小值 int Tree_Max(Node *T); // 二叉树中的最大值 int Tree_CengNum(Node *T); // 计算二叉树的层级 void Level_Print(Node *T, int level); // 打印二叉树某一层的所有结点 int Level_Count(Node *T, int level); // 打印二叉树某一层的结点个数 bool Tree_Search(Node *T, int key); // 二叉树的搜索 void Delete(Node *T, int k); // 删除某个元素的结点 void Delete(Node *T, int k) { if(Tree_Search(T, k)) { // 查找 要删除的结点temp Node *temp = T; while(temp) { if(temp->data == k) break; else temp = (k < temp->data) ? temp->lchild : temp->rchild; } if(temp->lchild) // 若有左子树 { Node *temp1 = temp->lchild; Node *temp2 = temp1; while(temp2->rchild) // 去查找左子树中最右边的结点 { temp1 = temp2, temp2 = temp2->rchild; } // 用左子树中最右边的点覆盖要删除的点 temp->data = temp2->data; if(temp1 != temp2) // 若左子树有右结点 temp1->rchild = temp2->lchild; else // 若temp左子树没有右结点 temp->lchild = temp2->lchild; free(temp2); } else // 若无左子树 { Node *q = temp; q = q->rchild; free(q); q = NULL; } } else cout<<"没有这个数，无法删除！"; } bool Tree_Search(Node *T, int key) { Node *temp = T; int i = 1; while(temp) { if(temp->data == key) { cout<<"在第"<<i++<<endl; return true; } else { i++; temp = (key < temp->data) ? (temp->lchild) : (temp->rchild); } } return false; } void Level_Print(Node *T, int level) { if(!T)return; if(level == 1) cout<<T->data; else { Level_Print(T->lchild, level -1); Level_Print(T->rchild, level -1); } } int Level_Count(Node *T, int level) { if(T == NULL || level < 1 || level > Tree_CengNum(T)) { return 0; } if(level == 1) return 1; return Level_Count(T->lchild, level - 1) + Level_Count(T->rchild, level -1); } int Tree_CengNum(Node *T) { if(NULL==T){ return 0; }else{ int lh=Tree_CengNum(T->lchild); int rh=Tree_CengNum(T->rchild); return (lh>rh)?(lh+1):(rh+1); } } int Tree_Min(Node *T) { Node *temp = T; while(temp->lchild) { temp = temp->lchild; } return temp->data; } int Tree_Max(Node *T) { Node *temp = T; while(temp->rchild) { temp = temp->rchild; } return temp->data; } // 二叉排序的树的插入 Node *Tree_Insert(Node *T, int key) { Node *p = T; Node *temp1, *temp2; while(p != NULL) { temp1 = p; if(key == p->data) { cout<<"要插入的节点已存在，不必再插入！"<<endl; return T; } p = (key > p->data) ? p->rchild : p->lchild; } temp2 = new Node; temp2->data = key; temp2->lchild = NULL; temp2->rchild = NULL; if(T == NULL) return temp2; if(key < temp1->data) temp1->lchild = temp2; else temp1->rchild = temp2; return T; } Node *Create() { int key; Node *T = NULL; cout<<"输入节点数据值为（-1）为结束值"<<endl; cin>>key; while(key != -1) { T = Tree_Insert(T, key); cin>>key; } return T; } // 二叉排序树的中序遍历 void inOrder(Node *T) { if(T) { inOrder(T->lchild);; cout<<T->data; inOrder(T->rchild); } return; } int main() { cout<<"二叉树的构建"<<endl; Node *T = Create(); cout<<"二叉树的中序遍历"<<endl; inOrder(T); cout<<"输出该二叉树的层级"<<endl; cout<<Tree_CengNum(T)<<endl; cout<<"输入要打印的层n:"<<endl; int n; cin>>n; cout<<endl; Level_Print(T, n); cout<<"输入要查找的结点n:"; cin>>n; cout<<Tree_Search(T, n)<<endl; //打印二叉树某一层的结点个数 cout<<"输入要打印的某层n,求该层的结点个数"<<endl; cin>>n; cout<<Level_Count(T, n)<<endl; // system("pause"); return 0; }
