KY11 二叉树遍历

KY11 二叉树遍历

法一:

import sys
position = 0
class TreeNode():  
    def __init__(self, data=-1):
        self.data = data
        self.leftChild = None
        self.rightChild = None
    def InOrder(self):
        if self.leftChild != None:
            self.leftChild.InOrder()
        print(self.data,end=' ')
        if self.rightChild != None:
            self.rightChild.InOrder()
    def getTree(self, line):
        self.data = line[0]
        if line[1:] == "##":
            self.leftChild = None
            self.rightChild = None
        else:
            line = line[1:]
            cntData, cntSharp = 0, 0
            for c in line:
                if c == "#":
                    cntSharp += 1
                else:
                    cntData += 1
                if cntSharp-1 == cntData:
                    break
            leftInfo, rightInfo = line[:cntSharp+cntData],line[cntSharp+cntData:]
            self.leftChild, self.rightChild = TreeNode(), TreeNode()
            if leftInfo == '#':
                self.leftChild = None
            else:
                self.leftChild.getTree(leftInfo)
            if rightInfo == "#":
                self.rightChild = None
            else:
                self.rightChild.getTree(rightInfo)
def buildTree(line): 
    global position   
    if line[position]=='#':
        position += 1
        return None
    else:
        data = line[position]
        position += 1
        root = TreeNode(data)
        root.leftChild = buildTree(line)
        root.rightChild = buildTree(line)
        return root

for line in sys.stdin:
    position = 0
    line = line.strip()
    # print("开始创建树...")
    root = buildTree(line)
    # print("完成创建树...")
    root.InOrder()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

法二:

# 总节点数N=N0+N1+N2
# 总边数L=N1+2*N2
# 总边数+1=总节点数
# "#"的数量=2*N0+N1
# 推导出: "#"的数量=总结点数+1,
# 由此关系可以分出左子树部分和右子树部分

import sys
class TreeNode():  
    def __init__(self, data=-1):
        self.data = data
        self.leftChild = None
        self.rightChild = None
    def InOrder(self):
        if self.leftChild != None:
            self.leftChild.InOrder()
        print(self.data,end=' ')
        if self.rightChild != None:
            self.rightChild.InOrder()
    def getTree(self, line):
        self.data = line[0]
        if line[1:] == "##":
            self.leftChild = None
            self.rightChild = None
        else:
            line = line[1:]
            cntData, cntSharp = 0, 0
            for c in line:
                if c == "#":
                    cntSharp += 1
                else:
                    cntData += 1
                if cntSharp-1 == cntData:
                    break
            leftInfo, rightInfo = line[:cntSharp+cntData],line[cntSharp+cntData:]
            self.leftChild, self.rightChild = TreeNode(), TreeNode()
            if leftInfo == '#':
                self.leftChild = None
            else:
                self.leftChild.getTree(leftInfo)
            if rightInfo == "#":
                self.rightChild = None
            else:
                self.rightChild.getTree(rightInfo)
        
for line in sys.stdin:
    line = line.strip()
    root = TreeNode()
    # print("开始创建树...")
    root.getTree(line)  # 包括根节点在内的先序访问序列
    # print("完成创建树...")
    root.InOrder()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52