hdu3999-The order of a Tree (二叉树的先序遍历)
2023-09-27 14:24:37 时间
http://acm.hdu.edu.cn/showproblem.php?pid=3999
The order of a Tree
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1361 Accepted Submission(s): 695
Problem Description
As we know,the shape of a binary search tree is greatly related to the order of keys we insert. To be precisely:
1. insert a key k to a empty tree, then the tree become a tree with
only one node;
2. insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.
1. insert a key k to a empty tree, then the tree become a tree with
only one node;
2. insert a key k to a nonempty tree, if k is less than the root ,insert
it to the left sub-tree;else insert k to the right sub-tree.
We call the order of keys we insert “the order of a tree”,your task is,given a oder of a tree, find the order of a tree with the least lexicographic order that generate the same tree.Two trees are the same if and only if they have the same shape.
Input
There are multiple test cases in an input file. The first line of each testcase is an integer n(n <= 100,000),represent the number of nodes.The second line has n intergers,k1 to kn,represent the order of a tree.To make if more simple, k1 to kn is a sequence of 1 to n.
Output
One line with n intergers, which are the order of a tree that generate the same tree with the least lexicographic.
Sample Input
4
1 3 4 2
Sample Output
1 3 2 4
题解:题目意思即,给你一个插入数列,形成一棵二叉树,你给出字典序最小的插入方法建相同的一棵树出来。说白了,就是求先序序列。
代码:
1 #include <fstream> 2 #include <iostream> 3 4 using namespace std; 5 6 typedef struct Node{ 7 Node *lch,*rch,*nex; 8 int x; 9 Node(int x){ 10 this->x=x; 11 lch=NULL; 12 rch=NULL; 13 } 14 }inode; 15 16 int n,tn; 17 inode *head; 18 19 void insert(int t); 20 void preOrder(inode *p); 21 22 int main() 23 { 24 //freopen("D:\\input.in","r",stdin); 25 //freopen("D:\\output.out","w",stdout); 26 int t; 27 while(~scanf("%d",&n)){ 28 scanf("%d",&t); 29 head=new inode(t); 30 for(int i=1;i<n;i++){ 31 scanf("%d",&t); 32 insert(t); 33 } 34 tn=0; 35 preOrder(head); 36 } 37 return 0; 38 } 39 void insert(int t){ 40 inode *p=head,*s=new inode(t); 41 while(p!=NULL){ 42 if(t<p->x) 43 if(p->lch!=NULL) p=p->lch; 44 else{ 45 p->lch=s; 46 break; 47 } 48 else 49 if(p->rch!=NULL) p=p->rch; 50 else{ 51 p->rch=s; 52 break; 53 } 54 } 55 } 56 void preOrder(inode *p){ 57 if(p!=NULL){ 58 printf("%d",p->x); 59 if(++tn<n) printf(" "); 60 else printf("\n"); 61 preOrder(p->lch); 62 preOrder(p->rch); 63 delete p; 64 } 65 }
相关文章
- Java实现二叉树及相关遍历方式
- 【华为OD机试真题 python】 二叉树中序遍历【2022 Q4 | 200分】
- 【算法】【链表模块】二叉树空间复杂度为O(1)的遍历方法(Morris算法)
- 剑指offer 面试题6:重建二叉树
- Morris遍历判断二叉树是否为搜索二叉树
- 判断二叉树是否为满二叉树
- 【Leetcode】110. 平衡二叉树(简单)
- 二叉树的层序遍历-Python
- 二叉树的深度优先遍历和广度优先遍历-Python
- 数据结构 有序树转二叉树 (树的遍历)
- C 二叉树模板及笔记
- 剑指offer解法汇总82-二叉树中和为某一值的路径(一)
- 剑指offer编程题解法汇总18-二叉树的镜像
- LeetCode 103. 二叉树的锯齿形层序遍历
- LeetCode103二叉树的锯齿形层次遍历(相关话题:二叉树、层次遍历)
- 98、【树与二叉树】leetcode ——112. 路径总和:5行精简代码回溯法[带剪枝]+迭代法(C++版本)
- 90、【树与二叉树】leetcode ——104. 二叉树的最大深度:层次遍历+DFS+子问题分解(C++版本)
- JLOI 2009 二叉树问题
- 二叉树的几种遍历方法
- LintCode 二叉树的遍历 (非递归)
- 【leetcode】103:二叉树的锯齿形层序遍历
- 【Leetcode】105: 从前序与中序遍历序列构造二叉树
- [LeetCode] 1028. Recover a Tree From Preorder Traversal 从先序遍历还原二叉树
- [LeetCode] 314. Binary Tree Vertical Order Traversal 二叉树的竖直遍历
- [LeetCode] Verify Preorder Serialization of a Binary Tree 验证二叉树的先序序列化
- [LeetCode] 106. Construct Binary Tree from Inorder and Postorder Traversal 由中序和后序遍历建立二叉树
- [LeetCode] 107. Binary Tree Level Order Traversal II 二叉树层序遍历之二
- 数据结构 树、二叉树、查找算法总结
- 已知二叉树前序和中序,求后序
- 二叉树遍历算法的非递归实现