“Python字典”的PostOrder、InOrder预序

Question

有人能提供任何帮助或建议，如何做一般的遍历python字典吗？

下面是我的示例数据(从维基百科页面中删除遍历数据)

TREEDATA = [['F', 'B', 'A'],
    ['F', 'B', 'D', 'C'],
    ['F', 'B', 'D', 'E'],
    ['F', 'G', 'I', 'H']]

我有一个简单的函数来根据这些数据创建一个dict。

def createTree(allTransactionsMatrix):
    root = {}
    for transaction in allTransactionsMatrix:
        tempDict = root
        for item in transaction:
            tempDict = tempDict.setdefault(item, {})
    return root

我成功地为这个dict创建了一个预顺序遍历。

def preOrderTraversal(pyTree):
    for key, value in pyTree.items():
        print(key)
        if isinstance(value, dict):
            preOrderTraversal(value)

所以我跑的时候..。

import json
pyTree = createTree(TREEDATA)
print(json.dumps(pyTree, indent=5))

我有一本好字典

{
     "F": {
          "B": {
               "A": {},
               "D": {
                    "C": {},
                    "E": {}
               }
          },
          "G": {
               "I": {
                    "H": {}
               }
          }
     }
}

我可以得到这棵树的前置遍历

preOrderTraversal(pyTree)

带输出

F
B
A
D
C
E
G
I
H

然而，无序和事后秩序被证明是困难的。

postorder的开始是在我访问一个叶节点之后删除它。但是，由于剪枝/删除的工作方式，这并不能通过整个树。

def postOrderTraversal(pyTree):
    for key, value in list(pyTree.items()):
        if pyTree[key] == {}:
            print(key)
            del pyTree[key]
        else:
            postOrderTraversal(pyTree[key])

注意，我之所以使用list(pyTree.items())，是因为在python3中，您不能删除当前的迭代器。它会知道并抛出错误。所以转换成一张单子让我开始做这个。

谢谢你的帮助！

Answer 1

字典是伟大的可视化，但不是很好的遍历方法。因此，我实现了一个python树类，它可以是二进制的或n-ary的(但不是二进制搜索树，值和类型都不重要)。

下面是所有遍历方法的代码和示例输出等等。

from queue import *
import json
import itertools
import math


class Node:
    def __init__(self, val):
        self.val = val
        self.children = []
        self.freq = 1

    def get(self):
        return self.val

    def set(self, val):
        self.val = val

    def getChild(self, val):
        for each in self.children:
            if each.val == val:
                return each

    def getChildren(self):
        childArray = []
        for each in self.children:
            childArray.append(each.val)
        return childArray

    def printStats(self):
        print("Value: " + str(self.val) + " | " +
              "Frequency: " + str(self.freq) + " | " +
              "Children: " + ','.join(self.getChildren()))


class PythonTree:
    def __init__(self):
        self.root = Node("*root*")
        self.totalTreeNodes = 1
        self.totalInsertions = 1
        self.treeDepth = 0
        self.visualDict = {self.root.get()}

    def setVisualDict(self, passedMatrix):
        root = {}
        for transaction in passedMatrix:
            tempDict = root
            for item in transaction:
                tempDict = tempDict.setdefault(item, {})
        self.visualDict = root

    def addByMatrix(self, passedMatrix):
        self.setVisualDict(passedMatrix)
        for subArray in passedMatrix:
            currentNode = self.root
            tempLength = len(subArray)
            if tempLength > self.treeDepth:
                self.treeDepth = tempLength
            for each in subArray:
                self.totalInsertions += 1
                if each in currentNode.getChildren():
                    currentNode = currentNode.getChild(each)
                    currentNode.freq += 1
                else:
                    self.totalTreeNodes += 1
                    tempNode = Node(each)
                    currentNode.children.append(tempNode)
                    currentNode = tempNode

    def preOrder(self, currentNode, retArray):
        retArray.append(currentNode.get())
        for each in currentNode.children:
            self.preOrder(each, retArray)
        return retArray

    def preOrderTraversal(self):
        return self.preOrder(self.root, [])

    def inOrder(self, currentNode, retArray):
        whole = len(currentNode.children)
        half = math.ceil(whole / 2)

        for each in itertools.islice(currentNode.children, 0, half):
            self.inOrder(each, retArray)
        retArray.append(currentNode.get())
        for each in currentNode.children[half:]:
            self.inOrder(each, retArray)

        return retArray

    def inOrderTraversal(self):
        return self.inOrder(self.root, [])

    def postOrder(self, currentNode, retArray):
        for each in currentNode.children:
            self.postOrder(each, retArray)
        retArray.append(currentNode.get())
        return retArray

    def postOrderTraversal(self):
        return self.postOrder(self.root, [])

    def levelOrderTraversal(self):
        currentNode = self.root
        q = Queue()
        q.put(currentNode)
        output = []
        while q.qsize() > 0:
            currentNode = q.get()
            output.append(currentNode.val)
            for each in currentNode.children:
                q.put(each)
        return output

    def getStatsTraversal(self):
        currentNode = self.root

        mostFrequent = []
        leastFrequent = []
        maxVal = currentNode.freq
        minVal = currentNode.freq

        q = Queue()
        q.put(currentNode)
        while q.qsize() > 0:
            currentNode = q.get()
            currentNode.printStats()
            # Max Checks
            if currentNode.freq > maxVal:
                mostFrequent = [currentNode.get()]
                maxVal = currentNode.freq
            if currentNode.freq == maxVal:
                if currentNode.get() not in mostFrequent:
                    mostFrequent.append(currentNode.get())
            # Min Checks
            if currentNode.freq < minVal:
                leastFrequent = [currentNode.get()]
                minVal = currentNode.freq
            if currentNode.freq == minVal:
                if currentNode.get() not in leastFrequent:
                    leastFrequent.append(currentNode.get())

            for each in currentNode.children:
                q.put(each)
        return mostFrequent, leastFrequent, maxVal, minVal

    def getTreeStats(self):
        print("***Including the *root* node***\n")
        mostFrequent, leastFrequent, maxVal, minVal = self.getStatsTraversal()
        print("\nTotal Nodes: " + str(self.totalTreeNodes))
        print("Total Insertions ( greater than or equal to total Nodes ): " + str(self.totalInsertions))
        print("Depth of Tree: " + str(self.treeDepth))
        print("Most Frequent Nodes: " + str(mostFrequent) + " appeared (" + str(maxVal) + ") time(s)")
        print("Least Frequent Nodes: " + str(leastFrequent) + " appeared (" + str(minVal) + ") time(s)")
        avg = float(self.totalInsertions / self.totalTreeNodes)
        print("Average Node Frequency " + str(avg) + " (totalNodes/ totalInsertions")
        print(json.dumps(self.visualDict, indent=5))

