List Leaves

Given a tree, you are supposed to list all the leaves in the order of top down, and left to right.

Input Specification

Each input file contains one test case. For each case, the first line gives a positive integer N(10)N(≤10) which is the total number of nodes in the tree – and hence the nodes are numbered from 0 to N−1. Then N lines follow, each corresponds to a node, and gives the indices of the left and right children of the node. If the child does not exist, a “-” will be put at the position. Any pair of children are separated by a space.

Output Specification

For each test case, print in one line all the leaves’ indices in the order of top down, and left to right. There must be exactly one space between any adjacent numbers, and no extra space at the end of the line.

Sample Input

8
1 -
- -
0 -
2 7
- -
- -
5 -
4 6

Sample Output

4 1 5

ac代码

#include<iostream>
#include<queue>
#define MaxTree 10
#define Tree int
#define Null -1
using namespace std;
struct TreeNode
{
    Tree Left;
    Tree Right;
}T[MaxTree];
Tree BuildTree(struct TreeNode[]);
void leaves(Tree);
int main()
{
    Tree R;
    R=BuildTree(T);
    leaves(R);
}
Tree BuildTree(struct TreeNode T[])
{
    int i,N,check[MaxTree];
    char cl,cr;
    Tree Root;
    cin>>N;
    if(!N)return Null;
    for(i=0;i<N;i++)check[i]=0;
    for(i=0;i<N;i++) {
        cin>>cl>>cr;
        if (cl != '-') {
            T[i].Left = cl - '0';
            check[T[i].Left] = 1;
        } else T[i].Left = Null;
        if (cr != '-') {
            T[i].Right = cr - '0';
            check[T[i].Right] = 1;
        } else T[i].Right = Null;
    }
    for(i=0;i<N;i++)if(!check[i])break;
    Root=i;
    return Root;
}
void leaves(Tree R){
    queue<int> q;
    int flag=0;
    q.push(R);
    while(!q.empty()){
        if(T[q.front()].Left!=Null)q.push(T[q.front()].Left);
        if(T[q.front()].Right!=Null)q.push(T[q.front()].Right);
        if(T[q.front()].Left==Null&&T[q.front()].Right==Null){
            if(!flag){
                cout<<q.front();
                flag=1;
            }
            else cout<<' '<<q.front();
        }
        q.pop();
    }
}

Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

