题目：层序遍历二叉树

给定一棵二叉树，要求层序遍历该二叉树，即从上到下按层次访问该树，每一层单独输出一行，每一层要求访问的顺序为从左到右。我们在遍历的过程中将该层节点的孩子节点压入一个队列，这样就可以实现从上到下一层一层地遍历该二叉树。 

初始时，根结点入队列。 

然后，while循环判断队列不空时，弹出一个结点，访问它，并把它的所有孩子结点入队列。



template<class T>
struct BinaryTreeNode
{
    BinaryTreeNode(const T& data)
        :_data(data)
        ,_pLeft(NULL)
        ,_pRight(NULL)
    {}

    T _data;
    BinaryTreeNode<T>* _pLeft;
    BinaryTreeNode<T>* _pRight;
};
template<class T> class BinaryTree
{
    typedef BinaryTreeNode<T> Node;
public:
    BinaryTree()
        :_pRoot(NULL)
    {}
    BinaryTree(const T array[],size_t size,const T& invalid)
    {
        size_t index = 0;
        _CreateTree(_pRoot,array,size,index,invalid);
    }
    void LevelOrder()
    {
        cout<<"层序遍历二叉树:"<<endl;
        queue<Node*> q;
        Node* pCur = NULL;
        if(NULL != _pRoot)
        {
            q.push(_pRoot);
            while(!q.empty())
            {
                pCur = q.front();
                cout<<pCur->_data <<" ";
                if(pCur->_pLeft )
                    q.push(pCur->_pLeft );
                if(pCur->_pRight )
                    q.push(pCur->_pRight );
                q.pop();
            }
        }
        cout<<endl;
    }
private:
    void _CreateTree(Node*& pRoot,const T array[],size_t size,size_t& index, const T& invalid)
    {
        if(index < size && array[index ]!= invalid)
        {
            pRoot = new Node(array[index]);
            _CreateTree(pRoot->_pLeft ,array,size,++index,invalid);
            _CreateTree(pRoot->_pRight ,array,size,++index,invalid);
        }
    }
private:
    Node* _pRoot;
};
int main()
{
    char *str = "124###35##6";
    BinaryTree<char> t(str,strlen(str),'#');
    t.LevelOrder ();
    return 0;
}

　给定一个插入序列就可以唯一确定一个平衡二叉树，但是，一个给定的平衡二叉树却可以由不同的插入序列得到。 

　比如按照序列｛２，１，３｝与序列｛２，３，１｝插入初始为空的二叉搜索树中，将得到相同的二叉平衡树。强调内容

那么我们应该怎么判断输入的不同序列是否生成的是同一颗二叉搜索树呢？

有一下三种方式：



1.建立搜索树

　根据两个序列分别建立两个搜索树，在去比较两个树是否一样。



2.不建立搜索树

首先比较序列的第一个元素是否相同，如果不相同，则说明两个序列对应的一定不是同一个树，如果相同，说明两个序列的根元素是相同的。然后可以把后边的元素分成两堆（比第一个元素小的，比第一个元素大的），分类的时候元素的顺序是不能改变的。 

　　比如序列１｛３，１，２，４｝与序列２｛３，４，１，２｝首先判断第一个元素是相等的，则把后边的元素分类。序列１变为{**1,2,**3,**4**},序列２变为{**3,1,**2,**4**},比较可得两个序列对应的是同一个二叉搜索树。 

　　又如{3,1,2,4}与{3,2,4,1}　这两个序列，经过变化之后为{1,2,3,4},{2,1,3,4} 可以得到前两个的元素顺序是不相同的，所以这两个序列对应的搜索树是不相同的。



3.建立一个树，在判断其他序列是否与该树相同。



3.1 搜索树表示方法



typedef struct TreeNode *Tree;
struct TreeNode
{
    ElementType v;
    Tree left,right;
    int flag;
};

ｖ表示的是在结构体中存储的数据，类型为ElementType,left,right表示的是左右孩子节点的地址。flag是作为一个节点的标记，默认为0。



