1、二叉查找树的类型定义
typedef int DataType; //结点关键码的数据类型
typedef struct node
{
DataType data; //结点的数据值
struct node * lchild, *rchild; //指向左、右子女结点的指针
}BiTNode, *BiTree;
注意：BiTNode 等价于 struct node；*BiTree 等价于 struct node*。
2、判别给定的二叉树是否是二叉查找树
void binSearchTree (BiTNode *t, BiTNode * & pr, int & bs)
{
//t赋予根结点指针root,pr赋予NULL,bs赋予1
//t为当前子树根结点
//pr是当前子树根结点t的前驱指针
if(t != NULL && bs)
{
binSearchTree (t->lchild, pr,bs); //递归到左子树判断
if(pr == NULL)
{
pr = t; bs = 1;
}
else
{
if(t->data > pr->data)
{
pr = t; bs = 1;
}
else
bs = 0;
}
if(bs)
binSearchTree (t->rchild, pr,bs); //递归到右子树判断
}
}
注意：
①、因为当前子树根结点t的前驱指针的值一直在改变，故采用的是指针的引用形式
②、指针的引用，相当于传递的是： 指针的指针，这样指针的数值是可以改变的；而单传递指针，不传递指针的引用，那么指针指向的数据是可以改变，而指针本身是不可以改变的 （示例）——简单讲：*&指针本身可变； **指针本身不变，仅指向的内容可变
fun(int * pA); // pA的数值在函数返回后不会变化
fun(int*& pA); // pA的数值在函数返回可能会发生变化，如果fun函数内部对pA赋值的话
void InitStack(LNode*& HS)
{
HS = NULL; // 函数返回后,HS就是NULL了
}
void InitStack(LNode* HS)
{
HS = NULL; // 函数返回后,HS依然是传递进来的数值
}
3、递归实现从大到小输出所有不小于x的关键码
void Output(BSTNode *t,Datatype x){
if(t != NULL){
if(t->rchild != NULL)
Output(t->rchild,x);
if(t->data >= x)
printf("%d",t->data);
if(t->lchild != NULL && t->lchild->data >= x)
Output(t->lchild,x);
}
}
4、时间复杂度为O(log2n),查找第k小的元素,增加一个count成员，保存以该结点为根的字数上的结点个数
BSTNOde *Search_small(BSTNode *t,int k)
{
if（k<1 || k>t->count）
return NULL;
if(t->lchild && t->lchild->count == k-1)
return t;
if(t->lchild && t->lchild->count > k-1)
return Search_Small(t->lchild,k);
if(!t->lchild)
return Search_Small(t->rchild,k-1);
if(t->lchild && t->lchild->count < k-1)
return Search_Small(t->rchild, t->count - t->lchild->count - 1);
}
5、求指定结点在二叉查找树中的层次
int level_Count(BSTree & T, BSTNode *p)
{
int level=0;
BSTNode * q=T;
if(q!=NULL)
{
level++;
while(q!=NULL && q->data!=p->data){
if(q->data < p->data)
q=q->rchild;
else q = q->lchild;
level++;
}
if(q==NULL)
level=0;
}
return level;
}
6、按折半查找判定树的生成方法构造二叉查找树
void Create_BestBST(BSTNode *&t, int low, int high, dataTYpe k[]){
if(low >high)
t = NULL;
else{
int m=(low +high)/2;
t=new BSTNode;
t->data=k[m];
Create_BestBST(t->lchild,low,m-1,k);
Create_BestBST(t->lchild,m+1,high,k);
}
}
7、中序遍历二叉树，将结果存放于A[n]中
void InOrderTraverse（BSTNode *t,DataType A[].int &n）{
if(t!=NULL){
InOrderTraverse(t->lchild,A,n);
A[n++]=t->data;
InOrderTraverse(t->rchild,A,n);
}
}
8、将n个值不同的元素A[n]插入到一个空的二叉查找树中
void BSTI（BSTree &T,DataTYpe A[],int n）
{
BSTNOde *p,*pr, *q;
int 1;
for(i=0; i<n; i++){
q=new BSTNode;
q->data=A[i];
q->lchild=q->rchild=NULL;
if(T == NULL)
T=q;
else{
p=T;
pr=NULL;
whi9le(p!=NULL && p->data !=q->data)
{
pr=p;
if(p->data < q->data)
p=p->rchild;
else
p=p->lchild;
}
if(p== NULL)
if(q->data <pr->data)
pr->lchild=q;
else pr->rchild=q;
}
}
}
9、向二叉查找树中插入一个元素，入树中已经有该元素，则将匹配结点中的count域的值加1，否则该元素作为新结点插入
void Insert1(BSTNode *&t, BSTNode *& pr, DataTYpe x)
{
BSTNode *p=t;
while(p != NULL)
{
if(p->data != x){
pr=p;
if(x < p->data)
p=p->lchild;
else p=p-rchild;
}
else(p->count++;return;)
}
BSTNode *s = new BSTNode;
s->data=x;s->count=1;
s->lchild=s->rchild=NULL;
if(pr==NULL)
t=s;
else if(x <pr->data)
pr->lchild=s;
else r->rchild=s;
};
10、二叉查找树上的插入
int Insert(BSTree& root, DataType x){
BSTNode *s,*p,*f;
p=Search(root,x,f);
if(p!=NULL)
return 0;
s=new BSTNode;
if(s==NULL)return 0;
s->data=x; s->lchild=NULL;s->rchils=NULL;
if(f==NULL)root=s;
else if(x<f->data)
f->lchild=s;
else f->rchild=s;
return 1;
}
11、后序遍历求二叉树的高度，并判断二叉树是否平衡
int HeightBalance(BiTNode *t ,int & height){
if(t != NULL)
{
int lh,rh;
if(!heightBalance(t->lchild,lh))
return 0;
if(!heightBalance(t->rchild,rh))
return 0;
height=(lh>rh)?1+lh:1+rh;
if(lh-rh)<=1 &&lh-rh>=-1)
return 1;
else return 0;
}
else(height=0;return 1;)
}
12、前遍历的非递归算法
void PreOrder(BITNode *t){
while(t!=NULL){
printf("%d",p->data);
PreOrder(t->lchild);
t=t->rchild;
}
}
void PreOrder(BITNode *t){
BITNode *p;
BiTNode *S[n];top=0;
S[top]=t;
while(top !=1)
{
p=S[top];
top--;
printf("%d",p->data);
if(p->lchild!=NULL)
{
S[++top]=p->lchild;
}
if(p->rchild!=NULL)
{
S[++top]=p->rchild;
}
}
}
13、求一颗二叉树中叶子结点的值及所在层次
void leave(BiTree &T,BiTNode *leaf[],int lev[],int&num){
BiTNode *p=T;
num=0;
if(p!=NULL)
{
int front=0,rear=0,last=1,level=1;
BiTNode *Q[n];
rear++;
Q[rear]=p;
while(front !=rear){
front=(front+1)%n;
p=Q[front];
}
if(p->lchild==NULL && p->rchild==NULL)
{
leaf[num]=p;
lev[num]=level;
num++;
}
if(p->lchild!=NULL)
{
rear=(rear+1)%n;
Q[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
rear=(rear+1)%n;
Q[rear]=p->rchild;
}
if(front==last){
last=rear;
level++;
}
}
}
14、计算二叉树各层结点个数。并返回二叉树的宽度
int Level_Nodes(BiTree& T,int count[],int& level){
BiTNode *p=T;
if(p!=NULL)
{
level=0;
int front=0,rear=0,last=1,num=0,max=0;
BiTNode *Q[n];
rear++;
Q[rear]=p;
while(front !=rear){
front=(front+1)%n;
p=Q[front];
num++;
if(p->lchild!=NULL)
{
rear=(rear+1)%n;
Q[rear]=p->lchild;
}
if(p->rchild!=NULL)
{
rear=(rear+1)%n;
Q[rear]=p->rchild;
}
if(front==last){
last=rear;
count[level++]=num;
num=0;
}
}
for(num=0;num<level;num++)
if(count[num]>max)
max=count[num];
return max;
}
return 0;
}
15、判断二叉树是否是完全二叉树
int isComplete_BinTree(BiTree & T){
BiTNOde *p=T;
if(p==NULL)
return 1;
BiTNode *[Q];
int front=0,rear=0;
int flag=0;
Q[rear]=p;
rear=(rear+1)%n;
while(front !=rear){
p=Q[front];
front=(front+1)%n;
if(p==NULL)
flag=1;
else if(flag)
return 0;
else{
Q[rear]=p->lchild;
rear=(rear+1)%n;
Q[rear]=p->rchild;
rear=(rear+1)%n;
}
}
return 1;
}
16、构造一棵二叉排序树的非递归算法
void CSBT (BStree T, Elemtype A[],int n)
{
for(i=1; i<=n; i++)
{
p=T;
f=NULL；
while（p！=NULL）
if(p->data <A[i])
{
f=p;
p=p->rchild;
}
else if(p->data >A[i])
{
f=p;
p=p->lchild;
}
s=(BSTree)malloc(sizeof(BINode));
s->data=A[i];
s->lchild = NULL;
s->rchild = NULL;
if(f==NULL)
T=s;
else if(s->data < f->data)
f->lchild = s;
else
f->rchild = s;
}
}
17、返回二叉树中序遍历的第一个结点
typedef struct pp
{
int d;
srruct pp *l, *r;
}Btree;
Btree *inFirstNode(Btree *bt)
{
if(bt==NULL)
return;
p=bt;
while(p->l!= NULL)
p=p->l;
return p;
}
18、设计一个算法，求在前序序列中处于第k个位置的结点
typedef struct node *pointer;
struct node{
datatype data;
pointer Lchild,rchild;
}
typedef pointer bitreptr;
void pre(bitreptr t; int k; bitreptr p)
{
if(t!=NULL)
{
i=i+1;
if(i==k)
{
p=t;
return(p);
}
pre(t->lchild, k, p);
pre(t->rchild, k, p);
}
}
19、交换二叉树中所有结点左右子树的算法
typedef struct node
{
int data;
struct node *lchild,*rchild;
}bitree;
void swapbitree(bitree *bt)
{
bitree *p;
if(bt==0)
return;
swapbitree(bt->lchild);
swapbitree(bt->rchild);
p = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = p;
}
20、三种遍历形式
前序遍历
思路：访问根节点--->前序遍历左子树--->前序遍历右子树
void PreOrderTraverse(BinTree T)
{
if(T==NULL) return;
printf("%c ",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}
中序遍历
思路：中序遍历左子树--->访问根节点--->中序遍历右子树
void InOrderTraverse(BinTree T)
{
if(T==NULL) return;
InOrderTraverse(T->lchild); /* 中序遍历左子树 */
printf("%c ",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
InOrderTraverse(T->rchild); /* 最后中序遍历右子树 */
}
后序遍历
思路：后序遍历左子树--->后序遍历右子树--->访问根节点
void PostOrderTraverse(BinTree T)
{
if(T==NULL) return;
PostOrderTraverse(T->lchild); /* 先后序遍历左子树 */
PostOrderTraverse(T->rchild); /* 再后序遍历右子树 */
printf("%c ",T->data); /* 显示结点数据，可以更改为其它对结点操作 */
}
21、二叉树的递归遍历转变成非递归遍历
#include"stack.h"
void InOrder(Bitree T){
stack S;
initStack(S);
BiTNode *p=T;
do{
while(p!=NULL){
Push(S,p);
p=p->lchild;
}
if(!IsEmpty(S)){
Pop(S,p);
count<<p->data<<endl;
p=p->rchild;
}
}while(p!=NULL || !IsEmpty(S));
};
22、层次序遍历
#include "queue.h"
void levelOrder(Bitree T){
BiTNode *p;
Queue Q;
initQueue(Q);
enQueue(Q,T);
while(!IsEmpty(Q)){
deQueue(Q,p);
cout<<p->data<<endl;
if(p->lchild= NULL)
enQueue(Q,p->lchild);
if(p->rchild= NULL)
enQueue(Q,p->rchild);
}
}
23、求指定结点的父结点
BiTNode * Parent(BiTNode * t, BITNode *p)
{
if(t == NULL)
return NULL;
if(t->lchild == p || t->rchild == p)
return t; //找到，返回父结点 *t
BiTNode * p = Parent(t->lchild,p); //递归在左子树中查找
if(p != NULL)
return p;
else return Parent(t->rchild,p); //递归在右子树中查找
}
24、统计二叉树中度为1的结点个数
int Degrees_1(BiTNode *t)
{
if(t == NULL)
return 0;
if(t->lchild != NULL && t->rchild == NULL || t->lchild == NULL && t->rchild != NULL)
return 1+Degrees_1(t->lchild)+Degrees_1(t->rchild);
else return Degrees_1(t->lchild)+Degrees_1(t->rchild);
};
25、统计二叉树中度为2的结点个数
int Degrees_2(BiTNode *t)
{
if(t == NULL)
return 0;
if(t->lchild != NULL && t->rchild != NULL )
return 1+Degrees_2(t->lchild)+Degrees_2(t->rchild);
else return Degrees_2(t->lchild)+Degrees_2(t->rchild);
};
26、统计二叉树中度为0的结点个数
int leaves(BiTNode *t)
{
if(t == NULL)
return 0;
if(t->lchild == NULL && t->rchild == NULL)
return 1;
return leaves(t->lchild)+leaves(t->rchild);
};
int NumofLeaf(*t)
{
if(t==NULL)
return 0;
if(!t->lchild && !t->rchild)
{ return 1;
d1=NumofLeaf(t->lchild);
d2=NumofLeaf(t->rchild)
}
return(d1+d2);
}
27、计算二叉树中指定结点*p所在层次
int level(BiTNode * t ,BiTNode * p,int d)
{
if(t == NULL)
return 0;
if(t == p)
return d;
int SubTreeLevel;
if(SubTreeLevel = level(t->lchild, p, d+1) > 0)
return SubTreeLevel;
else return level(t->rchild, p, d+1);
}
28、从二叉树中删除所有的叶子结点
void defoliate(BiTNode *& t)
{
if(t == NULL)
return ;
if(t->lchild == NULL && t->rchild == NULL)
{
delete t;
t = NULL;
}
else
{
defoliate(t->lchild);
defoliate(t->rchild);
}
}
29、计算二叉树中各结点中的最大元素的值
void maxValue(BITNode * t, DataType & max)
{
if(t != NULL)
{
if(t->data > max)
max = t->data;
maxValue(t->lchild,max);
maxValue(t->rchild,max);
}
}
30、求前序中第k个结点
BiTNode *Pre_Search_k(BiTNode *t, int &count, int k)
{
if(t != NULL){
count++;
if(count == k)
return t;
BiTNode *p;
if((p = Pre_Search_k(t->lchild, count, k)) != NULL)
return p;
return Pre_Search_k(t->rchild, count, k)
}
return NULL;
}
31、编写二叉树中查找值为x的结点
int Find_Print(BiTNode *t,DataType x, DataType path[],int level, int & count){
if(t != NULL){
path[level-1] = t->data;
if(t->data == x)
{count=level; return 1;}
if(Find_Print(t->lchild, x, path, level+1，count))
return 1;
return Find_Print(t->rchild, x, path, level+1，count);
}
else return 0;
}
32、构造二叉树
前序与中序构造二叉树
void createBinTree(BiTNode *&t, Datatype pre[], DataType in[], int s1,int t1,int s2, int t2){
int i;
if(s1<=t1)
{
t=(*BITNode) malloc(sizeof(BiTNode));
t->data=pre[s1];t->lchild=t->rchild=NULL;
for(i=s2; i<=t2; i++)
if(in[i]==pre[s1])
break;
createBinTree(t->lchild, pre, in, s1+1,s1+i-s2,s2,i-1);
createBinTree(t->lchild, pre, in, s1+i-s2+1,t1,i+1,t2);
}
}
}
后序与中序构造二叉树
void createBinTree(BiTNode *&t, Datatype post[], DataType in[], int s1,int t1,int s2, int t2){
if(s1<=t1)
{
t=(*BITNode) malloc(sizeof(BiTNode));
t->data=post[s1];t->lchild=t->rchild=NULL;
int i;
for(i=s2; i<=t2; i++)
if(in[i]==post[t1])
break;
createBinTree(t->lchild, post, in, s1+i-s2,t1-1,i+1,t2);
createBinTree(t->lchild, post, in, s1,s1+i-s2-1,s2,i-1);
}
33、建立二叉树的二叉链表表示
void ConstructTree(Datatype T[], int n, int i,BiTNode *&ptr)
{
if（i>=n）
ptr=NULL;
else{
ptr=(BiTNode *)malloc(sizeof(BiTNode));
ptr->data=T[i];
ConstructTree(T,n,2*i+1,ptr->lchild);
ConstructTree(T,n,2*i+1,ptr->rchild);
}
}
34、完全二叉树转换成二叉树的顺序表示
void LinkList_to_Array(BiTNode *t, Datatype A[], int n, inti){
if(t==NULL)
return;
if(i>=n)
{
printf("数组空间不足");
exit(1);
}
A[i]=t;
LinkList_to_Array(t->lchild,A,n,2*i+1);
LinkList_to_Array(t->rchild,A,n,2*i+2);
}
35、输出所有节点的数值以及所在层次
void nodePrint(BiTnode *t, int i)
{
if(t != NULL)
{
cout<<t->data<<","<<i<<end1=l;
nodePrint(t->lchild,i+1);
nodePrint(t->rchild,i+1);
}
}
36、写一个算法，统计出T所指向的二叉树的结点总数和叶子结点
void BiTreeNode(BTNode *T ,int &all, int &leaf)
{
if（T！= NULL）
{
BiTreeNode(T->lchild, all ,leaf);
all++;
if(T->lchild == NULL && T->rchild == NULL)
leaf++;
BiTreeNode(T->rchild,all,leaf);
}
}
37、求二叉树的高度
int depth(Bitree *t)
{
if（t==NULL）
return 0;
else{
hl=depth(t->lchild);
hr=depth(t->rchild);
if(hl>hr)
return hl+1;
else
return hr+1;
}
}
38、求一棵二叉树中结点总数的算法
int NumofAll（Bitree *BT）
{
if(BT == NUll)
return 0;
else
return NumofAll(BT->lchild)+NumofAll(BT->rchild)+1;
}