自学教程：C++ subtree函数代码示例

booledit_interface_rep::set_hybrid_footer (tree st) {  // WARNING: update edit_dynamic_rep::activate_hybrid when updating this  if (is_atomic (st))    if (is_func (subtree (et, path_up (tp, 2)), HYBRID, 1)) {      string msg;      // macro argument      string name= st->label;      path mp= search_upwards (MACRO);      if (!is_nil (mp)) {	tree mt= subtree (et, mp);	int i, n= N(mt)-1;	for (i=0; i<n; i++)	  if (mt[i] == name) {	    set_message (concat (kbd ("return"), ": insert argument ", name),			 "hybrid command");	    return true;	  }      }      // macro application      tree f= get_env_value (name);      if (drd->contains (name) && (f == UNINIT))	set_message (concat (kbd ("return"), ": insert primitive ", name),		     "hybrid command");      else if (is_func (f, MACRO) || is_func (f, XMACRO))	set_message (concat (kbd ("return"), ": insert macro ", name),		     "hybrid command");      else if (f != UNINIT)	set_message (concat (kbd ("return"), ": insert value ", name),		     "hybrid command");      else return false;      return true;    }  return false;}

pathedit_select_rep::selection_get_subtable (  int& row1, int& col1, int& row2, int& col2){  if (selection_active_table ()) {    path fp= ::table_search_format (et, common (start_p, end_p));    if (is_nil (fp)) return fp;    tree st= subtree (et, fp);    table_search_coordinates (st, tail (start_p, N(fp)), row1, col1);    table_search_coordinates (st, tail (end_p, N(fp)), row2, col2);    if (row1>row2) { int tmp= row1; row1= row2; row2= tmp; }    if (col1>col2) { int tmp= col1; col1= col2; col2= tmp; }    table_bound (fp, row1, col1, row2, col2);    return fp;  }  else if (selection_active_table (false)) {    path fp= ::table_search_format (et, common (start_p, end_p) * 0);    if (is_nil (fp)) return fp;    path p= fp;    tree st;    while (true) {      st= subtree (et, p);      if (is_func (st, TABLE) && N(st) > 0 && is_func (st[0], ROW)) break;      if (!is_func (st, TFORMAT)) return path ();      p= p * (N(st) - 1);    }    row1= 0; col1= 0;    row2= N(st)-1; col2= N(st[0])-1;    return fp;  }  else return path ();}

pathedit_cursor_rep::make_cursor_accessible (path p, bool forwards) {  //time_t t1= texmacs_time ();  path start_p= p;  bool inverse= false;  int old_mode= get_access_mode ();  if (get_init_string (MODE) == "src")    set_access_mode (DRD_ACCESS_SOURCE);  while (!is_accessible_cursor (et, p) && !in_source ()) {    path pp;    ASSERT (rp <= p, "path outside document");    p= rp * closest_inside (subtree (et, rp), p / rp);    if (forwards ^ inverse)      pp= rp * next_valid (subtree (et, rp), p / rp);    else      pp= rp * previous_valid (subtree (et, rp), p / rp);    if (pp == p) {      if (inverse) break;      else { p= start_p; inverse= true; }    }    else p= pp;  }  set_access_mode (old_mode);  //time_t t2= texmacs_time ();  //if (t2-t1 >= 1) cout << "made_cursor_accessible took " << t2-t1 << "ms/n";  return p;}

pathfind_subtable_selection (tree et, path p1, path p2,                         int& row1, int& col1, int& row2, int& col2) {  if (is_table_selection (et, p1, p2, true)) {    path fp= table_search_format (et, common (p1, p2));    if (is_nil (fp)) return fp;    tree st= subtree (et, fp);    table_search_coordinates (st, tail (p1, N(fp)), row1, col1);    table_search_coordinates (st, tail (p2, N(fp)), row2, col2);    if (row1>row2) { int tmp= row1; row1= row2; row2= tmp; }    if (col1>col2) { int tmp= col1; col1= col2; col2= tmp; }    // table_bound (fp, row1, col1, row2, col2);    // FIXME: table editing routines should be moved to src/Data/Tree    return fp;  }  else if (is_table_selection (et, p1, p2, false)) {    path fp= table_search_format (et, common (p1, p2) * 0);    if (is_nil (fp)) return fp;    path p= fp;    tree st;    while (true) {      st= subtree (et, p);      if (is_func (st, TABLE) && N(st) > 0 && is_func (st[0], ROW)) break;      if (!is_func (st, TFORMAT)) return path ();      p= p * (N(st) - 1);    }    row1= 0; col1= 0;    row2= N(st)-1; col2= N(st[0])-1;    return fp;  }  else return path ();}

static pathtable_search_format (tree t, path p) {  tree st= subtree (t, p);  if (is_func (st, TFORMAT) && is_func (st[N(st)-1], TABLE)) return p;  while ((!is_nil (p)) && (!is_func (subtree (t, p), TABLE))) p= path_up (p);  if ((!is_nil (p)) && (is_func (subtree (t, path_up (p)), TFORMAT)))    p= path_up (p);  return p;}

int subtree(tree *t1,tree *t2){	if(t1==NULL)		return 0;	if(t1->element==t2->element)		if(match_tree(t1,t2))			return 1;	return subtree(t1->left,t2)||subtree(t1->right,t2);}

// check if node2 tree is subtree of node1 treebool subtree(treeNode *node1, treeNode *node2){	if(node1 == NULL){		return false; // tree1 is empty	}	else if(node1->data == node2->data){		return matchTree(node1, node2);	}	else{		return subtree(node1->left, node2) || subtree(node1->right, node2);	}}

edit_main_rep::edit_main_rep (server_rep* sv, tm_buffer buf):  editor_rep (sv, buf), props (UNKNOWN), ed_obs (edit_observer (this)){#ifdef EXPERIMENTAL  cct= copy (subtree (et, rp));  copy_ip (subtree (et, rp), cct);#endif  attach_observer (subtree (et, rp), ed_obs);  notify_change (THE_TREE);  tp= correct_cursor (et, rp * 0);}

booladmissible_selection (gr_selection sel) {  if (sel->type != "box" || N(sel->cp) != 1) return true;  if (last_item (sel->cp[0]) < 0 || N(sel->cp[0]) <= 2) return true;  path p= path_up (sel->cp[0]);  if (!has_subtree (the_et, p)) return true;  tree st= subtree (the_et, p);  if (is_compound (st, "anim-edit")) return false;  tree pt= subtree (the_et, path_up (p));  if (is_func (st, WITH) && is_compound (pt, "anim-edit")) return false;  return true;}

bool subtree(Node<T> *a, Node<T> *b){    if (!a)        return false;    if (a->data == b->data)    {        if (matchTree(a, b))            return true;    }    return subtree(a->left, b) || subtree(a->right, b);}

AlnusPhyolgeticBranch*AlnusNewickParser::descendants(){    AlnusPhyolgeticBranch *branch = new AlnusPhyolgeticBranch;    AlnusPhyolgeticBranch *childBranch = subtree();    branch->addChild(childBranch);    while (mOperator == Operator::COMMA) {        next();        childBranch = subtree();        branch->addChild(childBranch);    }    return branch;}

void subtree(int *n, int *merge, int *node, int *pknode, int *pktree){  int i,j,k,temp,length,temp1,temp2, nn;  int *letree, *ritree;  int *lenode, *rinode;  temp=*node;  length=*n;      letree=(int *)malloc((length+1)*sizeof(int));  ritree=(int *)malloc((length+1)*sizeof(int));  lenode=(int *)malloc(length*sizeof(int));  rinode=(int *)malloc(length*sizeof(int));    nn=length+1;  i=temp-1;  temp1=*(merge+i);  j=length+i;  temp2=*(merge+j);  for(i=0;i<nn;i++)    {      letree[i]=0;      ritree[i]=0;    }  for(j=0;j<length;j++)    {      lenode[j]=0;      rinode[j]=0;    }    if(temp1<0)     pktree[-temp1-1]=1;  else    {    subtree(n, merge, &temp1, lenode, letree);    OrVector(n,lenode, pknode);    OrVector(&nn, letree, pktree);    }  if(temp2<0)     pktree[-temp2-1]=1;  else    {    subtree(n, merge, &temp2, rinode, ritree);    OrVector(n,rinode, pknode);    OrVector(&nn, ritree, pktree);    }  *(pknode+temp-1)=1;}

booledit_interface_rep::set_latex_footer (tree st) {  if (is_atomic (st))     if (is_func (subtree (et, path_up (tp, 2)), LATEX, 1) ||	is_func (subtree (et, path_up (tp, 2)), HYBRID, 1)) {      string s= st->label;      string help;      command cmd;      if (sv->kbd_get_command (s, help, cmd)) {	set_left_footer (concat (kbd ("return"), ": " * help));	set_right_footer ("latex command");	return true;      }    }  return false;}

void Path::moveLeft(unsigned Level) {  assert(Level != 0 && "Cannot move the root node");  // Go up the tree until we can go left.  unsigned l = 0;  if (valid()) {    l = Level - 1;    while (path[l].offset == 0) {      assert(l != 0 && "Cannot move beyond begin()");      --l;    }  } else if (height() < Level)    // end() may have created a height=0 path.    path.resize(Level + 1, Entry(nullptr, 0, 0));  // NR is the subtree containing our left sibling.  --path[l].offset;  NodeRef NR = subtree(l);  // Get the rightmost node in the subtree.  for (++l; l != Level; ++l) {    path[l] = Entry(NR, NR.size() - 1);    NR = NR.subtree(NR.size() - 1);  }  path[l] = Entry(NR, NR.size() - 1);}

booledit_interface_rep::complete_try () {  tree st= subtree (et, path_up (tp));  if (is_compound (st)) return false;  string s= st->label, ss;  int end= last_item (tp);  array<string> a;  if (inside (LABEL) || inside (REFERENCE) || inside (PAGEREF)) {    if (end != N(s)) return false;    ss= copy (s);    tree t= get_labels ();    int i, n= N(t);    for (i=0; i<n; i++)      if (is_atomic (t[i]) && starts (t[i]->label, s))	a << string (t[i]->label (N(s), N(t[i]->label)));  }  else {    if ((end==0) || (!is_iso_alpha (s[end-1])) ||	((end!=N(s)) && is_iso_alpha (s[end]))) return false;    int start= end-1;    while ((start>0) && is_iso_alpha (s[start-1])) start--;    ss= s (start, end);    a= find_completions (drd, et, ss);  }  if (N(a) == 0) return false;  complete_start (ss, a);  return true;}

voidedit_process_rep::generate_aux (string which) {  // path saved_path= tp;  generate_aux_recursively (which, subtree (et, rp), rp);  // if (which == "") go_to (saved_path);  // ... may be problematic if cursor was inside regenerated content}

voidedit_select_rep::select (path p1, path p2) {  //cout << "Select " << p1 << " -- " << p2 << "/n";  if (start_p == p1 && end_p == p2) return;  if (!(rp <= p1 && rp <= p2)) return;  if (start_p == end_p && p1 == p2) {    start_p= copy (p1);    end_p  = copy (p2);    return;  }  if (p1 != p2) {    path cp= common (p1, p2);    tree st= subtree (et, cp);    if (!is_func (st, TABLE) && !is_func (st, ROW))      (void) semantic_select (cp, p1, p2, 0);  }  if (path_less (p1, p2)) {    start_p= copy (p1);    end_p  = copy (p2);  }  else {    start_p= copy (p2);    end_p  = copy (p1);  }  notify_change (THE_SELECTION);}

voidedit_typeset_rep::typeset_invalidate_all () {  //cout << "Invalidate all/n";  notify_change (THE_ENVIRONMENT);  typeset_preamble ();  ::notify_assign (ttt, path(), subtree (et, rp));}

bool isSubtree(Tree<T> &a, Tree<T> &b){    if (!b.root)        return true;    return subtree(a.root, b.root);}

booljoin (modification& m1, modification m2, tree t) {  if (m1->k == MOD_INSERT &&      m2->k == MOD_INSERT &&      is_atomic (m1->t) &&      root (m1) == root (m2) &&      (index (m2) == index (m1) ||       index (m2) == index (m1) + N (m1->t->label)))    {      string s= m1->t->label * m2->t->label;      if (index (m2) == index (m1))	s= m2->t->label * m1->t->label;      m1= mod_insert (root (m1), index (m1), tree (s));      return true;    }  if (m1->k == MOD_REMOVE &&      m2->k == MOD_REMOVE &&      is_atomic (subtree (t, root (m1))) &&      root (m1) == root (m2) &&      (index (m1) == index (m2) ||       index (m1) == index (m2) + argument (m2)))    {      m1= mod_remove (root (m2), index (m2),		      argument (m1) + argument (m2));      return true;    }  return false;}

voidedit_select_rep::selection_get (selection& sel) {  if (selection_active_table ()) {    int row1, col1, row2, col2;    path fp= selection_get_subtable (row1, col1, row2, col2);    tree st= subtree (et, fp);    int i, j;    rectangle r (0, 0, 0, 0);    for (i=row1; i<=row2; i++)      for (j=col1; j<=col2; j++) {	path cp= fp * ::table_search_cell (st, i, j);	sel= eb->find_check_selection (cp * 0, cp * 1);	if (sel->valid) {	  rectangles rs= sel->rs;	  if (r != rectangle (0, 0, 0, 0)) rs= rectangles (r, rs);	  r= least_upper_bound (rs);	}      }    sel= selection (rectangles (r), fp * 0, fp * 1);  }  else {    path p_start, p_end;    //cout << "Find " << start_p << " -- " << end_p << "/n";    selection_correct (start_p, end_p, p_start, p_end);    //cout << "Find " << p_start << " -- " << p_end << "/n";    sel= eb->find_check_selection (p_start, p_end);    //cout << "sel= " << sel << "/n";  }}

voidedit_typeset_rep::typeset_sub (SI& x1, SI& y1, SI& x2, SI& y2) {  //time_t t1= texmacs_time ();  typeset_prepare ();  eb= empty_box (reverse (rp));  // saves memory, also necessary for change_log update  bench_start ("typeset");#ifdef USE_EXCEPTIONS  try {#endif    eb= ::typeset (ttt, x1, y1, x2, y2);#ifdef USE_EXCEPTIONS  }  catch (string msg) {    the_exception= msg;    std_error << "Typesetting failure, resetting to empty document/n";    assign (rp, tree (DOCUMENT, ""));    ::notify_assign (ttt, path(), subtree (et, rp));    eb= ::typeset (ttt, x1, y1, x2, y2);      }  handle_exceptions ();#endif  bench_end ("typeset");  //time_t t2= texmacs_time ();  //if (t2 - t1 >= 10) cout << "typeset took " << t2-t1 << "ms/n";  picture_cache_clean ();}

booledit_interface_rep::complete_keypress (string key) {  set_message ("", "");  if (key == "space") key= " ";  if ((key != "tab") && (key != "S-tab")) {    set_input_normal (); return false; }  tree st= subtree (et, path_up (tp));  if (is_compound (st)) {    set_input_normal (); return false; }  string s= st->label;  int end= last_item (tp);  string old_s= completions [completion_pos];  string test= completion_prefix * old_s;  if ((end<N(test)) || (s (end-N(test), end) != test)) {    set_input_normal (); return false; }  if (key == "tab") completion_pos++;  else completion_pos--;  if (completion_pos < 0) completion_pos= N(completions)-1;  if (completion_pos >= N(completions)) completion_pos= 0;  string new_s= completions [completion_pos];  remove (path_up (tp) * (end-N(old_s)), N(old_s));  insert (path_up (tp) * (end-N(old_s)), new_s);  complete_message ();  return true;}

AlnusPhyolgeticTree* AlnusNewickParser::parse(){    AlnusPhyolgeticTree *t = tree();    AlnusPhyolgeticBranch *root = subtree();    t->setRoot(root);    return t;}

voidnotify_remove_node (typesetter ttt, path p) {  // cout << "Remove node " << p << "/n";  tree t= subtree (ttt->br->st, p);  if (is_nil (path_up (p))) ttt->br= make_bridge (ttt, t, ttt->br->ip);  else ttt->br->notify_assign (path_up (p), t);}

boolhas_player (path ip) {  path p= reverse (ip);  if (!has_subtree (the_et, p)) return false;  tree t= subtree (the_et, p);  blackbox bb;  return t->obs->get_contents (ADDENDUM_PLAYER, bb);}

voidedit_graphics_rep::back_in_text_at (tree t, path p, bool forward) {  (void) forward;  int i= last_item (p);  if ((i == 0) && is_empty (t[0])) {    p= path_up (p);    if (is_func (subtree (et, path_up (p)), WITH)) p= path_up (p);    tree st= subtree (et, path_up (p));    if (is_func (st, GRAPHICS)) {      if (N(st) == 1) assign (p, "");      else {        remove (p, 1);        go_to_border (path_up (p) * 0, true);      }    }  }}

bool containsTree(treeNode *node1, treeNode *node2){	if(node2 == NULL){		return true;	}	else{		return subtree(node1, node2);	}}