打印两个二分搜索法树的公共节点 开发文档-麻将胡了pg电子网站

原文:

给定两个二分搜索法树，在其中找到公共节点。换句话说，找到两个 bst 的交集。

例:

方法 1(简单解法)一种简单的方法是在第二棵树中逐个搜索第一棵树的每个节点。该方案的时间复杂度为 o(m * h)，其中 m 是第一棵树的节点数，h 是第二棵树的高度。

方法二 :

• approach–如果我们想到另一个问题，其中给我们两个排序数组，我们必须找到它们之间的交集，我们可以使用两个指针技术轻松地做到这一点。现在我们可以很容易地把这个问题转化为上面的问题。我们知道，如果我们将 bst 的有序遍历存储在一个数组中，该数组将按升序排序。所以我们能做的就是简单地对这两棵树进行有序遍历，并将它们存储在两个独立的数组中，然后找到两个数组之间的交集。
• 算法– 1)对第一棵树进行有序遍历，并将遍历结果存储在辅助数组 ar1[]中。参见此处的。

• complexity analysis:

  • 时间复杂度: o(m n)。 这里的‘m’和‘n’分别是第一棵树和第二棵树的节点数，因为我们需要遍历这两棵树。
  • 辅助空间:不使用任何数据结构来存储值-: o(m n) 原因是我们需要两个单独的数组来存储两棵树的有序遍历。

  方法 3(线性时间和有限的额外空间) 想法是使用