3.2 建立搜索树

 首先需要读入序列的长度N，与需要判断序列的个数L。然后根据N个元素去建立搜索树T。最后依据树T去判断后边的L个序列是否能与树T形成同一个搜索树。


需要设计的主要函数有:

读取数据建树 MakeTree(int N);
判断一个序列是否与T构成一样的树(Judge(Tree T,int N));

main函数主要框架构建：
void main()
{
    int N,L,i;
    Tree T;
    scanf("%d",&N);
    while(N)
    {
        scanf("%d",&L);
        T = MakeTree(N);//建树
        for(i = 0;i<L;i++)//有L个序列需要比较
        {
            if(Judge(T,N))//满足条件，表示是同一个序列
                printf("Yes\n");
            else 
                printf("No\n");
            Reset(T);//序列比较结束，当比较下一个序列的时候，把当前做的标记清除。
        }
        FreeTree(T);//释放树
        scanf("%d",&N);//继续下一批序列的比较
    }
}



3.3判断一个序列是否与搜索树相同

当一个树T建立之后，如何判断一个序列对应的搜索树是否跟T相同呢？


方法: 在树T中按顺序搜索序列中的的每个数。

如果每次搜索所经过的节点都出现过，则表示相同
搜索中遇到前面没有遇到的节点，则表示不一致。


对应的函数实现：



int check(Tree T,int V)
{
    if(T->flag)
    {
        if(T->v > V)
            check(T->left,V);
        else if(T->v < V)
            check(T->right,V);
        else
            return 0;
    }
    else
    {
        if(T->v == V)
        {
            flag == 1;
            return 1;   
        }
        else // 在标记是0 的条件下，数值也不相同，导致在序列构建树的时候，该节点会不一致。
        return 0;
    } 
}

Judge(Tree T ,int N)函数的具体实现：



int Judge(Tree T,int N)//有bug
{
    int V,i;
    scanf("%d",&V);
    if(T->v != V)return 0;
    else T->flag = 1;
    for(i = 1;i<N;i++)
    {
        scanf("%d",&V);
        if(!check(T,V))return 0;
    }
    else return 1;
}

然后在这种情况下，Judge函数会有一个bug出现，当一个序列还没有输入完全的时候，出现了不一致，导致了后边的数值无法输入。所以在Judge函数中引入一个标记，确保在不一致的时候，也可以把后边的序列输入完全。

更改如下：



int Judge(Tree T,int N)
{
    int V,i;
    int flag = 0;//标记默认为 0，当序列与T出现不一致的时候，设为 1 
    scanf("%d",&V);
    if(T->v != V)flag = 1;//根节点不同，把标记设为 1 
    else 
        T->flag = 1;//注意与函数中的标记做区分
     for(i = 1;i<N;i++)
    {
        scanf("%d",&V);
        if((!flag)&&(!check(T,V))) flag = 1;
    }
    if(flag)
        return return 0;
    return 1;
}

全部代码：



#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode *Tree;
struct TreeNode
{
    ElementType v;
    Tree left,right;
    int flag;
}

void main()
{
    int N,L,i;
    Tree T;
    scanf("%d",&N);//输入二叉树的节点数。
    while(N)
    {
        scanf("%d",&L);//L表示的是有几个需要不比较的数目
        T = MakeTree(N);
        for(i = 0;i<L;i++)
        {
            if(Judge(T,N))printf("Yes\n");
            else printf("No\n");
            Reset(T);//清除标记 
        }
        FreeTree(T);
        scanf("%d",&N); 
    } 
}
int Judge(Tree T,int N)//当发现出现不一致的时候，也要把后边的数据输入完，不能直接返回。所以添加了flag标记。 
{
    int i ,V;
    int flag = 0;//flag = 1;表示的是已经出现了不一致。 

    scanf("%d",&V);
    if(V != T->v ) flag = 1;
    else T->flag = 1;

    for(i = 1;i<N;i++)
    {
        scanf("%d",&V);
        //if(!check(T,V))return 0;出现不一致，不可以直接返回，要把后边的数据输入完
        if((!flag) && (!check(T,V))) flag = 1;
    }
    if(flag) return 0;
    else return 1;
}

