关键词:
1.指针实现
#include <iostream> #include <vector> #include <queue> #include <cstdio> #include <cstring> using namespace std; #define maxn 100 struct Node { bool have_value; int value; /*节点结构体*/ Node *left,*right; Node():have_value(false),left(NULL),right(NULL){} }; /*全局变量写起来更方便*/ char s[maxn]; Node* root=NULL; bool faile; /*用来防止内存泄漏*/ void remove_tree(Node* tree) { if(tree==NULL) return; remove_tree(tree->left); remove_tree(tree->right); delete tree; } /*创建新节点封装成函数*/ Node* newnode() { return new Node();} /*添加新节点的函数*/ void addnode(int v,char* s) { int n=strlen(s); Node* u=root; for(int i=0;i<n;i++) { if(s[i]==‘L‘) { if(u->left==NULL) u->left=newnode(); u=u->left; } else if(s[i]==‘R‘) { if(u->right==NULL) u->right=newnode(); u=u->right; } } if(u->have_value) faile=true; u->value=v; u->have_value=true; } /*读入数据并创建树,成功返回true读到文件结尾则返回false*/ bool read_input() { faile=false; remove_tree(root); root=newnode(); for(;;) { if(scanf("%s",s)!=1) return false; if(!strcmp(s,"()")) break; int v; sscanf(&s[1],"%d",&v); addnode(v,strchr(s,‘,‘)+1); } return true; } /*宽度优先算法,用队列实现将结果存在向量中*/ bool bfs(vector<int>& ans) { queue<Node*> q; ans.clear(); q.push(root); while(!q.empty()) { Node* u=q.front(); q.pop(); if(!u->have_value) return false; ans.push_back(u->value); if(u->left!=NULL) q.push(u->left); if(u->right!=NULL) q.push(u->right); } return true; } int main() { vector<int> v; while(read_input()) { if(!bfs(v) || faile==true) printf("%d ",-1); else for(vector<int>::iterator i = v.begin(); i != v.end(); ++i) printf("%d ",*i); cout<<endl; } }
2.数组实现
#include <iostream> #include <vector> #include <queue> #include <cstdio> #include <cstring> using namespace std; #define maxn 1000 bool have_value[maxn]; int tleft[maxn]; int tright[maxn]; int value[maxn]; char s[100]; bool faile; const int root=1; int cnt; void newtree() { tleft[root]=0; tright[root]=0; have_value[root]=false; cnt=root; } int newnode() { int u=++cnt; tleft[u]=0; tright[u]=0; have_value[u]=false; return u; } void addnode(int v,char* s) { int n=strlen(s); int u=root; for(int i=0;i<n;i++) { if(s[i]==‘L‘) { if(tleft[u]==0) tleft[u]=newnode(); u=tleft[u]; } else if(s[i]==‘R‘) { if(tright[u]==0) tright[u]=newnode(); u=tright[u]; } } if(have_value[u]) faile=true; value[u]=v; have_value[u]=true; } bool read_input() { faile=false; newtree(); for(;;) { if(scanf("%s",s)!=1) return false; if(!strcmp(s,"()")) break; int v; sscanf(&s[1],"%d",&v); addnode(v,strchr(s,‘,‘)+1); } return true; } bool bfs(vector<int>& ans) { queue<int> q; ans.clear(); q.push(root); while(!q.empty()) { int u=q.front(); q.pop(); if(!have_value[u]) return false; ans.push_back(value[u]); if(tleft[u]!=0) q.push(tleft[u]); if(tright[u]!=0) q.push(tright[u]); } return true; } int main() { vector<int> v; while(read_input()) { if(!bfs(v) || faile==true) printf("%d ",-1); else for(vector<int>::iterator i = v.begin(); i != v.end(); ++i) printf("%d ",*i); cout<<endl; } }
书上的接口写的太棒了,换了种实现方式,代码基本上没改,比我自己写的接口不知道高到哪里去了.
数据结构与算法(周鹏-未出版)-第六章树-6.3二叉树基本操作的实现
6.3二叉树基本操作的实现 二叉树的基本操作在6.2.1小节中已经定义,在这些操作中有一组非常重要的操作就是遍历操作,下面首先介绍遍历及其实现,然后介绍其他操作的实现。 在以下操作的实现中涉及了实现二叉树的B... 查看详情
数据结构与算法(周鹏-未出版)-第六章树-6.2二叉树
6.2二叉树在进一步讨论树的存储结构及其操作之前,先讨论一种简单而极其重要的树结构—二叉树。因为任何树都可以转化为二叉树进行处理,并且二叉树适合计算机的存储和处理,因此在本章中二叉树是研究的重点。 6.2.1... 查看详情
第六章二叉树算法入门经典结构体指针
运行效果图结构体指针实现#include<stdio.h>#include<stdlib.h>#include<string.h>#defineN10000intfailed,n,v,ans[N];chars[N];//保存读入结点typedefstructNode//结点类型{ intflag;//是否被赋值过 intnumber;//结点值 structNo 查看详情
数据结构与算法(周鹏-未出版)-第六章树-习题
①二叉树是不是树的特殊情况?答:不是!虽然二叉树也属于一种树结构,但它是另外单独定义的一种树,并非一般树的特例。它的子树有顺序规定,分为左子树和右子树。不能随意颠倒。②:满二叉树和完全二叉树有什么区别... 查看详情
第六章总结--图
这两个星期,说实话没有好好用功,惭愧无比。图,不同于先前学过的数据结构,它是一种非线性的结构,即可以一对多或者多对多。存储方式主要有邻接矩阵和邻接表。邻接矩阵主要是用一个一维数组和一个二维数组分别存储... 查看详情
二叉树的层次遍历ii
二叉树的层次遍历II 给出一棵二叉树,返回其节点值从底向上的层次序遍历(按从叶节点所在层到根节点所在的层遍历,然后逐层从左往右遍历)样例给出一棵二叉树 {3,9,20,#,#,15,7},3/920/157按照从下往上的层次遍历为:[[15... 查看详情
1040.二叉树层次遍历
Description给出一棵二叉树,求它的层次遍历结果。[二叉树的遍历问题是一种精神,务必领会]InputFormat第一行,N<1000000,表示二叉树节点数。默认序号为0的节点为树根。接下来共N-1行,依次表示序号为1,...,N-1的节点的父亲节... 查看详情
层次遍历二叉树
层次遍历二叉树,编程之美上看过解法,然后在练习了一下。用递归和vector,队列实现了,然后加上了测试函数,测试函数的二叉树创建方法待改进。//有一棵二叉树,请设计一个算法,按照层次打印这棵二叉树... 查看详情
重建二叉树与二叉树的层次遍历
数据结构实验之求二叉树后序遍历和层次遍历TimeLimit:1000ms Memorylimit:65536K 有疑问?点这里^_^题目描写叙述已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历。输入输入数据有多组,第一行是一个整数t(t<1... 查看详情
利用层次遍历原理构建二叉树(代码片段)
层次遍历构建二叉树:1.定义二叉树节点:1functionTreeNode(val)2this.val=val;3this.left=this.right=null;42.层次遍历构建二叉树:1functioncreateTree(arr)2if(!arr||!arr.length)returnnull;3varroot=newTreeNode(arr.shift());4varlist=[ 查看详情
二叉树的层次遍历(代码片段)
题目 :给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。例如:给定二叉树: [3,9,20,null,null,15,7],3/920/157返回其层次遍历结果:[[3],[9,20],[15,7]]思路分析:因为需要按层次遍历节点,所以... 查看详情
从底向上层次遍历二叉树
题目原型: Givenabinarytree,returnthebottom-uplevelordertraversalofitsnodes‘values.(ie,fromlefttoright,levelbylevelfromleaftoroot).Forexample:Givenbinarytree{3,9,20,#,#,15,7},?12345 3 查看详情
第五章 二叉树(e4)层次遍历
102binarytreelevelordertraversal二叉树的层次遍历
给定一个二叉树,返回其按层次遍历的节点值。(即zhu‘ceng‘de,从左到右访问)。例如:给定二叉树:[3,9,20,null,null,15,7], 3 /\ 9 20 / \ 15 7返回其层次遍历结果为:[ [... 查看详情
102.二叉树的层次遍历(代码片段)
给定一个二叉树,返回其按层次遍历的节点值。(即逐层地,从左到右访问所有节点)。例如:给定二叉树: [3,9,20,null,null,15,7],3/920/157返回其层次遍历结果:[[3],[9,20],[15,7]]vector<vector<int>>levelOrder(TreeNode*root)//數據結構... 查看详情
树——二叉树的层次遍历(代码片段)
1,二叉树的遍历: 1,二叉树的遍历(TraversingBinaryTree)是指从根结点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次,且仅被访问一次; &n... 查看详情
lintcode69.二叉树的层次遍历
题目:给出一棵二叉树,返回其节点值的层次遍历(逐层从左往右访问) 样例给一棵二叉树 {3,9,20,#,#,15,7} :3/920/157返回他的分层遍历结果:[[3],[9,20],[15,7]]挑战 挑战1:只使用一个队列去实现它挑战2:用DFS算法来... 查看详情
二叉树前中后层次遍历(代码片段)
#include<iostream>#include<stack>#include<queue>usingnamespacestd;/*二叉树遍历算法递归+非递归:前序遍历:根->左->右中序遍历:左->根->右后序遍历:左->右->根层次遍历*/structTreeNodeintval;TreeNode*lef 查看详情