• 做法: 这里的思路是优化空间。在上面的方法中，我们存储树的所有元素，然后进行比较，但问题是真的有必要存储所有元素吗？我们可以做的是存储树的特定分支(最坏的情况是“树的高度”)，然后开始比较。我们可以取两个栈，在各自的栈中存储树的有序遍历，但是元素的最大数量应该等于树的特定分支。一旦分支结束，我们就开始弹出并比较堆栈的元素。现在如果top(stack-1)在 top(stack-1)的右分支中可以有更多的元素大于它并且可以等于 top(stack-2)。所以我们插入顶部(堆栈-1)的右分支，直到它等于空。在每个这样的插入结束时，我们有三个条件要检查，然后我们相应地在堆栈中进行插入。

  ``` if top(stack-1)right (then do insertions)

  if top(stack-1)>top(stack-2) root2=root2->right (then do insertions)

  else it's a match

  ```

  c

  ``` // c program of iterative traversal based method to // find common elements in two bsts.

  using namespace std;

  // a bst node struct node {     int key;     struct node left, right; };

  // a utility function to create a new node node newnode(int ele) {     node temp = new node;     temp->key = ele;     temp->left = temp->right = null;     return temp; }

  // function two print common elements in given two trees void printcommon(node root1, node root2) {     // create two stacks for two inorder traversals     stack stack1, s1, s2;

  while (1)     {         // push the nodes of first tree in stack s1         if (root1)         {             s1.push(root1);             root1 = root1->left;         }

  // push the nodes of second tree in stack s2         else if (root2)         {             s2.push(root2);             root2 = root2->left;         }

  // both root1 and root2 are null here         else if (!s1.empty() && !s2.empty())         {             root1 = s1.top();             root2 = s2.top();

  // if current keys in two trees are same             if (root1->key == root2->key)             {                 cout << root1->key << " ";                 s1.pop();                 s2.pop();

  // move to the inorder successor                 root1 = root1->right;                 root2 = root2->right;             }

  else if (root1->key < root2->key)             {                 // if node of first tree is smaller, than that of                 // second tree, then its obvious that the inorder                 // successors of current node can have same value                 // as that of the second tree node. thus, we pop                 // from s2                 s1.pop();                 root1 = root1->right;

  // root2 is set to null, because we need                 // new nodes of tree 1                 root2 = null;             }             else if (root1->key > root2->key)             {                 s2.pop();                 root2 = root2->right;                 root1 = null;             }         }

  // both roots and both stacks are empty         else  break;     } }

  // a utility function to do inorder traversal void inorder(struct node *root) {     if (root)     {         inorder(root->left);         coutright);     } }

  / a utility function to insert a new node with given key in bst / struct node insert(struct node node, int key) {     / if the tree is empty, return a new node /     if (node == null) return newnode(key);

  / otherwise, recur down the tree /     if (key < node->key)         node->left  = insert(node->left, key);     else if (key > node->key)         node->right = insert(node->right, key);

  / return the (unchanged) node pointer /     return node; }

  // driver program int main() {     // create first tree as shown in example     node *root1 = null;     root1 = insert(root1, 5);     root1 = insert(root1, 1);     root1 = insert(root1, 10);     root1 = insert(root1,  0);     root1 = insert(root1,  4);     root1 = insert(root1,  7);     root1 = insert(root1,  9);

  // create second tree as shown in example     node *root2 = null;     root2 = insert(root2, 10);     root2 = insert(root2, 7);     root2 = insert(root2, 20);     root2 = insert(root2, 4);     root2 = insert(root2, 9);

  cout << "tree 1 : ";     inorder(root1);     cout << endl;

  cout << "tree 2 : ";     inorder(root2);

  cout << "\ncommon nodes: ";     printcommon(root1, root2);

  return 0; } ```

  java 语言（一种计算机语言,尤用于创建网站)

  ``` // java program of iterative traversal based method to  // find common elements in two bsts. import java.util.*; class gfg { 

  // a bst node  static class node  {      int key;      node left, right;  }

  // a utility function to create a new node  static node newnode(int ele)  {      node temp = new node();      temp.key = ele;      temp.left = null;     temp.right = null;      return temp;  } 

  // function two print common elements in given two trees  static void printcommon(node root1, node root2)  { 

  stack s1 = new stack ();      stack s2 = new stack ();

  while (true)      {          // push the nodes of first tree in stack s1          if (root1 != null)          {              s1.push(root1);              root1 = root1.left;          } 

  // push the nodes of second tree in stack s2          else if (root2 != null)          {              s2.push(root2);              root2 = root2.left;          } 

  // both root1 and root2 are null here          else if (!s1.isempty() && !s2.isempty())          {              root1 = s1.peek();              root2 = s2.peek(); 

  // if current keys in two trees are same              if (root1.key == root2.key)              {                  system.out.print(root1.key " ");                  s1.pop();                  s2.pop(); 

  // move to the inorder successor                  root1 = root1.right;                  root2 = root2.right;              } 

  else if (root1.key < root2.key)              {                  // if node of first tree is smaller, than that of                  // second tree, then its obvious that the inorder                  // successors of current node can have same value                  // as that of the second tree node. thus, we pop                  // from s2                  s1.pop();                  root1 = root1.right; 

  // root2 is set to null, because we need                  // new nodes of tree 1                  root2 = null;              }              else if (root1.key > root2.key)              {                  s2.pop();                  root2 = root2.right;                  root1 = null;              }          } 

  // both roots and both stacks are empty          else break;      }  } 

  // a utility function to do inorder traversal  static void inorder(node root)  {      if (root != null)      {          inorder(root.left);          system.out.print(root.key " ");          inorder(root.right);      }  } 

  / a utility function to insert a new node with given key in bst / static node insert(node node, int key)  {      / if the tree is empty, return a new node /     if (node == null) return newnode(key); 

  / otherwise, recur down the tree /     if (key < node.key)          node.left = insert(node.left, key);      else if (key > node.key)          node.right = insert(node.right, key); 

  / return the (unchanged) node pointer /     return node;  } 

  // driver program  public static void main(string[] args)  {      // create first tree as shown in example      node root1 = null;      root1 = insert(root1, 5);      root1 = insert(root1, 1);      root1 = insert(root1, 10);      root1 = insert(root1, 0);      root1 = insert(root1, 4);      root1 = insert(root1, 7);      root1 = insert(root1, 9); 

  // create second tree as shown in example      node root2 = null;      root2 = insert(root2, 10);      root2 = insert(root2, 7);      root2 = insert(root2, 20);      root2 = insert(root2, 4);      root2 = insert(root2, 9); 

  system.out.print("tree 1 : " "\n");      inorder(root1);      system.out.println();     system.out.print("tree 2 : " "\n");      inorder(root2);      system.out.println();     system.out.println("common nodes: ");

  printcommon(root1, root2); 

  } }  ```

  python 3

  ```

  class newnode:     def init(self, key):         self.key = key         self.left = self.right = none

  def printcommon(root1, root2):

  # create two stacks for two inorder     # traversals      s1 = []     s2 = []

  while 1:

  # append the nodes of first          # tree in stack s1          if root1:             s1.append(root1)             root1 = root1.left

  # append the nodes of second tree         # in stack s2          elif root2:             s2.append(root2)             root2 = root2.left

  # both root1 and root2 are null here          elif len(s1) != 0 and len(s2) != 0:             root1 = s1[-1]              root2 = s2[-1] 

  # if current keys in two trees are same              if root1.key == root2.key:                 print(root1.key, end = " ")                 s1.pop(-1)                  s2.pop(-1)

  # move to the inorder successor                  root1 = root1.right                  root2 = root2.right

  elif root1.key < root2.key:

  # if node of first tree is smaller, than                  # that of second tree, then its obvious                  # that the inorder successors of current                  # node can have same value as that of the                  # second tree node. thus, we pop from s2                  s1.pop(-1)                 root1 = root1.right 

  # root2 is set to null, because we need                  # new nodes of tree 1                  root2 = none             elif root1.key > root2.key:                 s2.pop(-1)                 root2 = root2.right                  root1 = none

  # both roots and both stacks are empty          else:             break

  def inorder(root):     if root:         inorder(root.left)          print(root.key, end = " ")         inorder(root.right)

  def insert(node, key):

  # if the tree is empty, return a new node      if node == none:         return newnode(key) 

  # otherwise, recur down the tree      if key < node.key:          node.left = insert(node.left, key)      elif key > node.key:          node.right = insert(node.right, key)

  # return the (unchanged) node pointer      return node

  if name == 'main':

  # create first tree as shown in example      root1 = none     root1 = insert(root1, 5)      root1 = insert(root1, 1)      root1 = insert(root1, 10)      root1 = insert(root1, 0)      root1 = insert(root1, 4)      root1 = insert(root1, 7)      root1 = insert(root1, 9) 

  # create second tree as shown in example      root2 = none     root2 = insert(root2, 10)      root2 = insert(root2, 7)      root2 = insert(root2, 20)      root2 = insert(root2, 4)      root2 = insert(root2, 9)

  print("tree 1 : ")      inorder(root1)      print()

  print("tree 2 : ")     inorder(root2)     print()

  print("common nodes: ")      printcommon(root1, root2)

  ```

  c

  ``` using system; using system.collections.generic;

  // c# program of iterative traversal based method to  // find common elements in two bsts.  public class gfg {

  // a bst node  public class node {     public int key;     public node left, right; }

  // a utility function to create a new node  public static node newnode(int ele) {     node temp = new node();     temp.key = ele;     temp.left = null;     temp.right = null;     return temp; }

  // function two print common elements in given two trees  public static void printcommon(node root1, node root2) {     stack s1 = new stack ();     stack s2 = new stack ();

  while (true)     {         // push the nodes of first tree in stack s1          if (root1 != null)         {             s1.push(root1);             root1 = root1.left;         }

  // push the nodes of second tree in stack s2          else if (root2 != null)         {             s2.push(root2);             root2 = root2.left;         }

  // both root1 and root2 are null here          else if (s1.count > 0 && s2.count > 0)         {             root1 = s1.peek();             root2 = s2.peek();

  // if current keys in two trees are same              if (root1.key == root2.key)             {                 console.write(root1.key " ");                 s1.pop();                 s2.pop();

  // move to the inorder successor                  root1 = root1.right;                 root2 = root2.right;             }

  else if (root1.key < root2.key)             {                 // if node of first tree is smaller, than that of                  // second tree, then its obvious that the inorder                  // successors of current node can have same value                  // as that of the second tree node. thus, we pop                  // from s2                  s1.pop();                 root1 = root1.right;

  // root2 is set to null, because we need                  // new nodes of tree 1                  root2 = null;             }             else if (root1.key > root2.key)             {                 s2.pop();                 root2 = root2.right;                 root1 = null;             }         }

  // both roots and both stacks are empty          else         {             break;         }     } }

  // a utility function to do inorder traversal  public static void inorder(node root) {     if (root != null)     {         inorder(root.left);         console.write(root.key " ");         inorder(root.right);     } }

  / a utility function to insert a new node with given key in bst / public static node insert(node node, int key) {     / if the tree is empty, return a new node /     if (node == null)     {         return newnode(key);     }

  / otherwise, recur down the tree /     if (key < node.key)     {         node.left = insert(node.left, key);     }     else if (key > node.key)     {         node.right = insert(node.right, key);     }

  / return the (unchanged) node pointer /     return node; }

  // driver program  public static void main(string[] args) {     // create first tree as shown in example      node root1 = null;     root1 = insert(root1, 5);     root1 = insert(root1, 1);     root1 = insert(root1, 10);     root1 = insert(root1, 0);     root1 = insert(root1, 4);     root1 = insert(root1, 7);     root1 = insert(root1, 9);

  // create second tree as shown in example      node root2 = null;     root2 = insert(root2, 10);     root2 = insert(root2, 7);     root2 = insert(root2, 20);     root2 = insert(root2, 4);     root2 = insert(root2, 9);

  console.write("tree 1 : " "\n");      inorder(root1);      console.writeline();      console.write("tree 2 : " "\n");      inorder(root2);      console.writeline();      console.write("common nodes: " "\n"); 

  printcommon(root1, root2);

  } }

  // this code is contributed by shrikant13 ```

  输出:

  4 7 9 10

• complexity analysis:

  • 时间复杂度: o(n m)。 这里的‘m’和‘n’分别是第一棵树和第二棵树的节点数，因为我们需要遍历这两棵树。
  • 辅助空间:使用堆栈存储值，最多元素=“树的高度”:o(h1 h2)

  本文由 供稿。如果你发现任何不正确的地方，或者你想分享更多关于上面讨论的话题的信息，请写评论。