精华内容
下载资源
问答
  • 题目:层序遍历二叉树给定棵二叉树,要求层序遍历该二叉树,即从上到下按层次访问该树,每层单独输出行,每层要求访问的顺序从左到右。我们遍历的过程中将该层节点的孩子节点压入个队列,这样就可以...

    题目:层序遍历二叉树

    给定一棵二叉树,要求层序遍历该二叉树,即从上到下按层次访问该树,每一层单独输出一行,每一层要求访问的顺序为从左到右。我们在遍历的过程中将该层节点的孩子节点压入一个队列,这样就可以实现从上到下一层一层地遍历该二叉树。
    初始时,根结点入队列。
    然后,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;
    }
    展开全文
  •  比如按照序列{2,1,3}与序列{2,3,1}插入初始为空的二叉搜索树中,将得到相同的二叉平衡树。强调内容那么我们应该怎么判断输入的不同序列是否生成的是同一颗二叉搜索树呢?有一下三种方式:1.建立搜索...

     给定一个插入序列就可以唯一确定一个平衡二叉树,但是,一个给定的平衡二叉树却可以由不同的插入序列得到。
     比如按照序列{2,1,3}与序列{2,3,1}插入初始为空的二叉搜索树中,将得到相同的二叉平衡树。强调内容


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

    有一下三种方式:

    1.建立搜索树

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

    2.不建立搜索树

    首先比较序列的第一个元素是否相同,如果不相同,则说明两个序列对应的一定不是同一个树,如果相同,说明两个序列的根元素是相同的。然后可以把后边的元素分成两堆(比第一个元素小的,比第一个元素大的),分类的时候元素的顺序是不能改变的。
      比如序列1{3,1,2,4}与序列2{3,4,1,2}首先判断第一个元素是相等的,则把后边的元素分类。序列1变为{**1,2,**3,**4**},序列2变为{**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;
    };

    v表示的是在结构体中存储的数据,类型为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);    
    } 
    展开全文
  • [PAT-A 1066]Root of AVL Tree

    2019-09-06 18:10:43
    给出N个正整数,将它们依次插在一颗初始为空的AVL树上,求插入后根节点的值。 思路 考察平衡二叉树的建立操作[算法笔记]二叉树 注意在插入和旋转操作的时候用对节点类型的形式参数使用引用 AC代码 //1066 Root of ...

    在这里插入图片描述
    考察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;
    }
    
    展开全文
  • 题目大意:有n个操作和个集合(初始为空),并且集合内元素满足按顺序排列。 现有三种操作: add x : 将元素x加入集合中。 del x: 将集合中的x元素删除。 sum: 统计集合中元素下标满足i%5==3的总和。 ...

    题目链接: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

    展开全文
  • // 根据数组a中n个权值建立一颗哈夫曼树,则返回树根指针 BTreeNode **b, *q; // 动态地分配一个由b指向的指针数组 b = new BTreeNode*[n]; int i, j; // 初始化b指针数组,使每个指针元素指向a数组中...
  • """创建一颗子弹,并将其加入到编组bullets中""" if len(bullets) 限制子弹数量10以内 new_bullet = Bullet(ai_settings, screen, ship) # 新建一个子弹 bullets.add(new_bullet) # bullets中再添加一个...
  • Prim算法求解最小生成树的Java实现

    千次阅读 2017-07-06 21:11:15
    与Krusal算法不同的是,Prim算法求解过程中始终保持临时结果是一颗联通的树。该算法的伪代码如下 //假设网络中至少有一个个顶点 设T为所选边的集合,初始化T为空 设 TV为已树中的顶点的集合,置TV={1} 令E为网络...
  • Description有一颗初始为空的二叉查找树,每次加入一个数,求每次加入后当前树中,两两点之间的距离和。 n先把树给建出来, 暴力建树显然会被卡,有结论:设当前的数为x, 比x小的数中最大的数是a,比x大的数中...
  • 二叉搜索树又被称为二叉排序树,它或者是一颗空树,或者是具备以下性质的二叉树 若它的左子树不为空,则左子树上所有节点的值都小于根节点的值 若它的右子树不为空,则右子树上所有节点的值都大于根节点的值 它的...
  • 【说明】:博客内容选自课程课件 已知长度为12的表:  (Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec) ...2.按表中元素的顺序依次插入生成一颗二叉排序树(初始为空),并求其等概率的情况下...
  • 随机生成 对于任何一组关键码词条,考察它所有可能的排列,将关键码依次插入一颗初始为空的树。当关键码为n时, 可能的生成序列有n!种。 n!颗BST树平均高度为logn。(有重复) 2.随机组成 将所有的n...
  • 我们知道在一个排好序的数组中进行二分查找的时间复杂度是 O(logn), 是非常高效的(40亿量级的数据,只需要32次左右的查找);所以将二分查找的思想应用在二叉树中,就是一颗二叉查找...
  • 文章目录头文件定义结构体初始化栈//入栈出栈取栈顶元素值判断栈是否为空生成一颗二叉树前序中序后序主函数运行结果 头文件 #include<dos.h> #include<conio.h> #include<stdio.h> #include<...
  • 数据结构——Trie树

    2018-12-08 22:17:00
    Tire树(字典树)是用于...一颗空的Tire树仅包含根节点,且该点的指针为空 插入 当我们要插入一个字符串a时,我们先令指针p指向根节点,然后扫描a中的每一个字符c,执行以下操作: 1.当p中的c指向一个已存在的...
  • 题意:一颗n节点的带权无向树,一个初始为空的集合S,有两种操作:1 x 如果S中没有x,加入x ;2 x 如果S中存在x,删除x。每次操作完后求出使S集合连通的最小边权和。 解析:设root为S集合的LCA。点i的左右时间戳为L...
  • 算法思想 ...对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有个权值为Wi的根结点,它的左右子树均为空。(为方便计算机上...
  • 现在给你N个关键字值各不相同的节点,要求你按顺序插入初始为空树的二叉排序树中,每次插入后成功后,求相应的父亲节点的关键字值,如果没有父亲节点,则输出-1。 自己debug一边,发现 for(i=0;i;i++){ ...
  • 洛谷P2346四子连棋

    2019-09-29 02:31:17
    在一个4*4的棋盘上摆放了14颗棋子,其中有7颗白色棋子,7颗黑色棋子,有两个空白地带,任何一颗黑白棋子都可以向上下左右四个方向移动到相邻的空格,这叫行棋一步. 黑白双方交替走棋,任意一方可以先走,如果某个...
  • (1)初始化:根据给定的n个权值,构造n棵二叉树的森林集合F={T1,T2,…,Tn},其中每棵二叉树只有个权值为Wi的根节点,左右子树均为空。 (2)找最小的树并构造新的树:森林集合F中选取两根的权值最小的树作为...
  • 、最小生成树问题 ...2)初始化:Vnew={x},x为任意个顶点,作为起始点,Enew={},为空 3)集合E中选择权值最小的边<u,v>,其中u为集合Vnew中的顶点,而v不集合Vnew中但V中,(若...
  • 并且消除之后,空隙上方的宝石会下落,底层左侧为空的话,便整体左移。给初始状态,问最大的得分。看数据规模明显就是让写搜索的,但肯定不会让裸的爆搜直接过掉- -,关键就是怎么剪枝了。我的写法是搜索的...
  • 题目意思是有一颗带边权的树,现在有个集合S,初始为空,有2种操作,把某个点加入S或者S中删除,每次操作完后,都要你输出当前S集合中所有点相连的最小路径和。 设加入的点为u, 其实答案更新是 ans+ u点到S集合...
  • 题意: 给一颗树,每个节点两...如果让线段树初始为空,叶子的值是-1。 将节点按 x 从大到小排序,x 相等则 dfs序小的前 (这里子树中root的dfs序最小) 然后只要按序查询每个节点对应的子树,然后将节点更新到线
  • 子弹的实现可以使用STL中的vector,当按下开火键时发出一颗子弹,就往vector中添加一个结点;当子弹飞出窗口或击中敌机时,再将结点从vector中删除。每帧游戏画面中子弹飞行时只需将vector中的所有子弹进行处理、...
  • 二叉树总结(序列化与反序列化) ... * “#”不是节点为空,“!”表示个节点值的结束。不加结 * 束符号,可能根据序列化字符串产生多树,存在歧义。 * 3、如果遇到非空节点,假设节点...
  • 1.问题 [描述算法问题,首选形式化方式(数学语言),其次才是非形式化方式(日常语言)] ...①随机选择一点v加入V(初始为空),并设变量ans记录已选中的权值和 ②找到图中权值最小的边<v1,v2>,要求v1存在
  • //有 if (T1[R1].element!=T2[R2].element) return 0;//根节点数据不`同 if ((T1[R1].left==null)&&(T2[R2].left==null)) //都没有左节点 return judge(T1[R1].right,T2[R2].right); if(((T1[R1]....

空空如也

空空如也

1 2 3
收藏数 41
精华内容 16
关键字:

在一颗初始为空的