int check(Tree T,int V)
{
    if(T->flag)
    {
        if(T->v > V) check(T->Left,V);
        else if(T->v < V)check(T->Right,V);
        else return 0;
    }
    else
    {
        if(T->v == V)
        {
            T->flag = 1;
            return 1;
        }
        else return 0;
    }
}

//建立二叉树
Tree MakeTree(int N)//n表示的是这颗树有多少个节点 
{
    Tree T;
    int V i;
    scanf("%d",&V);//输入第二个节点的数值，去建立一个树
    Tree = NewNode(V);//建立根节点
    for(i = 1;i<N;i++)
    {
        scanf("%d",&V);//先节点的数值 
        T = Insert(T,V);//在根节点上插入节点 
    }
    return T; 
}
//插入节点函数
Tree Insert(Tree T,int V)
{
    if(!T)T = NewNode(V);//
    else
    {
        if(T->v > V)
        {
            T->left = Insert(T,V);  
        }
        else
            T->right = Insert(T,V); 
    }
    return T;
} 


//建立二叉树的每一个节点
Tree NewNode(int V)
{
    Tree T = (Tree)malloc(sizeof(struct TreeNode));
    T->v = V;
    T->left = T->right = NULL;
    T->flag = 0;
    return T;  
} 
//清楚标记 
void Reset(Tree T)
{
    if(T->left)Reset(T->left);
    if(T->right)Reset(T->right);
    T->flag = 0;
}
//释放内存空间
void FreeTree(Tree T)
{
    if(T->left) FreeTree(T->left);
    if(T->right)FreeTree(T->right);
    free(T);    
} 

考察AVL树的操作
给出N个正整数，将它们依次插在一颗初始为空的AVL树上，求插入后根节点的值。
思路

考察平衡二叉树的建立操作[算法笔记]二叉树
注意在插入和旋转操作的时候用对节点类型的形式参数使用引用

AC代码
//PAT_A 1066
#include<cstdio>
#include<algorithm>
using namespace std;
struct node {
	int v, height;
	node* lchild;
	node* rchild;
}*root;
node* newNode(int v) {
	node* Node = new node;
	Node->v = v;
	Node->lchild = Node->rchild = NULL;
	Node->height = 1;//节点初始高度为1
	return Node;
}
int getHeight(node* root) {
	if (root == NULL)return 0;
	return root->height;
}
void updateHeight(node* root) {
	root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
int getBalanceFactor(node* root) {
	return getHeight(root->lchild) - getHeight(root->rchild);
}
void L(node*& root) {//左旋
	node* temp = root->rchild;
	root->rchild = temp->lchild;
	temp->lchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}
void R(node*& root) {//右旋
	node* temp = root->lchild;
	root->lchild = temp->rchild;
	temp->rchild = root;
	updateHeight(root);
	updateHeight(temp);
	root = temp;
}
void insert(node*& root, int v) {
	if (root == NULL) {
		root = newNode(v);
		return;
	}
	if (v < root->v) {
		insert(root->lchild, v);//像左子树插入
		updateHeight(root);
		if (getBalanceFactor(root) == 2) {
			if (getBalanceFactor(root->lchild) == 1) {//LL
				R(root);
			}
			else if (getBalanceFactor(root->lchild) == -1) {//LR
				L(root->lchild);
				R(root);
			}
		}
	}
	else {
		insert(root->rchild, v);
		updateHeight(root);
		if (getBalanceFactor(root) == -2) {
			if (getBalanceFactor(root->rchild) == -1) {//RR
				L(root);
			}
			else if (getBalanceFactor(root->rchild) == 1) {//RL
				R(root->rchild);
				L(root);
			}
		}
	}
}
node* create(int data[], int n) {
	node* root = NULL;
	for (int i = 0; i < n; i++) {
		insert(root, data[i]);
	}
	return root;
}
int main() {
	int n, v;
	(void)scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		(void)scanf("%d", &v);
		insert(root, v);
	}
	printf("%d\n", root->v);
	return 0;
}

    
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4288
 