(图片暂时找不到了😳囧…)

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N(30)N(≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format:
“Push X” where X is the index of the node being pushed onto the stack;
or “Pop” meaning to pop one node from the stack.

Output Specification

For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.

Sample Input

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output

3 4 2 6 5 1

分析

实际上在输入格式中Push的过程是二叉树前序遍历的结果,Pop的过程是二叉树的中序遍历的结果
如因此题目的意思变成已知二叉树的前序遍历和中序遍历求二叉树的后序遍历

void solve(int prel,int postl,int inl,int n)
{ //只需要获得前序的第一个结点下标以及子树的结点数,然后在中序序列中操作即可
    if(!n)return;
    if(n==1)
    {
        post[postl]=pre[prel];
        return;
    }
    int root=pre[prel];
    post[postl+n-1]=root;
    for(int i=0;i<n;i++)if(in[inl+i]==root)break;
    int l=i,r=n-l-1;
    solve(prel+1,inl,postl,l);
    solve(prel+l+1,inl+l+1,postl+l,r);
}

ac代码

#include<iostream>
#include<stack>
#include<string>
#define MaxTree 30
using namespace std;
int inorder[MaxTree],preorder[MaxTree],postorder[MaxTree];
void getseries(int);
void post(int, int, int);
int main()
{
    int n;
    cin>>n;
    getseries(n);
    post(0,0,n-1);
}
void getseries(int n){
    stack<int> s;
    int i=0,j=0,nu;string str;
    while(i<n||j<n){
        cin>>str;
        if(str=="Push"){
            cin>>nu;
            s.push(nu);
            preorder[i++]=nu;
        }
        if(str=="Pop"){
            inorder[j++]=s.top();
            s.pop();
        }
    }
}
void post(int root, int start, int end) {  //root为根结点,start和end是中序序列的开始和结尾
    //用分而治之的策略,使用先序序列第一个元素(根结点)对中序序列的划分出的左右子树的两个中序序列递归进行划分,直到划分到只剩一个
    //如果给出后序和中序,求先序,也是一样的,只是变成用后序序列的最后一个元素划分中序序列
    //中序序列是必须知道的,因为没有中序序列,就没法把二叉树划分成根和左右子树
    if(start > end)return;
    int i = start;
    static int flag=0;
    while(i < end && inorder[i] != preorder[root]) i++;     //找到中序序列中的根结点下标
    post(root + 1, start, i - 1);                           //左子树求后序序列,root+1为左子树先序序列中的根结点
    post(root + 1 + i - start, i + 1, end);   //右子树求后序序列,i-start是左子树结点个数,root+1+i-start是右子树先序根结点
    if(!flag){
        cout<<preorder[root];
        flag=1;
    }else cout<<' '<<preorder[root];
}

Complete Binary Search Tree

A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:
The left subtree of a node contains only nodes with keys less than the node’s key. The right subtree of a node contains only nodes with keys greater than or equal to the node’s key. Both the left and right subtrees must also be binary search trees. A Complete Binary Tree (CBT) is a tree that is completely filled, with the possible exception of the bottom level, which is filled from left to right. Now given a sequence of distinct non-negative integer keys, a unique BST can be constructed if it is required that the tree must also be a CBT. You are supposed to output the level order traversal sequence of this BST.

Input Specification

Each input file contains one test case. For each case, the first line contains a positive integer N(1000)N(≤1000). Then N distinct non-negative integer keys are given in the next line. All the numbers in a line are separated by a space and are no greater than 2000.

Output Specification

For each test case, print in one line the level order traversal sequence of the corresponding complete binary search tree. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input

10
1 2 3 4 5 6 7 8 9 0

Sample Output

6 3 8 1 5 7 9 0 2 4

分析

完全二叉搜索树将给定的序列通过某种组织方式使其既是一棵完全二叉树又是一棵二叉搜索树

树的表示法:链表vs数组

  • 需要的操作
    • 填写数字(某种遍历) —— 完全二叉树,不浪费空间
    • 层序遍历 —— 直接顺序输出
  • 数组完胜

核心算法

void solve(int Aleft,int Aright,TRoot)   
{//排序后的输入序列A,从A中选出正确的根结点填入T[TRoot]中
    //初始调用为solve(0,n-1,0);
    n=Aright-Aleft+1;       //计算出输入序列的结点数
    if(!n)return;           //n为0时结束递归调用
    L=GetLeftLength(n);     //计算出n个结点的树其左子树有多少个结点
    T[TRoot]=A[Aleft+L];    //ALeft+左子树结点个数就是序列中根结点的下标
    LeftTRoot=TRoot*2+1;    //左子树的根结点下标为TRoot*2+1(整个树的根结点下标为0)
    RightTRoot=LeftTRoot+1; //右子树根结点下标为TRoot*2+1
    solve[Aleft,Aleft+L-1,LeftTRoot];    //在左右子树递归调用此过程
    solve[Aleft+L+1,Aright,RightTRoot];
}

计算左子树的规模GetLeftLength()

完全二叉树前h-1层的总结点个数:(2h1)1(2^h-1)-1 (h从1开始)。因此左子树的结点数n=2h21+xn=2^{h-2}-1+x,x为最下面一层的结点个数(0x2h2)(0\leq x\leq2^{h-2}),此时h=lg(n+1)h=⌊lg(n+1)⌋
不过到这里x的值不一定等于x(最下一层结点数),此时有两种情况:x超过左子树的叶子结点数,x不超过左子树的叶子结点数
x=min(x,2h2)x=min(x,2^{h-2})

ac代码

#include<iostream>
#include<queue>
#include<cmath>
#define MAXLINE 1000
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
typedef struct TreeNode *BinTree;
typedef int ElementType;
struct TreeNode {
    ElementType val;
    BinTree left,right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
int pre[MAXLINE],in[MAXLINE],lev[MAXLINE];
void CBST(int*,int,int,int);
int partiation(int*,int,int);
void qksort(int*,int,int);
BinTree create(int*,int*,int,int,int,int);
void levelorder(BinTree);
int main() {
    int i,n,v[MAXLINE];
    cin>>n;
    for(i=0;i<n;i++)cin>>v[i];
    qksort(v,0,n-1);
    CBST(v,n,0,n-1);
    BinTree BT= create(pre,in,0,n-1,0,n-1);
    levelorder(BT);
    for(i=0;i<n-1;i++)cout<<lev[i]<<' ';
    cout<<lev[n-1];
}
int partiation(int* v,int start,int end){
    if(v==NULL||start<0||start>end)return -1;
    int pivot=v[start];
    while(start<end){
        for(;v[end]>=pivot&&start<end;end--);
        v[start]=v[end];
        for(;v[start]<pivot&&start<end;start++);
        v[end]=v[start];
    }
    v[start]=pivot;
    return start;
}
void qksort(int*v,int start,int end){
    if(end-start<1)return;
    int pivot= partiation(v,start,end);
    if(pivot>start+1)qksort(v,start,pivot-1);
    if(pivot<end-1)qksort(v,pivot+1,end);
}
void CBST(int*v,int n,int start,int end){
    int h,pivot;
    static int i=0,j=0;
    if(end-start<1){
        pre[i++]=in[j++]=v[start];
        return;
    }
    for(h=0;(int)pow(2,h)<n+1;h++);
    pivot=start+(min(pow(2,h-2),(int)pow(2,h-1)-(int)pow(2,h)+1+n))+(int)pow(2,h-2)-1;
    pre[i++]=v[pivot];
    if(pivot-start>0)CBST(v,pivot-start,start,pivot-1);
    in[j++]=v[pivot];
    if(end-pivot>0)CBST(v,end-pivot,pivot+1,end);
}
BinTree create(int*pre,int*in,int ps,int pe,int is,int ie){
    if(ps>pe)return nullptr;
    TreeNode* node = new TreeNode(pre[ps]);
    int pos;
    for(int i=is;i<=ie;i++)
        if(in[i]==node->val){
            pos=i;
            break;
    }
    node->left=create(pre,in,ps+1,ps+pos-is,is,pos-1);
    node->right=create(pre,in,pe-ie+pos+1,pe,pos+1,ie);
    return node;
}
void levelorder(BinTree BT){
    queue<BinTree> q;
    int i=0;
    BinTree T=BT;
    q.push(T);
    while(!q.empty()){
        T=q.front();
        q.pop();
        lev[i++]=T->val;
        if(T->left)q.push(T->left);
        if(T->right)q.push(T->right);
    }
}