下面是一个示例运行(来自wiki的相同节点，刚刚修改)。

myTree = PythonTree()
myTree.addByMatrix([['F', 'B', 'A'],
                    ['F', 'B', 'D', 'C'],
                    ['F', 'B', 'D', 'E'],
                    ['F', 'G', 'I', 'J'],
                    ['F', 'G', 'I', 'H']])

print("\nPRE ORDER TRAVERSAL")
print(myTree.preOrderTraversal())

print("\nLEVEL ORDER TRAVERSAL")
print(myTree.levelOrderTraversal())

print("\nIN ORDER TRAVERSAL")
print(myTree.inOrderTraversal())

print("\nPOST ORDER TRAVERSAL")
print(myTree.postOrderTraversal())

print("\nTREE STATS")
myTree.getTreeStats()

以及相关的输出。

PRE ORDER TRAVERSAL
['*root*', 'F', 'B', 'A', 'D', 'C', 'E', 'G', 'I', 'J', 'H']

LEVEL ORDER TRAVERSAL
['*root*', 'F', 'B', 'G', 'A', 'D', 'I', 'C', 'E', 'J', 'H']

IN ORDER TRAVERSAL
['A', 'B', 'C', 'D', 'E', 'F', 'J', 'I', 'H', 'G', '*root*']

POST ORDER TRAVERSAL
['A', 'C', 'E', 'D', 'B', 'J', 'H', 'I', 'G', 'F', '*root*']

TREE STATS
***Including the *root* node***

Value: *root* | Frequency: 1 | Children: F
Value: F | Frequency: 5 | Children: B,G
Value: B | Frequency: 3 | Children: A,D
Value: G | Frequency: 2 | Children: I
Value: A | Frequency: 1 | Children: 
Value: D | Frequency: 2 | Children: C,E
Value: I | Frequency: 2 | Children: J,H
Value: C | Frequency: 1 | Children: 
Value: E | Frequency: 1 | Children: 
Value: J | Frequency: 1 | Children: 
Value: H | Frequency: 1 | Children: 

Total Nodes: 11
Total Insertions ( greater than or equal to total Nodes ): 20
Depth of Tree: 4
Most Frequent Nodes: ['F'] appeared (5) time(s)
Least Frequent Nodes: ['*root*', 'A', 'C', 'E', 'J', 'H'] appeared (1) time(s)
Average Node Frequency 1.8181818181818181 (totalNodes/ totalInsertions
{
     "F": {
          "B": {
               "A": {},
               "D": {
                    "C": {},
                    "E": {}
               }
          },
          "G": {
               "I": {
                    "J": {},
                    "H": {}
               }
          }
     }
}

如果您有任何问题，请评论。我知道排序遍历并不总是正确的，但是没有明确的方法来执行N进制树的有序遍历。但其他方法应该是一致的。