网站如何做站内站,wordpress客户端连接,培训手机软件开发,医院风格 wordpress目录
二叉查找树的定义
二叉查找树的基本操作
查找
插入
建立
删除
二叉树查找树的性质 二叉查找树的定义
二叉查找树是一种特殊的二叉树#xff0c;又称为排序二叉树、二叉搜索树、二叉排序树。
二叉树的递归定义如下#xff1a;
#xff08;1#xff09;要么二…目录
二叉查找树的定义
二叉查找树的基本操作
查找
插入
建立
删除
二叉树查找树的性质 二叉查找树的定义
二叉查找树是一种特殊的二叉树又称为排序二叉树、二叉搜索树、二叉排序树。
二叉树的递归定义如下
1要么二叉查找树是一棵空树。
2要么二叉查找树由根节点、左子树、右子树组成其中左子树和右子树都是二叉查找树且左子树上所以结点的数据域均小于或等于根节点的数据域右子树上的所有结点的数据域均大于根节点的数据域。
二叉查找树的基本操作
查找
进行二叉树的查找操作时由于无法确定二叉树的具体特性因此只能对左右子树都进行递归遍历。但是二叉查找树的性质决定了可以只选择一棵子树进行遍历。因此查找将会是从根节点查找的一条路径故最坏时间复杂度是其中h是二叉查找树的高度。于是就可以得到查找操作的基本思路
1如果当前根节点root为空说明查找失败返回。
2如果需要查找的x等于当前根节点的数据域root-data查找成功访问。
3如果需要查找的x小于当前根节点的数据域root-data说明应该往左子树查找因此向root-lchild递归。
4如果需要查找的x大于当前结点的数据域root-data则应该往右子树查找因此向root-rchild递归。
void search(node* root,int x){if(rootNULL){printf(search failed\n);return;}if(xroot-data){printf(%d\n,root-data);}else if(xroot-data){search(root-lchild,x);}else{search(root-rchild,x);}
}
可以看到和普通二叉树的查找函数不同二叉查找树的查找在于对左右子树的选择递归。在普通二叉树中无法确定需要查找的值x到底是在左子树还是右子树但是在二叉查找树中就可以确定因为二叉查找树中的数据域顺序总是左子树根节点右子树。
插入
对一棵二叉查找树来说查找某个数据域的结点一定是沿着确定的路径进行的。因此当对某个需要查找的值在二叉查找树中查找成功说明结点已经存在。反之如果这个需要查找的值在二叉查找树中查找失败那么说明查找失败的地方一定是结点需要插入的地方。因此可以在上面查找操作的基础上在rootNULL时新建需要插入的点。
void insert(node* root,int x){if(rootNULL){rootnewNode[x];return;}if(xroot-data){return;}else if(xroot-data){insert(root-lchild,x);}else{insert(root-rchild,x);}
}
建立
node* Create(int data[],int n){node* rootNULL;for(int i0;in;i){insert(root,data[i]);}return root;
}
需要注意的是即使是一组相同的数字如果插入它们的顺序不同最后生成的二叉查找树也可能不同。
删除
把二叉查找树中比结点权值小的最大结点称为该结点的前驱而把比结点权值大的最小结点称为该结点的后继。显然结点的前驱是该结点左子树的最右结点也就是从左子树根节点开始不断沿着rchild往下直到rchild为NULL时的结点而结点的后继则是该结点右子树的最左节点也就是从右子树根节点开始不断沿着lchild往下直到lchild为NULL时的结点。下面两个函数用来寻找以root为根的树中最大或最小权值的结点用以辅助寻找结点的前驱和后继
//寻找以root为根结点的树中的最大权值结点
node* findMax(node* root){while(root-rchild!NULL){rootroot-rchild;}return root;
}
//寻找以root为根结点的树中的最小权值结点
node* findMin(node* root){while(root-lchild!NULL){rootroot-lchild;}return root;
}
删除操作的基本思路如下
1如果当前结点root为空说明不存在权值为给定权值x的结点直接返回。
2如果当前结点root的权值恰为给定的权值x说明找到了想要删除的结点此时进入删除处理。如果当前结点root不存在左右孩子说明是叶子节点直接删除。如果当前结点root存在左孩子那么在左子树中寻找结点前驱pre然后让前驱的数据覆盖root接着在左子树中删除结点pre。如果当前结点root存在右孩子那么在右子树中寻找结点后继next然后让next的数据覆盖root接着在右子树中删除结点next。
3如果当前结点root的权值大于给定权值的x则在左子树中递归删除权值为x的结点。
4如果当前结点root的权值小于给定权值的x则在右子树中递归删除权值为x的结点。
//寻找以root为根结点的树中的最大权值结点
node* findMax(node* root){while(root-rchild!NULL){rootroot-rchild;}return root;
}
//寻找以root为根结点的树中的最小权值结点
node* findMin(node* root){while(root-lchild!NULL){rootroot-lchild;}return root;
}
void deleteNode(node* root,int x){if(rootNULL){return;}if(root-datax){if(root-lchildNULLroot-rchildNULL){rootNULL;}else if(root-lchild!NULL){node* prefindMax(root-lchild);root-datapre-data;deleteNode(root-lchild,pre-data);}else{node* nextfindMin(root-rchild);root-datanext-data;deleteNode(root-rchild,next-data);}}else if(root-datax){deleteNode(root-lchild,x);}else{deleteNode(root-rchild,x);}
}
但是也要注意总是优先删除前驱或后继容易导致树的左右子树高度极度不平衡使得二叉查找树退化成一条链。解决这一问题的办法有两种一种是每次交替删除前驱或后继另一种是记录子树高度总是优先在高度较高的一棵子树里删除结点。
二叉树查找树的性质
二叉查找树一个实用的性质对二叉查找树进行中序遍历遍历的结果是有序的。
另外如果合理调整二叉查找树的形态使得树上的每个结点都尽量有两个子节点这样整个二叉查找树的高度就会很低也即树的高度大概在的级别。
例题
给出N个正整数来作为一棵二叉排序树的结点插入顺序问这串序列是否是该二叉排序树的先序序列或是该二叉排序树的镜像树的先序序列。所谓镜像树是指交换二叉树的所有结点的左右子树而形成的树也即左子树所有结点数据域大于或等于根节点而根节点数据域小于右子树所有结点的数据域。如果是则输出YES并输出对应的树的后序序列否则输出NO。
思路
通过给定的插入序列构建出二叉排序树。对镜像树的先序遍历只需要在原树的先序遍历时交换左右子树的访问顺序即可。
//镜像树先序遍历结果存放于vi
void preordermirror(node* root,vectorintvi){if(rootNULL){return;}vi.push_back(root-data);preordermirror(root-right,vi);preordermirror(root-left,vi);
}
注意点
使用vector来存放初始序列、先序序列、镜像树先序序列可以方便相互之间的比较。若使用数组则比较操作需要使用循环才能实现。
#includecstdio
#includevector
using namespace std;
struct node{int data;node* left,*right;
};
vectorint origin,pre,preM,post,postM;
void insert(node* root,int data){if(rootNULL){rootnew node;root-datadata;root-leftroot-rightNULL;return;}if(dataroot-data){insert(root-left,data);}else{insert(root-right,data);}
}
void preorder(node* root,vectorint vi){if(rootNULL){return;}vi.push_back(root-data);preorder(root-left,vi);preorder(root-right,vi);
}
void preordermirror(node* root,vectorint vi){if(rootNULL){return;}vi.push_back(root-data);preordermirror(root-right,vi);preordermirror(root-left,vi);
}
void postorder(node* root,vectorint vi){if(rootNULL){return;}postorder(root-left,vi);postorder(root-right,vi);vi.push_back(root-data);
}
void postordermirror(node* root,vectorint vi){if(rootNULL){return;}postordermirror(root-right,vi);postordermirror(root-left,vi);vi.push_back(root-data);
}
int main(){int n,data;node* rootNULL;scanf(%d,n);for(int i0;in;i){scanf(%d,data);origin.push_back(data);insert(root,data);}preorder(root,pre);preordermirror(root,preM);postorder(root,post);postordermirror(root,postM);if(originpre){printf(YES\n);for(int i0;ipost.size();i){printf(%d,post[i]);if(ipost.size()-1){printf( );}}}else if(originpreM){printf(YES\n);for(int i0;ipostM.size();i){printf(%d,postM[i]);if(ipostM.size()-1){printf( );}}}else{printf(NO\n);return 0;}
}
