建立二叉树
首先先明确节点结构：
struct node{
int data;
node* lchild;
node* rchild;
};
当前二叉树的后序序列区间为[postL,postR],中序序列区间为[inL,inR]:
node* create(int postL,int postR,int inL,int inR){
if(postL>postR){
return NULL; //若后序序列长度小于等于0，则直接返回
}
node* root=new node; //新建一个新的结点，用来存放当前二叉树的根节点
root->data=post[postR]; //新结点的数据域为根节点的值
int k;
for(k=inL;k<=inR;k++){
if(in[k]==post[postR]){ //在中序序列中找到in[k]==pre[L]的结点
break;
}
}
int numLeft=k-inL; //左子树结点数
//返回左子树的根结点地址，赋值给root的左指针
root->lchild=create(postL,postL+numLeft-1,inL,k-1);
//返回右子树的根结点地址，赋值给root的右指针
root->rchild=create(postL+numLeft,postR-1,k+1,inR);
}
当前二叉树的先序序列区间为[preL,preR],中序序列区间为[inL,inR]:
node* create (int preL,int preR,int inL,int inR){
if(preL>preR){
return NULL; //若先序序列长度小于等于0，则直接返回
}
node* root=new node; //新建一个新的结点，用来存放当前二叉树的根结点
root->data=pre[preL]; //新结点的数据与未根结点的值
int k;
for(k=inL;k<=inR;k++){
if(in[k]==pre[preL]){ //在中序序列中找到in[k]==pre[L]的结点
break;
}
}
int numLeft=k-inL; //左子树的结点数
//返回左子树的根结点地址，赋值给root的左指针
root->lchild=create(preL+1,preL+numLeft,inL,k-1);
//返回右子树的根结点地址，赋值给root的右指针
root->rchild=create(preL+numLeft+1,preR,k+1,inR);
return root;
}
仅靠先序序列和后序序列是无法确定唯一的二叉树的
遍历二叉树
根据之前建立的二叉树，我们可以进行遍历
先序遍历：
void preorder(node* root){
if(root==NULL){
return;
}
printf("%d ",root->data);
preorder(root->lchild);
preorder(root->rchild);
}
如果二叉树以数组的方式存储：
void preorder(int root){
printf("%d",number[root]);
preorder(root*2);
preorder(root*2+1);
}
非递归实现：
//非递归前序遍历
void preorderTraversal(node*root){
stack<node*> s;
node*cur = root;
while(cur != NULL || !s.empty()){
while(cur != NULL){
cout<<cur ->val<<" ";
s.push(cur );
cur = cur ->left;
}
if(!s.empty()){
cur = s.top();
s.pop();
cur = cur ->right;
}
}
}
中序遍历：
void inorder(node* root){
if(root==NULL){
return;
}
inorder(root->lchild);
printf("%d ",root->data);
inorder(root->rchild);
}
如果二叉树以数组的方式存储：
void inOrder(int root){
inOrder(root*2);
printf("%d",number[root]);
inOrder(root*2+1);
}
非递归实现：
//非递归中序遍历
void inorderTraversal(node*root)
{
stack<node*> s;
node*cur = root;
while(cur != NULL || !s.empty()){
while(cur != NULL){
s.push(cur );
cur = cur ->left;
}
if(!s.empty()){
cur = s.top();
cout<<cur ->val<<" ";
s.pop();
cur = cur ->right;
}
}
}
后序遍历：
void postorder(node* root){
if(root==NULL){
return;
}
postorder(root->lchild);
postorder(root->rchild);
printf("%d ",root->data);
}
如果二叉树以数组的方式存储：
void postOrder(int root){
postOrder(root*2);
postOrder(root*2+1);
printf("%d",number[root]);
}
非递归实现:
vector<int> postorderTraversal(node*root) {
stack<node*> s;
node*cur = root;
node*last = NULL; // 上一个被完整后序遍历过的树的根结点
vector<int> v;
while (cur != NULL || !s.empty()) {
while (cur != NULL) {
s.push(cur);
cur = cur->lchild;
}
node*top = s.top();
if (top->rchild == NULL||top->rchild== last) {
cout<<top->data<<" ";
s.pop();
last = top;
} else {
cur = top->rchild;
}
}
return v;
}
层序遍历/广度优先遍历:
void BFS(node* root){
queue<node*> q;
q.push(root);
while(!q.empty()){
node* now=q.front();
q.pop();
printf("%d ",now->data);
if(now->lchild!=NULL)
q.push(now->lchild);
if(now->rchild!=NULL)
q.push(now->rchild);
}
}
平衡：
重新设置一下结点的结构：
struct node{
int v,height;
node *lchild,*rchild;
}*root;
如果一个结点的左右孩子高度差的绝对值大于1，那么可以说这个地方不平衡，故我们在建立AVL的时候应该在插入时就进行处理高度差问题.
首先我们要解决的一个问题，那就是每个数据读入之后，如何在树中创建一个新结点；
生成新结点的函数：
node* newNode(int v){
node* Node=new node; //申请一个node型变量的地址空间
Node->v=v; //结点权值为v
Node->height=1; //结点的初始高度设置为1
Node->lchild=Node->rchild=NULL; //初始设定没有左右孩子
return Node; //返回新建结点的地址
}
在判断高度差的问题上，我们先明确两点:
一个确认当前结点高度差的问题上，我们按照左子树高度减掉右子树高度的，
还有一个就是每次在添加结点的过程中在添加完孩子之后，父结点的高度就应该+1，例如孩子是默认高度1，那父结点就该变成2.
不过，先写出获取高度的函数以便我们上述想法的实现。
获取以root为根节点的字数的当前的height:
int getHeight(node* root){
if(root==NULL) return 0; //空结点要设置为0
return root->height;
}
更新结点root的height：
void updateHeight(node* root){
//取左右孩子中最大的高度+1
root->height=max(getHeight(root->lchild),getHeight(root->rchild))+1;
}
计算结点root的平衡因子：
int getBalanceFactor(node* root){
//左子树高度减掉右子树高度
return getHeight(root->lchild)-getHeight(root->rchild);
}
如果判断出不平衡的地方，也就是我们的getBalanceFactor()返回的值的绝对值大于1，我们进入正题，平衡的方式有两种：左旋和右旋
左旋:
void L(node* &root){
node* temp=root->rchild; //root指向结点A,temp指向结点B
root->rchild=temp->lchild;
temp->lchild=root;
updateHeight(root); //更新结点A的高度
updateHeight(temp); //更新结点B的高度
root=temp;
}
右旋：
void R(node* &root){
node* temp=root->lchild; //root指向结点B,temp指向结点A
root->lchild=temp->rchild;
temp->rchild=root;
updateHeight(root); //更新结点B的高度
updateHeight(temp); //更新结点A的高度
root=temp;
}
我们要处理的返回值如果是2，那么我们看它左子树的返回值，如果是1那就是LL型，-1那就是LR型；
我们要处理的返回值如果是-2，那么我们看它右子树的返回值，如果是-1那就是RR型，1那就是RL型；
LL型：右旋父结点一次
LR型：左旋左子树一次，右旋父结点一次
RR型：左旋父结点一次
RL型：右旋右子树一次，左旋父结点一次
插入权值为v的结点：
void insert(node* &root,int v){
if(root==NULL){ //到达空结点
root==newNode(v);
return;
}
//根据权值去判断往哪个子树插
if(v < root->v){ //v比根结点权值小
insert(root->lchild,v); //往左子树插入
updateHeight(root); //更新树高
if(getBalanceFactor(root)==2){
if(getBalanceFactor(root->lchild)==1){ //LL型
R(root);
}else if(getBalanceFactor(root->lchild)==-1){ //LR型
L(root->lchild);
R(root);
}
}
}else{ //v比根结点权值大
insert(root->rchild,v); //往右子树插入
updateHeight(root); //更新树高
if(getBalanceFactor(root)==-2){
if(getBalanceFactor(root->rchild)==-1){ //RR型
L(root);
}else if(getBalanceFactor(root->rchild)==1){ //RL型
R(root->rchild);
L(root);
}
}
}
}
网友评论