题目大意：有n个操作和一个集合（初始为空），并且集合内元素满足按顺序排列。
现有三种操作：
add x ： 将元素x加入集合中。
del x： 将集合中的x元素删除。
sum： 统计集合中元素下标满足i%5==3的总和。
 
解题思路：  以为在线段树方面小有火候，现在发现自己在线段树方面还没起火，处于冒烟阶段。
                这题让我蛋蛋又碎了，WA了一个晚上，各种调试，最后发现是数组必须开成节点4倍大小，我只开了两倍大小，导致了一个晚上的悲剧（why？个人认为两倍足够了，可以证明的）。
                可以想到五颗线段树的操作，离线处理还是比较难想到的。先离线处理可以知道我们要处理多少个点，进行建树操作。然后接下来对这n个操作进行即时更新，遇见add x，则往x的对应位置进行传递，直到达到叶子节点，更新叶子节点sz为1，del x则更新对应叶子节点sz为0。然后递归回去上传更新，父亲的  sum[u][i]等于左孩子的sum[u][i]，而右孩子上传时则需要处理，因为位置发生了变化，cnt表示父亲的左孩子有cnt个实节点，所以右孩子上传时下标是从cnt+i开始，五种状态随时更新，随时相互转换。
View Code 

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 #define lz 2*u,l,mid
 8 #define rz 2*u+1,mid+1,r
 9 const int maxn=100005;
10 __int64 sum[4*maxn][6];  ///开成2*maxn WA了一个晚上，蛋蛋都碎了
11 int a[maxn], X[maxn], sz[4*maxn];
12 char str[maxn][20];
13 
14 void push_up(int u)
15 {
16     sz[u]=sz[2*u]+sz[2*u+1];
17     for(int i=0; i<5; i++) sum[u][i]=sum[2*u][i];
18     for(int i=0; i<5; i++) sum[u][(i+sz[2*u])%5]+=sum[2*u+1][i];
19 }
20 
21 void build(int u, int l, int r)
22 {
23     sz[u]=0;
24     for(int i=0; i<5; i++) sum[u][i]=0;
25     if(l==r) return ;
26     int mid=(l+r)>>1;
27     build(lz);
28     build(rz);
29 }
30 
31 void Update(int u, int l, int r, int pos, int c)
32 {
33     if(l==r)
34     {
35         sz[u]=c;
36         sum[u][1]=c*X[l];
37         return ;
38     }
39     int mid=(l+r)>>1;
40     if(pos<=mid) Update(lz,pos,c);
41     else Update(rz,pos,c);
42     push_up(u);
43 }
44 
45 int main()
46 {
47     int n;
48     while(cin >> n)
49     {
50         int num=0, pos;
51         for(int i=0; i<n; i++)
52         {
53             scanf("%s",str[i]);
54             if(str[i][0]!='s')
55             {
56                 scanf("%d",&a[i]);
57                 if(str[i][0]=='a') X[++num]=a[i];
58             }
59         }
60         sort(X+1,X+num+1);
61         int ep=unique(X+1,X+num+1)-(X+1);  ///去重
62         build(1,1,ep);
63         for(int i=0; i<n; i++)
64         {
65             if(str[i][0]=='a') pos=upper_bound(X+1,X+ep+1,a[i])-(X+1), Update(1,1,ep,pos,1);
66             else if(str[i][0]=='d') pos=upper_bound(X+1,X+ep+1,a[i])-(X+1), Update(1,1,ep,pos,0);
67             else printf("%I64d\n",sum[1][3]);
68         }
69     }
70     return 0;
71 }


 

转载于:https://www.cnblogs.com/kane0526/archive/2013/04/25/3043170.html