洛谷——P2171 Hz吐泡泡

2023-10-28 21:10

文章标签 洛谷泡泡 hz p2171

本文主要是介绍洛谷——P2171 Hz吐泡泡，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P2171 Hz吐泡泡

题目描述

这天，Hz大大心血来潮，吐了n个不同的泡泡玩（保证没有重复的泡泡）。因为他还要写作业，所以他请你帮他把这些泡泡排序成树（左子树<=根<右子树）。输出它的后序遍历。

BST插入操作模板

BST学习

#include<iostream>
#include<cstdio>
#include<cstring>using namespace std;
typedef struct node;
typedef node *tree;
struct node{int x,dep;tree lc,rc;
}*tr;int maxdep;
void insert(tree& bt,int n,int deep){if(bt){if(n<=bt->x) insert(bt->lc,n,deep+1);else insert(bt->rc,n,deep+1);}else{bt=new node;bt->x=n;bt->dep=deep;bt->lc=bt->rc=NULL;maxdep=max(maxdep,deep);}
}
int n;
void cou(tree bt){if(bt){cou(bt->lc);cou(bt->rc);printf("%d\n",bt->x);}
}
int main()
{scanf("%d",&n);for(int x,i=1;i<=n;i++){scanf("%d",&x);insert(tr,x,1);}printf("deep=%d\n",maxdep);cou(tr);return 0;
}

递归版的BST操作总结

void preorder(tree bt) { //先序遍历根结点为bt的二叉树的递归算法if(bt) {cout << bt->data;preorder(bt->lchild);preorder(bt->rchild);}
}

先序遍历

void inorder(tree bt)  //中序遍历根结点为bt的二叉树的递归算法
{if(bt){inorder(bt->lchild);cout << bt->data;inorder(bt->rchild);    　　　}    　　　
}

中序遍历

void postorder(tree bt) { //后序遍历根结点为bt的二叉树的递归算法if(bt) {postorder(bt->lchild);postorder(bt->rchild);cout << bt->data;}
}

后序遍历

void pre_crt(tree &bt) { //按先序次序输入二叉树中结点的值，生成char ch;ch = getchar();  //二叉树的单链表存储结构，bt为指向根结点的指针,'$'表示空树if(ch != '$') {bt = new node;      //建根结点bt->data = ch;pre_crt(bt->lchild);  //建左子树pre_crt(bt->rchild);  //建右子树} else bt = NULL;
}

1.建立二叉树

void dis(tree &bt) {         //删除二叉树if(bt) {dis(bt->lchild);     //删左子树dis(bt->rchild);     //删右子树delete bt;          //释放父结点
    }
}

2.删除二叉树

void insert(tree &bt, int n) {  //插入一个结点到排序二叉树中if(bt) {if(n < bt->data) insert(bt->lchild, n);else if(n > bt->data) insert(bt->rchild, n);} else {bt = new node;      //新开一个空间bt->data = n;bt->lchild = bt->rchild = NULL;}
}

3.插入一个数到BST中

tree findn(tree bt, int n) { //在二叉树中查找一个数，找到返回该结点,否则返回NULL。if(bt) {if(n < bt->data) findn(bt->lchild, n);else if(n > bt->data) findn(bt->rchild, n);else return bt;} else return NULL;
}

4.在BST中查找一个数

void print(tree bt) {         //用嵌套括号表示法输出二叉树if(bt) {cout << bt->data;if(bt->lchild || bt->rchild) {cout << '(';print(bt->lchild);if(bt->rchild) cout << ',';print(bt->rchild);cout << ')';}}
}