不要将重复的值添加到Python中的二叉树(非二叉搜索树)。

huangapple go评论78阅读模式
英文:

Not to add duplicate values to Binary tree in python (not BST)

问题

我正在尝试从值数组创建二叉树。如果发现重复值,我不希望将重复项添加到树中,而是需要增加现有节点的计数器。

class eNode:
    def __init__(self, data):
        self.data = data 
        self.left = self.right = None
        self.Counter = 1
    def __str__(self):
        return str(self.data) + " Counter: " + str(self.Counter)

def insertLevelOrder(arr, root, i, n):
    if i < n:
        temp = eNode(arr[i])
        root = temp
        
        root.left = insertLevelOrder(arr, root.left, 
                                    2 * i + 1, n)
        root.right = insertLevelOrder(arr, root.right, 
                                    2 * i + 2, n)    
    return root

def main():
    empList = [1, 2, 2, 3, 5]
    n = len(empList) 
    root = None
    root = insertLevelOrder(empList, root, 0, n)
    print (root);
    print (root.left);
    print (root.right);
    print (root.left.left);
    print (root.left.right);
    #inOrder(root)
                

main()

是否有方法可以实现这个?所有的帮助都将不胜感激。

英文:

I am trying to create a binary tree from an array of values. I dont want to add a duplicate entry to the tree, if a duplicate value is found, I need to increment the counter of existing node.

class eNode: 
	def __init__(self, data):
		self.data = data 
		self.left = self.right = None
		self.Counter = 1
	def __str__(self):
		return str(self.data) + &quot; Counter: &quot; + str(self.Counter)
def insertLevelOrder(arr, root, i, n):
	if i &lt; n:
		temp = eNode(arr[i])
		root = temp
		
		root.left = insertLevelOrder(arr, root.left, 
									2 * i + 1, n)
		root.right = insertLevelOrder(arr, root.right, 
									2 * i + 2, n)	
	return root

def main():
	empList = [1, 2, 2, 3, 5]
	n = len(empList) 
	root = None
	root = insertLevelOrder(empList, root, 0, n)
	print (root);
	print (root.left);
	print (root.right);
	print (root.left.left);
	print (root.left.right);
	#inOrder(root)
				

main()

Is there a way to achieve this ? all helps are appreciated.

答案1

得分: 1

由于您的树构建算法将一个值分配给树中的一个特定位置,该位置仅取决于输入数组中的索引,所以当某些值不成为树中的节点(但会增加其他节点的计数器)时,就会出现问题:

该值的潜在子节点将成为孤立节点。

以以下示例为例:

[1, 2, 2, 3, 5, 6]

如果不对重复值进行任何特殊处理,将产生以下树:

     1
   /   \
  2     2
 / \   / 
3   5 6

6 最终位于第三层,位于第3个位置,这完全由于该值在输入数组中出现在索引5处(从零开始索引),而没有其他因素。如果我们不为第二个2创建节点,我们将得到一个孤立的6:

     1
   /   
  2     
 / \    
3   5 6

解决此问题的一种方法是同意原始输入数组中的索引不再定义节点的位置,树将变为:

     1
   /   \
  2*    3
 / \    
5   6

...其中星号表示计数为2。请注意,这是一棵完全不同的树。例如,现在3是1的直接子节点,仅因为有重复的2...

如果这是您希望的工作方式,请将算法更改为迭代而不是递归,并跟踪任何新创建节点的父节点是什么:

class eNode: 
    def __init__(self, data):
        self.data = data 
        self.left = self.right = None
        self.counter = 1
        
    def __str__(self):
        return str(self.data) + " Counter: " + str(self.counter)

def insertLevelOrder(arr):
    if arr == []:
        return
    root = eNode(arr[0])
    nodes = [root]
    d = {root.data: root}
    right = False
    parent = 0
    for val in arr[1:]:
        if val in d:
            d[val].counter += 1
        else:
            node = eNode(val)
            nodes.append(node)
            d[val] = node    
            if right:
                nodes[parent].right = node
                parent += 1
            else:
                nodes[parent].left = node
            right = not right
    return root

def main():
    empList = [1, 2, 2, 3, 5]
    root = insertLevelOrder(empList)
    print (root);
    print (root.left);
    print (root.right);
    print (root.left.left);
    print (root.left.right);

main()
英文:

Since your tree building algorithm assigns a value to a specific location in the tree, that only depends on the index in the input array, it becomes a problem when certain values would not become a node in a tree (but would increment a counter of some other node):

The would-be children of that value will be orphaned.

Take the example:

[1, 2, 2, 3, 5, 6]

Without any special treatment for duplicates, this produces the following tree:

     1
   /   \
  2     2
 / \   / 
3   5 6

The fact that 6 ends up on the third level, at the 3<sup>rd</sup> place, is completely determined by the fact that this value occurs at index 5 in the input array (zero-based indexing), and nothing else. If we would not create the node for the second 2, we would get an orphaned 6:

     1
   /   
  2     
 / \    
3   5 6

One way to solve this, is to agree that the index in the original input array is no longer defining the position of the node, and the tree would become:

     1
   /   \
  2*    3
 / \    
5   6

...where the asterisk represents a count of 2. Note that this is a completely different tree. For instance, now 3 is a direct child of 1, and only because there was a duplicate 2...

If this is however how you would want it to work, then make your algorithm iterative instead of recursive, and keep track of what the parent is of any newly created node:

class eNode: 
    def __init__(self, data):
        self.data = data 
        self.left = self.right = None
        self.counter = 1
    
    def __str__(self):
        return str(self.data) + &quot; Counter: &quot; + str(self.counter)

def insertLevelOrder(arr):
    if arr == []:
        return
    root = eNode(arr[0])
    nodes = [root]
    d = {root.data: root}
    right = False
    parent = 0
    for val in arr[1:]:
        if val in d:
            d[val].counter += 1
        else:
            node = eNode(val)
            nodes.append(node)
            d[val] = node    
            if right:
                nodes[parent].right = node
                parent += 1
            else:
                nodes[parent].left = node
            right = not right
    return root

def main():
    empList = [1, 2, 2, 3, 5]
    root = insertLevelOrder(empList)
    print (root);
    print (root.left);
    print (root.right);
    print (root.left.left);
    print (root.left.right);

main()

答案2

得分: 0

你可以维护一个值到二叉树节点的字典。如果要插入的值已经存在于字典中,你可以获取节点的引用并更新它。

英文:

You can maintain a dictionary of value to binary tree nodes. If the value being inserted already exists in the dictionary, you can get the reference to the node and update it.

huangapple
  • 本文由 发表于 2020年1月4日 01:19:17
  • 转载请务必保留本文链接:https://go.coder-hub.com/59582721.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定