目录
二，HDU1710(Binary Tree Traversals)
一，概述
时间急迫，希望能在半个月把各个算法入门了，在一个专题一个专题的搞，二叉树也搞几天了，感觉自己的基础知识是真的菜，不过这几天也是实实在在的让我进步不少。下面就是一些典型的二叉树经典例题和一些我整理出来的模板，仅供自己用，如有侵权，及时联系。
二，HDU1710(Binary Tree Traversals)
Problem Description
A binary tree is a finite set of vertices that is either empty or consists of a root r and two disjoint binary trees called the left and right subtrees. There are three most important ways in which the vertices of a binary tree can be systematically traversed or ordered. They are preorder, inorder and postorder. Let T be a binary tree with root r and subtrees T1,T2.
In a preorder traversal of the vertices of T, we visit the root r followed by visiting the vertices of T1 in preorder, then the vertices of T2 in preorder.
In an inorder traversal of the vertices of T, we visit the vertices of T1 in inorder, then the root r, followed by the vertices of T2 in inorder.
In a postorder traversal of the vertices of T, we visit the vertices of T1 in postorder, then the vertices of T2 in postorder and finally we visit r.
Now you are given the preorder sequence and inorder sequence of a certain binary tree. Try to find out its postorder sequence.
[align=center][img]http://dl.iteye.com/upload/attachment/565933/ed3a92cd-9b72-33e3-907b-8bbb9006527c.jpg[/img][/align]
Input
The input contains several test cases. The first line of each test case contains a single integer n (1<=n<=1000), the number of vertices of the binary tree. Followed by two lines, respectively indicating the preorder sequence and inorder sequence. You can assume they are always correspond to a exclusive binary tree.
Output
For each test case print a single line specifying the corresponding postorder sequence.
Sample Input
9
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
Sample Output
7 4 2 8 9 5 6 3 1
题意:就是根据二叉树的先序序列和中序序列求后序序列。
这题和二叉搜索树无关，不过也是一种题型。
**算法思路: 由于先序是 头左右 中序是左头右
**则先序中的第一个必定是root,在中序中找到root,则root把中序序列分为了左子树的中序序列和右子树的中序序列
**则根据跨度，也可以在先序序列中求出左右子树的先序序列
1 2 4 7 3 5 8 9 6
4 7 2 1 8 5 9 3 6
root 1
左子树的中序遍历:4 7 2
右子树的中序遍历:8 5 9 3 6
左子树的先序遍历:2 4 7
右子树的先序遍历:3 5 8 9 6
在依次递归左子树和右子树
#include <iostream>
using namespace std;
const int _N = 1010;
int preorder[_N], inorder[_N], n; //定义先序，中序
void dfs(int pre, int in, int size, bool flag)
{
int i;
if(size <= 0)
return;
for(i = 0; preorder[pre] != inorder[in + i]; i++); //查找根出现在中序序列中的位置
dfs(pre + 1, in, i, false); //建立左子树
dfs(pre + i + 1, in + i + 1, size - i - 1, false); //遍历右子树
if(flag) //在后序中根是最后输出的
cout<<preorder[pre]<<endl;
else
cout<<preorder[pre]<<" ";
}
int main()
{
int i;
while(cin>>n)
{
for(i = 0; i < n; i++)
cin>>preorder[i];
for(i = 0; i < n; i++)
cin>>inorder[i];
dfs(0, 0, n, true);
}
return 0;
}以下是已知中序和后序求先序
#include <iostream>
using namespace std;
const int _N = 1010;
int inorder[_N], postorder[_N], n;
void dfs(int in, int post, int size, bool flag)
{
int i;
if(size <= 0)
return;
if(flag)
cout<<postorder[post];
else
cout<<" "<<postorder[post];
for(i = 0; inorder[in + i] != postorder[post]; i++); //查找跟在中序中的位置
dfs(in, post - size + i, i, false);
dfs(in + i + 1, post - 1, size - i - 1, false);
}
int main()
{
int i;
while(cin>>n)
{
for(i = 0; i < n; i++)
cin>>inorder[i];
for(i = 0; i < n; i++)
cin>>postorder[i];
dfs(0, n - 1, n, true);
cout<<endl;
}
return 0;
}
注意:如果已知先序和后序是不能求中序的，因为先序和后序能确定root但是不能确定左右子树
三， HDU3791-二叉搜索树
判断两序列是否为同一二叉搜索树序列
Input
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
Output
如果序列相同则输出YES，否则输出NO
Sample Input
2
567432
543267
576342
0Sample Output
YES
NO
二叉查找树又：二叉搜索树，二叉排序树
它或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
它的左、右子树也分别为二叉排序树。
注意二叉树和二叉搜索树（BST）的概念是不同的，二叉搜索树是一种特殊的二叉树。
它符合规律：所有节点的左孩子节点的值小于它根节点的值，右孩子节点的值大于根节点的值。就是小数放左边，大数放右边，来构成一棵二叉树。
一开始没有搞明白两者的区别，以为二叉搜索树就是二叉树，这让我在构造二叉树的时候产生了疑惑，因为根据数据结构书上的描述，二叉树可以根据前序、中序、后序序列构造，这样产生的结果就是不唯一的。
最后还是查找了一下二叉搜索树的概念才明白过来。根据它的规则就可以根据一个序列构成一个唯一的二叉搜索树了！
而同一个二叉搜索树却可以有不同的序列来描述。这
就产生了这道题的题意：给你两个不同的序列判断是否能构造出同一个二叉搜索树。
思路：那么我们就可以根据二叉搜索树的生成规则先将一开始给你的序列生成一个二叉搜索树用tree[]存储起来，
然后输入n个序列，每一个序列都生成一个二叉搜索树建立一个临时数组tree2[]存储，比较两个数组是否相同，相同输出“YES”，不同输出“NO”。
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int tree1[10000];
int tree2[10000];
void Insert(char word,int *tree)
{
//now表示第几个结点,c表示now结点中的值
int now=1;
int c=word-'0';
while(tree[now]!=-1)//如果结点有值,根左右子结点比较 ，
{
if(tree[now]<c)
now=now*2+1;
else now=now*2;
}
tree[now]=c;//比较后确定该值的位置
}
void build(char *str,int *tree)//构建二叉搜索树
{
int l=strlen(str);
tree[1]=str[0]-'0';
for(int i=1;i<l;i++)//一个一个数的插入
{
Insert(str[i],tree);
}
}
int main()
{
int n;
char str[1000];
while(~scanf("%d",&n)&&n)
{
memset(tree1,-1,sizeof(tree1)); //因为包括0-到9的数字，所以初始化为-1；
scanf("%s",str);
build(str,tree1);
for(int i=0;i<n;i++)
{
memset(tree2,-1,sizeof(tree2));
scanf("%s",str);
build(str,tree2);
int j;
for(j=0;j<5000;j++)
{
if(tree1[j]!=tree2[j])
break;
}
if(j==5000) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
这个方法比较靠取巧不过很管用’
下面再介绍一个正规军的做法，供参考
#include<stdio.h>
#include<string.h>
struct node
{
int val;
node *law,*raw;
};
bool flag;
node *insert(node *p,int x) //依次插入每个值
{
if(p==NULL) //节点为空时，插入此节点
{
node *q = new node; //申请一个动态空间
q->val=x; //赋值
q->law = q->raw =NULL; //左右儿子为空
return q; //返回此节点的地址
}
else //不为空，代表此节点有值
{
if(p->val>x) //如果这个值小于左儿子
p->law = insert(p->law,x); //递归向下寻找相应的位置，回溯赋值，构建链表
else //同理
p->raw = insert(p->raw,x);
return p;
}
}
void check(node *root,node *rom) //传入标准树和判断树的地址
{
if(root!=NULL&&rom!=NULL) //如果两个地址都不为空，即此节点两棵树都有值，只需判断值是否相同
{
check(root->law,rom->law);//中序遍历
if(root->val!=rom->val) //判断此节点的值是否和标准树一致
flag=false;
check(root->raw,rom->raw);
}
else if(root!=NULL||rom!=NULL) //如果两颗树中，只有一棵树在这个节点有值，那么这两棵树肯定不一致
flag=false;
}
int main()
{
int n;
while(~scanf("%d",&n)&&n)
{
node *root=NULL;//标准树地址为空
char str[20];
scanf("%s",str);
for(int i=0; i<strlen(str); i++) //构建一颗标准树
root = insert(root,str[i]-'0');
for(int i=0; i<n; i++) //n组数据
{
flag=true; //标记
node *rom=NULL; //判断树地址为空
scanf("%s",str);
for(int i=0; i<strlen(str); i++) //构建判断树
rom = insert(rom,str[i]-'0');
check(root,rom); //中序遍历，检查两棵树是否一致
if(flag)
printf("YES\n");
else
printf("NO\n");
}
}
return 0;
}
四，hd3999
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.
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 2Sample Output
1 3 2 4
就是简单先给出几个数，构建一个二叉搜索树，在先序输出
这里给你个我比较喜欢的编程风格代码，算是一个简单题的模板了
#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
int n,flag;
typedef struct node
{
int data;
node *lchild,*rchild;
}BiTreeNode,*BiTree;
void insert(BiTree &T,int x)
{
if(T==NULL)
{
T=new BiTreeNode;
T->data=x;
T->lchild=T->rchild=NULL;
return;
}
if(x<T->data)
insert(T->lchild,x);
else
insert(T->rchild,x);
}
void preOrder(BiTree &T)
{
if(T)
{
if(flag)
printf(" ");
printf("%d",T->data);
flag=1;
preOrder(T->lchild);
preOrder(T->rchild);
}
}
int main()
{
while(~scanf("%d",&n))
{
int x;
BiTree T=NULL;
for(int i=0;i<n;i++)
{
scanf("%d",&x);
insert(T,x);
}
flag=0;
preOrder(T);
printf("\n");
}
return 0;
}
五，比较全的模板
非常强大就是有时候各种运行错误，超时，让人崩溃。
不过都是可以运行出来，会的自己稍微改一下就好。
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <stack>
#include <queue>
#include <malloc.h>
using namespace std;
#define OK 1
#define ERROR -1
#define TRUE 1
#define FALSE 0
typedef int Status;
typedef struct STnode* link;
struct STnode{
int item;//元素值
link l;//该节点的左子树链接
link r;//该节点的右子树链接
};
//二叉搜索树的插入
link STinsert(link st, int num)
{
if(st == NULL)
{
//申请内存空间
link st = (link)malloc(sizeof(struct STnode));
//为节点赋值
st->item = num;
//将左右子树置为空
st->l = NULL;
st->r = NULL;
//将节点返回
return st;
}
//printf("*%d* ", st->item);
//该节点的值大于元素值的情况
if(st->item > num)
{
//递归调用节点的左子树
st->l = STinsert(st->l, num);
}
//该节点的值小于元素值的情况
else if(st->item < num)
{
//递归调用节点的右子树
st->r = STinsert(st->r, num);
}
}
//二叉搜索树中元素的查找
Status STsearch(link h,int v)
{
//空树,没有对应的值,查找失败
if(h == NULL)
{
return FALSE;
}
//找到对应的元素值,查找成功
if(v == h->item)
{
return TRUE;
}
//该节点的值大于元素值的情况
if(v < h->item)
{
//递归调用节点的左子树
STsearch(h->l, v);
}
//该节点的值小于元素值的情况
else
{
//递归调用节点的右子树
STsearch(h->r, v);
}
}
//删除节点代码
Status BSTdelete(link *st, int item)
{
link p = *st;
//空树的情况
if(!p)
{
return FALSE;
}
//找到了要删除的节点
if(p->item == item)
{
//如果该节点是叶子结点
if(!p->l && !p->r)
{
*st = NULL;
}
//如果该节点只有左孩子
else if(p->l && !p->r)
{
*st = p->l;
}
//如果该节点只有右孩子
else if(!p->l && p->r)
{
*st = p->r;
}
//如果该节点既有左孩子,又有右孩子
else
{
//将该节点的左孩子表示出来
link s = p->r;
//如果该节点的右孩子没有左孩子
if(!s->l)
{
s->l = p->l;
}
//如果该节点既有左孩子又有右孩子
else
{
//定义s节点的父节点parent
link parent = NULL;
//找到s节点下最左端的左叶子节点
while(s->l)
{
parent = s;
s = s->l;
}
//将s点断开
parent->l = s->r;
//将s点换到p点
s->l = p->l;
s->r = p->r;
}
//连成树
*st = s;
}
//将原节点释放掉
free(p);
return TRUE;
}
//如果元素值偏大
else if(item > ((*st)->item))
{
//递归右子树
BSTdelete(&(p->r), item);
}
//如果元素值偏小
else
{
//递归左子树
BSTdelete(&(p->l), item);
}
}
//递归树前序遍历
void Traverse1(link tree)
{
if(tree)
{
//先输出根结点
printf("%d ", tree->item);
//再递归其左子树
Traverse1(tree->l);
//再递归其右子树
Traverse1(tree->r);
}
}
//使用BST排序,即中序输出
void BSTsort(link h)
{
if(h == NULL)
{
return;
}
//递归调用左子树
BSTsort(h->l);
//输出元素值
printf("%d ", h->item);
//递归调用右子树
BSTsort(h->r);//递归调用
}
int main()
{
int a[12] = {2, 5, 3, 7, 6, 1, 4, 11, 8, 10, 9, 12};
link st = NULL;
int i;
//为空树中插入元素
for(i = 0; i < 12; i++)
{
st = STinsert(st, a[i]);
}
//先序遍历该二叉搜索树
Traverse1(st);
printf("\n");
//查找元素在二叉搜索树中是否存在
if(STsearch(st, 7))
{
printf("7 在树中存在.\n");
}
else
{
printf("** 在树中不存在.\n");
}
//中序遍历二叉搜索树,元素从小到大有序输出
BSTsort(st);
printf("\n");
//删除元素的情况
int flag = BSTdelete(&st, 11);
if(flag)
{
printf("删除成功!\n");
}
else
{
printf("要删除的元素不存在!\n");
}
//删除某个元素之后的先序遍历
Traverse1(st);
printf("\n");
//删除某个元素之后的中序遍历
BSTsort(st);
printf("\n");
return 0;
}
五，poj 1577
Falling Leaves
Figure 1
Figure 1 shows a graphical representation of a binary tree of letters. People familiar with binary trees can skip over the definitions of a binary tree of letters, leaves of a binary tree, and a binary search tree of letters, and go right to The problem.
A binary tree of letters may be one of two things:
It may be empty.
It may have a root node. A node has a letter as data and refers to a left and a right subtree. The left and right subtrees are also binary trees of letters.
In the graphical representation of a binary tree of letters:
Empty trees are omitted completely.
Each node is indicated by
Its letter data,
A line segment down to the left to the left subtree, if the left subtree is nonempty,
A line segment down to the right to the right subtree, if the right subtree is nonempty.
A leaf in a binary tree is a node whose subtrees are both empty. In the example in Figure 1, this would be the five nodes with data B, D, H, P, and Y.
The preorder traversal of a tree of letters satisfies the defining properties:
If the tree is empty, then the preorder traversal is empty.
If the tree is not empty, then the preorder traversal consists of the following, in order
The data from the root node,
The preorder traversal of the root’s left subtree,
The preorder traversal of the root’s right subtree.
The preorder traversal of the tree in Figure 1 is KGCBDHQMPY.
A tree like the one in Figure 1 is also a binary search tree of letters. A binary search tree of letters is a binary tree of letters in which each node satisfies:
The root’s data comes later in the alphabet than all the data in the nodes in the left subtree.
The root’s data comes earlier in the alphabet than all the data in the nodes in the right subtree.
The problem:
Consider the following sequence of operations on a binary search tree of letters
Remove the leaves and list the data removed
Repeat this procedure until the tree is empty
Starting from the tree below on the left, we produce the sequence of trees shown, and then the empty tree
by removing the leaves with data
BDHPY
CM
GQ
K
Your problem is to start with such a sequence of lines of leaves from a binary search tree of letters and output the preorder traversal of the tree.
Input
The input will contain one or more data sets. Each data set is a sequence of one or more lines of capital letters.
The lines contain the leaves removed from a binary search tree in the stages described above. The letters on a line will be listed in increasing alphabetical order. Data sets are separated by a line containing only an asterisk (‘*’).
The last data set is followed by a line containing only a dollar sign (‘$’). There are no blanks or empty lines in the input.
Output
For each input data set, there is a unique binary search tree that would produce the sequence of leaves. The output is a line containing only the preorder traversal of that tree, with no blanks.
Sample Input
BDHPY
CM
GQ
K
*
AC
B
$
Sample Output
KGCBDHQMPY
BAC
题意：就是输入多组字符串，如果字符串为‘ * ’，则把之前建树的都删了，碰到‘
$
’ ，就结束输入；
ps（主要是插入的是字符，和如果对字符进行处理这样的题型）’
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
const int maxn = 30;
struct SBT{
int left,right;
char c;
}tree[maxn];
int root,tot,st;
char s[maxn][maxn];
void add(int x, char ch){
if (ch<tree[x].c){
if (tree[x].left == 0){
tree[tot].c = ch;
tree[x].left = tot++;
}
else add(tree[x].left,ch);
}
else {
if (tree[x].right == 0){
tree[tot].c = ch;
tree[x].right = tot++;
}
else add(tree[x].right,ch);
}
}
void Print(int x){
printf("%c",tree[x].c);
if (tree[x].left) Print(tree[x].left);
if (tree[x].right) Print(tree[x].right);
}
int main(){
st = 0;
while (scanf("%s",s[st++])!=EOF){
if (s[st-1][0]=='*' || s[st-1][0]=='$') {
root = tot = 0;
memset(tree,0,sizeof(tree));
tree[tot++].c = s[st-2][0];
for (int i=st-3; i>=0; i--) {
for (int j=0; j<strlen(s[i]); j++) add(root,s[i][j]);
}
Print(root);
if (s[st-1][0]=='$') break;
st = 0;
printf("\n");
}
}
return 0;
}