zyg

用户名：jawide

访问量：942

签　名：

等　　级
排　　名	25558
经　　验	595
参赛次数	0
文章发表	2
年　　龄	0
在职情况	学生
学　　校	洛阳理工学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯2013年第四届真题-横向打印二叉树详解
浏览：708

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

蓝桥杯2013年第四届真题-横向打印二叉树详解

　　作者: zyg　　　　发表时间：2021-05-04 11:56:55 浏览：708　|　评论：0　

原题链接：蓝桥杯2013年第四届真题-横向打印二叉树

#### 解题思路:

1. 建立二叉排序树
2. 逆中序遍历二叉排序树

#### 注意事项:

1. 输出格式
```
.............|-25-|
.............|....|-23
........|-19-|
...|-18-|
...|....|-17-|
...|.........|-15-|
...|..............|....|-14-|
...|..............|....|....|-13
...|..............|-12-|
10-|
...|...........|-9
...|.......|-8-|
...|.......|...|-7
...|...|-6-|
...|-5-|
.......|...|-4
.......|-3-|
...........|-2-|
...............|-1
```
把它在水平方向上分层
```
... . .... . .... | -25- | 
... . .... . .... | .... | -23
... . .... | -19- |   
... | -18- |     
... | .... | -17- |   
... | .... . .... | -15- | 
... | .... . .... . .... | .... | -14- | 
... | .... . .... . .... | .... | .... | -13
... | .... . .... . .... | -12- |
10- | 
... | ... . ... . ... | -9
... | ... . ... | -8- | 
... | ... . ... | ... | -7
... | ... | -6- |   
... | -5- |     
... . ... | ... | -4  
... . ... | -3- |   
... . ... . ... | -2- | 
... . ... . ... . ... | -1
```
可以看出**每一层**的**某一列**的点的个数是由这一层的**节点**的数字的**长度**和**横线**决定的。如果该节点有父，它前面就有横线，有子，后面就有横线。
例如：13这个节点，把它剥离出来
```
... | -18- |     
... | .... | -17- |   
... | .... . .... | -15- | 
... | .... . .... . .... | .... | -14- | 
... | .... . .... . .... | .... | .... | -13
... | .... . .... . .... | -12- |
10- | 
```
13共有6个祖宗 10、18、17、15、12、14
13前面的点就是由这些祖宗的长度来决定的
解决了点的问题，再来看**竖线**，什么时候要画竖线？
13前共有4条竖线，竖线左右的数字由一定的规律
第一条 10<13<18
第二条 12<13<15
第三条 12<13<14
第四条 除了根节点每个节点前面都有
观察后可以发现，只要发生了"交叉"，或者说只要13位于两个祖宗之间，就要画竖线，如果不画竖线，就画点
然后就没了
#### 参考代码:

```python
def rin_order(node, visit):
    '''逆中序遍历'''
    if not node:
        return
    rin_order(node.rchild, visit)
    visit(node)
    rin_order(node.lchild, visit)

class DepthNode:
    '''带有深度、父节点的节点'''
    def __init__(self, data, depth, parent, lchild=None, rchild=None):
        self.data = data
        self.depth = depth
        self.parent = parent
        self.lchild = lchild
        self.rchild = rchild

class DepthSortBiTree:
    '''带有深度、父节点的二叉排序树'''
    def __init__(self):
        self.root = None

def insert(self, value, node=None, depth=0):
        if not self.root:
            self.root = DepthNode(value, depth, None)
            return
        if not node:
            node = self.root
        depth += 1
        if value < node.data:
            if not node.lchild:
                node.lchild = DepthNode(value, depth, node)
            else:
                self.insert(value, node.lchild, depth)
        else:
            if not node.rchild:
                node.rchild = DepthNode(value, depth, node)
            else:
                self.insert(value, node.rchild, depth)

def get_digits(n):
    '''获取数字长度'''
    return len(str(n))

def get_parents(node, parents):
    '''获取一个节点的所有父节点'''
    if node.parent:
        parents.append(node.parent)
        get_parents(node.parent, parents)

def sort_tree_print(node):
    '''打印二叉排序树中的某一个节点'''
    res = ""
    parents = []
    # 获取所有父节点
    get_parents(node, parents)
    # 逆序遍历
    for i in range(len(parents)-1, -1, -1):
        p = parents[i]
        # 计算父节点所占空间
        node_length = 0
        # 有父 -10
        if p.parent:
            node_length+=1
        # 有子 10-
        if p.lchild or p.rchild:
            node_length+=1
        node_length+=get_digits(p.data)
        # 画点
        res += "."*node_length
        # 画竖线
        if i > 0:
            # 左右交叉就加竖线，反之用点代替
            if node.data < p.data and node.data > parents[i-1].data:
                res += "|"
            elif node.data > p.data and node.data < parents[i-1].data:
                res += "|"
            else:
                res += "."
    # 有父
    if node.parent:
        res += "|-"
    res += str(node.data)
    # 有子
    if node.lchild or node.rchild:
        res += "-|"
    print(res)

# 10 18 17 15 12 14 13 19 25 23 5 6 8 9 7 3 4 2 1
a = list(map(int, input().split()))
tree = DepthSortBiTree()
# 建树
for i in a:
    tree.insert(i)
# 逆序遍历，打印
rin_order(tree.root, sort_tree_print)
```

0.0分

5 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zyg

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

台球碰撞（C++代码）

蓝桥杯2013年第四届真题-横向打印二叉树详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言训练-求函数值（C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

川哥的吩咐（C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

这可能是一个假的冒泡法

A+B for Input-Output Practice (IV) （C语言代码）

哥德巴赫曾猜测（C语言代码）

The 3n + 1 problem （C语言代码）

zyg

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题11.5 （C++代码）

C语言程序设计教程（第三版）课后习题8.5 （C++代码）

C语言程序设计教程（第三版）课后习题10.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.10 （C++代码）

台球碰撞 （C++代码）

蓝桥杯2013年第四届真题-横向打印二叉树 详解

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题9.1 （C++代码）

C语言训练-委派任务* （C语言代码）..................竟然是第一个

C语言训练-求函数值 （C语言代码）

C语言程序设计教程（第三版）课后习题8.3 （Java代码）

川哥的吩咐 （C++代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）

这可能是一个假的冒泡法

A+B for Input-Output Practice (IV) （C语言代码）

哥德巴赫曾猜测 （C语言代码）

The 3n + 1 problem （C语言代码）

台球碰撞（C++代码）

蓝桥杯2013年第四届真题-横向打印二叉树详解

　　评论区

C语言训练-求函数值（C语言代码）

川哥的吩咐（C++代码）

哥德巴赫曾猜测（C语言代码）