VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 1174|回复: 1

[求助] 能否将某一个右斜二叉树的子树进行左旋,然后再遍历整个二叉树?

[复制链接]
11_avatar_middle
在线会员 发表于 2015-8-31 18:18:50 | 显示全部楼层 |阅读模式
3驿站币
如题,能否将某一个右斜二叉树的子树进行左旋,然后再遍历整个二叉树?
比如,我们先构造一颗右斜二叉排序树,1 2 3 4 5 6 7 8。先序遍历得到1 2 3 4 5 6 7 8
我们对结点6这棵子树进行左旋转,然后对整个二叉树进行先序遍历,输出1 2 3 4 5 7 6 8,
请问能否实现? 个人设计的代码如下,但无法实现。  

#include "stdafx.h"
#include <iostream>
using namespace std;

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;//函数类型

typedef struct BiTNode{//二叉树的二叉链表节点结构定义
        int data;
        struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;


/* 递归查找二叉排序树T中是否存在key, */
/* 指针f指向T的双亲,其初始调用值为NULL */
/* 若查找成功,则指针p指向该数据元素结点,并返回TRUE */
/* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */

Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
        if (!T)        /*  查找不成功 */
        {
                *p = f;
                return FALSE;
        }
        else if (key == T->data) /*  查找成功 */
        {
                *p = T;
                return TRUE;
        }
        else if (key<T->data)
                return SearchBST(T->lchild, key, T, p);  /*  在左子树中继续查找 */
        else
                return SearchBST(T->rchild, key, T, p);  /*  在右子树中继续查找 */
}


/*  当二叉排序树T中不存在关键字等于key的数据元素时, */
/*  插入key并返回TRUE,否则返回FALSE */
Status InsertBST(BiTree *T, int key)
{
        BiTree p, s;
        if (!SearchBST(*T, key, NULL, &p)) /* 查找不成功 */
        {
                s = (BiTree)malloc(sizeof(BiTNode));
                s->data = key;
                s->lchild = s->rchild = NULL;
                if (!p)
                        *T = s;                        /*  插入s为新的根结点 */
                else if (key<p->data)
                        p->lchild = s;        /*  插入s为左孩子 */
                else
                        p->rchild = s;  /*  插入s为右孩子 */
                return TRUE;
        }
        else
                return FALSE;  /*  树中已有关键字相同的结点,不再插入 */
}
void PreOrderTraverse(BiTree T)
{
        if (T == NULL)
                return;
        cout << T->data << " ";/* 显示结点数据,可以更改为其它对结点操作 */
        PreOrderTraverse(T->lchild); /* 再先序遍历左子树 */
        PreOrderTraverse(T->rchild); /* 最后先序遍历右子树 */
}

void L_Rotate(BiTree *P)
{
        BiTree S, R;
        S = *P;
        for (int i = 1; i < 6; i++){
                *P = (*P)->rchild;
        }
        R = (*P)->rchild; /*  R指向P的右子树根结点 */
        (*P)->rchild = R->lchild; /* R的左子树挂接为P的右子树 */
        R->lchild = (*P);
        *P = S;
}

int main()
{
        int x;
        BiTree T;
        T = NULL;
        int a[] = {1,2,3,4,5,6,7,8};
        for (int i = 0; i != 8; i++){
                InsertBST(&T, a[i]);
        }
        PreOrderTraverse(T);
        cout << endl;
        L_Rotate(&T);
        PreOrderTraverse(T);
        system("pause");
        return 0;
}
请问如何才能实现预想的结果?谢谢( L_Rotate和main这两个函数自己改编的,其他函数都是教材上的)





上一篇:LNK2019: 无法解析的外部符号
下一篇:多程序写一个文件
81_avatar_middle
online_moderator 发表于 2015-8-31 21:51:23 | 显示全部楼层
类似这样的题我的建议是在纸上画一画,本身结点不多,一步步跟下来肯定能解决问题的,楼主不妨试试
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号tongdun|网站地图wx_jqr

GMT+8, 2019-5-21 09:41

Powered by Discuz! X3.4

© 2009-2019 cctry.com

快速回复 返回顶部 返回列表