C＃将节点添加到堆栈（BST预订） [英] C# Adding nodes to a stack (BST Pre-order)

问题描述

我有一个二叉搜索树，我想以正确的顺序打印数据。要做到这一点，我需要使用一个堆栈（如果我想给自己带来更多的麻烦，我可以用队列来做）。



所以，每个节点有两个孩子，左边和右边放置另一个节点。我的问题是当两个节点放在父节点下面。我需要它们以正确的顺序打印，即



root

firstlvl firstlvl

seclvl seclvl seclvl seclvl

3rdlvl 3rdlvl等等..



现在它会优先考虑我相信的左手边（未经测试）。

节点dataTempNode，depthNode; 
  private   int  depth =  0 ; 
  string  printData =  ; 
  public   void  PrintTransverse（）
 {
  if （depth ==  0 ）
 {
 dataTempNode = root; 
 printData =   root \t + dataTempNode。值的ToString（）; 
 depth ++; 
} 
  if （dataTempNode.right ==  null &&& dataTempNode .left！=  null ）
 {
 dataTempNode = dataTempNode.left; 
 printData + =   \ n Left \t + dataTempNode。值的ToString（）; 
 depth ++; 
  if （depthNode ==  null  || depthNode.depth ==  0  || dataTempNode.left！=  null  || dataTempNode.right！=  null ）
 {
 PrintTransverse（）; 
  return ; 
} 
  return ; 
 
} 
  if （dataTempNode.left ==  null & ;& dataTempNode.right！=  null ）
 {
 dataTempNode = dataTempNode.right; 
 printData + =   \ n Right \t + dataTempNode。值的ToString（）; 
 depth ++; 
  if （depthNode ==  null  || depthNode.depth ==  0  || dataTempNode.left！=  null  || dataTempNode.right！=  null ）
 {
 PrintTransverse（）; 
  return ; 
} 
  return ; 
} 
  if （dataTempNode.left！=  null &&& dataTempNode .right！=  null && dataTempNode.depth ==  0 ）
 {
 depthNode = dataTempNode; 
 depthNode.depth = depth; 
 printData + =   \ n低于两行=同一级别; 
 dataTempNode = dataTempNode.left; 
 PrintTransverse（）; 
  if （printData.Contains（  end ））
 {
  return ; 
} 
 dataTempNode = depthNode; 
 dataTempNode.depth =  0 ; 
 depthNode.depth =  0 ; 
 
  //   right  
 
 dataTempNode = depthNode 。对; 
 PrintTransverse（）; 
  if （printData.Contains（  end ））
 {
  return ; 
} 
 dataTempNode = depthNode; 
 dataTempNode.depth =  0 ; 
 depthNode.depth =  0 ; 
 
 
 depth ++; 
  if （dataTempNode.left ==  null && dataTempNode.right == < span class =code-keyword> null ）
 {
  return ; 
} 
 
} 
  if （dataTempNode.left ==  null && dataTempNode.right ==  null ）
 {
 
 Console.WriteLine（printData）; 
 printData + =   end; 
  return ; 
} 
  else  
 {
 PrintTransverse（）; 
} 
} 

解决方案

参考谢尔盖的回答，我建议阅读这篇文章：使用C＃2.0对数据结构进行广泛的检查 [ ^ ]

原始树没有堆栈或队列都没有提供您需要的订单。是不是很明显？



基本上，你描绘的结构也是一棵树，有两个层次，一个代表深度，另一个代表相同深度的节点代表他们的父母无关紧要。您将此分支表示为文本表示中的行。可以表示为节点列表的列表，例如 System.Collections.Generic.List< System.Collections.Generic.List< Node>> 。



要填充此类结构，您可以使用不同的方法。请参阅： http://en.wikipedia.org/wiki/Binary_tree#Breadth-first_order [< a href =http://en.wikipedia.org/wiki/Binary_tree#Breadth-first_ordertarget =_ blanktitle =New Window> ^ ]。



您还可以考虑遍历原始树并立即打印节点，而无需中间结构。我解释了这个结构只是为了引起你注意问题的根本原因。


