3. 平衡二叉树

梦里梦外; 2022-04-02 08:44 112阅读 0赞

程序输入一个字符串（只包含小写字母），请按照字符的输入顺序建立平衡二叉排序树，并分别输出二叉树的先序序列、中序序列和后序序列，最后输出该二叉树向左旋转 90 度后的结构。

例如：向左旋转 90 度后，以每层向里缩进 4 个空格的方式输出，输出结果为：

i  
g  
f  
a  
d  
c  
b

**输入：agxnzyimk**

输出：  
Preorder: xigamknzy  
Inorder: agikmnxyz  
Postorder: agknmiyzx  
Tree:  
z  
y  
x  
n  
m  
k  
i  
g  
a

<table> 
 <thead> 
  <tr> 
   <th>&nbsp;</th> 
   <th>测试输入<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=input&amp;lang=zh_cn" rel="nofollow"><img alt="关于“测试输入”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>期待的输出<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=expectedoutput&amp;lang=zh_cn" rel="nofollow"><img alt="关于“期待的输出”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>时间限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=timelimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“时间限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>内存限制<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=memlimit&amp;lang=zh_cn" rel="nofollow"><img alt="关于“内存限制”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
   <th>额外进程<a href="http://online.bit.edu.cn/moodle/help.php?component=programming&amp;identifier=nproc&amp;lang=zh_cn" rel="nofollow"><img alt="关于“{$a} 个额外进程”的帮助" src="http://online.bit.edu.cn/moodle/theme/image.php/lambda/core/1539000325/help"></a></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>测试用例 1</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77939&amp;test=100772&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>agxnzyimk↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77939&amp;test=100772&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>Preorder:&nbsp;xigamknzy↵</li> 
     <li>Inorder:&nbsp;agikmnxyz↵</li> 
     <li>Postorder:&nbsp;agknmiyzx↵</li> 
     <li>Tree:↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;z↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;y↵</li> 
     <li>x↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;n↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;m↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;i↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;g↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>测试用例 2</td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77939&amp;test=100773&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>asdfghjkl↵</li> 
    </ol></td> 
   <td><a href="http://online.bit.edu.cn/moodle/mod/programming/testcase/download_io.php?id=77939&amp;test=100773&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
    <ol> 
     <li>Preorder:&nbsp;gdafjhlks↵</li> 
     <li>Inorder:&nbsp;adfghjkls↵</li> 
     <li>Postorder:&nbsp;afdhksljg↵</li> 
     <li>Tree:↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;s↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;l↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;k↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;j↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;h↵</li> 
     <li>g↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;d↵</li> 
     <li>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a↵</li> 
    </ol></td> 
   <td>1秒</td> 
   <td>64M</td> 
   <td>0</td> 
  </tr> 
 </tbody> 
</table>

#include "stdio.h"
    #include "stdlib.h"
    typedef struct Avnode
    {
        char data;
        struct Avnode * lchild, *rchild;
    }NODE;
    NODE *root = NULL;
    
    int Height(NODE*p){
        if(p == NULL) return 0;
        else{
            if(Height(p->lchild) > Height(p->rchild))   return Height(p->lchild)+1;
            else return Height(p->rchild)+1;
        }
    }
    
    NODE* LL(NODE *p){
        NODE *q;
        q = p->lchild;
        p->lchild = q->rchild;
        q->rchild = p;
        return q;
    }
    
    NODE* RR(NODE *p){
        NODE *q = p->rchild;
        p->rchild = q->lchild;
        q->lchild = p;
        return q;
    }
    
    NODE* LR(NODE *p){
        NODE *q = p->lchild, *q1 = q->rchild;
        q->rchild = q1->lchild;
        p->lchild = q1;
        q1->lchild = q;
        p->lchild = q1->rchild;
        q1->rchild = p;
        return q1;
    }
    
    NODE* RL(NODE *p){
        NODE *q = p->rchild, *q1 = p->rchild->lchild;
        q->lchild = q1->rchild;
        p->rchild = q1;
        q1->rchild = q;
        p->rchild = q1->lchild;
        q1->lchild = p;
        return q1;
    }
    
    NODE* Insert(char c, NODE *p){
        if(p == NULL){
            p = (NODE*)malloc(sizeof(NODE));
            p->data = c;
            p->lchild = NULL;
            p->rchild = NULL;
            return p;
        }
        else{
            if(c < p->data){
                p->lchild = Insert(c, p->lchild);
                if(Height(p->lchild) - Height(p->rchild) > 1){
                    if(c < p->lchild->data){
                        p = LL(p);
                    }
                    else{
                        p = LR(p);
                    }
                }
                return p;
            }
            else{
                p->rchild = Insert(c, p->rchild);
                if(Height(p->lchild) - Height(p->rchild) < -1){
                    if(c > p->rchild->data){
                        p = RR(p);
                    }
                    else{
                        p = RL(p);
                    }
                }
                return p;
            }
        }
    }
    
    void Inorder(NODE *head)
    {
        if (head->lchild)
            Inorder(head->lchild);
        printf("%c", head->data);
        if (head->rchild)
            Inorder(head->rchild);
    }
    
    
    void Preorder(NODE *head)
    {
        printf("%c", head->data);
        if (head->lchild)
            Preorder(head->lchild);
        if (head->rchild)
            Preorder(head->rchild);
    }
    void Postorder(NODE *head)
    {
        if (head->lchild)
            Postorder(head->lchild);
        if (head->rchild)
            Postorder(head->rchild);
        printf("%c", head->data);
    }
    
    
    void Print(NODE *p, int depth){
        int i;
        if (p->rchild)
            Print(p->rchild, depth + 1);
        for (i = 0; i < depth; i++)
            printf("    ");
        printf("%c\n", p->data);
        if (p->lchild)
            Print(p->lchild, depth + 1);
    }
    
    int main()
    {
        char c;
        while (1)
        {
            c = getchar();
            if (c == '\n')
                break;
            root = Insert(c, root);
        }
        
        printf("Preorder: ");
        Preorder(root);
        putchar('\n');
        printf("Inorder: ");
        Inorder(root);
        putchar('\n');
        printf("Postorder: ");
        Postorder(root);
        putchar('\n');
        printf("Tree:\n");
        Print(root, 0);
        return 0;
    }