顺便说一下，每个节点有两个孩子并不完全正确。其中一些可以为空。您不会将它们检查为null。在你的方法中，你应该在所有调用 AddToStack 之前检查它，或者更好的是，在这个方法本身，在一开始。







顺便说一下，您应该明白，您所做的转换意味着信息丢失（请参见上文）。您的节点之间的关系会丢失。我会考虑更好的打印数据显示，这实际上是在这里和那里完成的。

-SA

Hi,

I have a binary search tree that I would like to print the data in the correct order. To do this I need to use a stack (well I could do it with a queue if I want to give myself more of a headache).

So, each node has two children, the left and right of it where another node is placed. My problem is when two nodes are placed below the parent. I need them to be print in the correct order i.e.

root
firstlvl firstlvl
seclvl seclvl seclvl seclvl
3rdlvl 3rdlvl and so on..

Right now it'll prioritize the left hand side I believe (not tested).

Node dataTempNode, depthNode;
        private int depth = 0;
        string printData = "";
        public void PrintTransverse()
        {
            if (depth == 0)
            {
                dataTempNode = root;
                printData = "root \t " + dataTempNode.value.ToString();
                depth++;
            }
            if (dataTempNode.right == null && dataTempNode.left != null)
            {
                dataTempNode = dataTempNode.left;
                printData += " \n Left \t " + dataTempNode.value.ToString();
                depth++;
                if (depthNode == null || depthNode.depth == 0 || dataTempNode.left != null || dataTempNode.right != null)
                {
                    PrintTransverse(); 
                    return;
                }
                return;

            }
            if (dataTempNode.left == null && dataTempNode.right != null)
            {
                dataTempNode = dataTempNode.right;
                printData += " \n Right \t " + dataTempNode.value.ToString();
                depth++;
                if (depthNode == null || depthNode.depth == 0 || dataTempNode.left != null || dataTempNode.right != null)
                {
                    PrintTransverse();
                    return;
                }
                return;
            }
            if (dataTempNode.left != null && dataTempNode.right != null && dataTempNode.depth == 0)
            {
                depthNode = dataTempNode;
                depthNode.depth = depth;
                printData += "\n below two lines = same level";
                dataTempNode = dataTempNode.left;
                PrintTransverse();
                if (printData.Contains("end"))
                {
                    return;
                }
                dataTempNode = depthNode;
                dataTempNode.depth = 0;
                depthNode.depth = 0;

                //right

                dataTempNode = depthNode.right;
                PrintTransverse();
                if (printData.Contains("end"))
                {
                    return;
                }
                dataTempNode = depthNode;
                dataTempNode.depth = 0;
                depthNode.depth = 0;


                depth++;
                if (dataTempNode.left == null && dataTempNode.right == null)
                {
                    return;
                }

            }
            if (dataTempNode.left == null && dataTempNode.right == null)
            {

                Console.WriteLine(printData);
                printData += "end";
                return;
            }
            else
            {
                PrintTransverse();
            }
        }

解决方案

With reference of Sergey's answer, i would suggest to read this article: An Extensive Examination of Data Structures Using C# 2.0 [^]

Neither original tree no stack or queue provide the order you require. Isn't that obvious?

Essentially, the structure you depicted is also a tree, with two levels, one representing depth, and other one the nodes of the same depth represented without concern to their parent. You represent this branch as the line in your text representation. At can be represented as a list of the list of nodes, for example System.Collections.Generic.List<System.Collections.Generic.List<Node>>.

To populate such structure, you can use different approaches. Please see: http://en.wikipedia.org/wiki/Binary_tree#Breadth-first_order[^].

You can also think about traversal of your original tree and printing nodes right away, without intermediate structure. I explained that structure just to bring to your attention the root cause of your problem.

By the way, "each node has two children" is not quite correct. Some of them can be null. You don't check up them for null. In your method, you should either check it up before all calls to AddToStack, or, better, in this method itself, in the very beginning.

[EDIT]

By the way, you should understand that the conversion you do means loss of information (please see above). Your relationship between nodes gets lost. I would think about better printed presentation of the data, which is actually done here and there.

—SA

这篇关于C＃将节点添加到堆栈（BST预订）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！