python-二叉树的实现(oj向)

末蓝、 2022-12-30 03:42 147阅读 0赞

**目录**

前言

基本操作函数

创建

遍历

先序遍历（递归）

中序遍历（递归）

后序遍历（递归）

层次遍历（迭代）

高度

高级操作函数

锯齿形遍历

全部代码

--------------------

# 前言 #

本文用python实现了二叉树，由于博主是为了刷leetcode，熟悉python如何去实现数据结构与算法，所以采用的Solution方式，函数没有当做二叉树类的方法。

**结构**

class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None

** 所用的树**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

# 基本操作函数 #

## 创建 ##

def create(self, gen, null: str = 'n'):
            """
            create a binary tree
            :param gen: a generator for parameters, use next() to get next one
            :param null: means no node
            :return: a binary tree's root
            """
            try:
                c = next(gen)
            except StopIteration:
                return None
            if c == null:
                root = None
            else:
                root = TreeNode(c)
                root.left = self.create(gen, null)
                root.right = self.create(gen, null)
            return root

**作用**

使用**先序遍历序列**创建一棵二叉树**，**博主还是花费了一会儿去设计的，python的输入是input()，它会读取一行，不能像c里面的scanf()似的，于是写了个**生成器**，这样用户输入时就可以把整个二叉树序列写在一行了，另外，如果你的二叉树节点的数据是字母，可能含‘n‘’，还可以用“\#”等来代替“n”，写了一个**默认参数**，修改时可传参，兼容性好点。

**参数**

*  gen:生成器，用于一个个的获取前序遍历序列的元素，方便用户输入一行即可，对大一些的二叉树比较方便，可以注释掉主函数的input()，直接令seq  = "3 9 n n 20 15 n n 7 n n"
 *  null**:**代表节点为空，默认是'n'

**返回**

二叉树的根节点

![20201223220207771.PNG][] 创建二叉树

## 遍历 ##

### 先序遍历（递归） ###

def recur_preorder(self, root: TreeNode) -> None:
            """
            show preorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                print(root.val, end=' ')
                self.recur_preorder(root.left)
                self.recur_preorder(root.right)

**参数**

*  root:二叉树的根节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1][] 先序遍历

中序和后序遍历不再截图！！！

\--------------2021年01月24日更新---------------

### 先序遍历（迭代） ###

def iter_preorder(self, root: TreeNode) -> None:
            """
            show preorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is None:
                return None
            stack = [root]
            while len(stack) != 0:
                tmp = stack.pop()
                print(tmp.val, end=' ')
                if tmp.right is not None:
                    stack.append(tmp.right)
                if tmp.left is not None:
                    stack.append(tmp.left)

先序遍历的迭代版本，使用栈模拟过程，先入右孩子再入左孩子，出栈时就是根左右了

**参数**

*  root:二叉树的根节点

\--------------2021年01月24日更新---------------

### 中序遍历（递归） ###

def recur_inorder(self, root: TreeNode) -> None:
            """
            show inorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                self.recur_preorder(root.left)
                print(root.val, end=' ')
                self.recur_preorder(root.right)

**参数**

*  root:二叉树的根节点

--------------2021年01月24日更新--------------

### 中序遍历（迭代） ###

def iter_inorder(self, root: TreeNode) -> None:
            """
            show inorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            stack = []
            while len(stack) != 0 or root is not None:
                # add node until no left child
                while root is not None:
                    stack.append(root)
                    root = root.left
                root = stack.pop()
                print(root.val, end=' ')
                root = root.right
            return None

中序遍历的迭代版本，使用栈模拟过程，先入左孩子直到**最左节点**，再入右孩子。出栈时的顺序就是左中右了。

**参数**

*  root:二叉树的根节点

\--------------2021年01月24日更新---------------

### 后序遍历（递归） ###

def recur_postorder(self, root: TreeNode) -> None:
            """
            show postorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                self.recur_preorder(root.left)
                self.recur_preorder(root.right)
                print(root.val, end=' ')

**参数**

*  root:二叉树的根节点

### 层次遍历（迭代） ###

def level(self, root: TreeNode) -> None:
            """
            show level traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                queue = [root]
                while len(queue) != 0:
                    n = len(queue)
                    for _ in range(n):
                        tmp = queue.pop(0)
                        print(tmp.val, end=' ')
                        if tmp.left is not None:
                            queue.append(tmp.left)
                        if tmp.right is not None:
                            queue.append(tmp.right)
                    print()

**作用**

利用**队列**，从上(根)至下(叶子)，从左到右遍历。

**参数**

*  root:二叉树的根节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2][] 层次遍历

## 高度 ##

def height(self, root) -> int:
            """
            calculate the height of a binary tree
            :param root: the root of a binary tree
            :return: the height of a binary tree
            """
            if root is None:
                return 0
            if root.left is None and root.right is None:
                return 1
            return max(self.height(root.left), self.height(root.right)) + 1

**作用**

计算二叉树的高度（二叉树的最高层数，从1开始）

**参数**

*  root:二叉树的根节点

** 返回**

二叉树的高度

![20201223220428347.PNG][] 高度

# 高级操作函数 #

## 锯齿形遍历 ##

锯齿形遍历：层次遍历按从左至右和从右至左交替进行，根节点所在层算从左至右遍历。

def zigzagLevelOrder(self, root: TreeNode) -> None:
            """
            https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
            it need to return a List in problem, I just show answer in this function to avoid that main function is too long
            :param root: the root of a binary tree
            :return: None
            """
            ans = []
            if root is not None:
                queue = [root]
                left = True
                while len(queue) != 0:
                    n = len(queue)
                    d = deque()
                    for _ in range(n):
                        tmp = queue.pop(0)
                        if left:
                            d.append(tmp.val)
                        else:
                            d.appendleft(tmp.val)
                        if tmp.left is not None:
                            queue.append(tmp.left)
                        if tmp.right is not None:
                            queue.append(tmp.right)
                    ans.append(list(d))
                    left = not left
            for level in ans:
                for node in level:
                    print(node, end=' ')
                print()

**作用**

利用层次遍历，使用**双端队列**进行部分结果的保存。

**参数**

*  root:二叉树的根节点

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3][] 锯齿形遍历

**不保存结果，直接输出**

def zigzagLevelOrder2(self, root: TreeNode) -> None:
            """
            like zigzagLevelOrder, but don't save the result
            :param root: the root of a binary tree
            :return: None
            """
            if root is not None:
                d = deque([root])
                left = True
                while len(d) != 0:
                    n = len(d)
                    for _ in range(n):
                        if left:
                            tmp = d.popleft()
                            if tmp.left is not None:
                                d.append(tmp.left)
                            if tmp.right is not None:
                                d.append(tmp.right)
                        else:
                            tmp = d.pop()
                            if tmp.right is not None:
                                d.appendleft(tmp.right)
                            if tmp.left is not None:
                                d.appendleft(tmp.left)
                        print(tmp.val, end=' ')
                    left = not left
                    print()
            return None

本层为**从左向右遍历**时，从**左侧出队**，**右侧入队**，**先入左孩子，再入右孩子**。 本层为从右向左遍历时，从右侧出队，左侧入队，先入左孩子，再入右孩子。

# 全部代码 #

"""
    --coding:utf-8--
    @File: binary-tree.py.py
    @Author:frank yu
    @DateTime: 2020.12.22 17:34
    @Contact: frankyu112058@gmail.com
    @Description:
    """
    from typing import List
    from collections import deque
    
    
    class TreeNode:
        def __init__(self, x):
            self.val = x
            self.left = None
            self.right = None
    
    
    class Solution:
        # basic
        def create(self, gen, null: str = 'n'):
            """
            create a binary tree
            :param gen: a generator for parameters, use next() to get next one
            :param null: means no node
            :return: a binary tree's root
            """
            try:
                c = next(gen)
            except StopIteration:
                return None
            if c == null:
                root = None
            else:
                root = TreeNode(c)
                root.left = self.create(gen, null)
                root.right = self.create(gen, null)
            return root
    
        def recur_preorder(self, root: TreeNode) -> None:
            """
            show preorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                print(root.val, end=' ')
                self.recur_preorder(root.left)
                self.recur_preorder(root.right)
    
        def iter_preorder(self, root: TreeNode) -> None:
            """
            show preorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is None:
                return None
            stack = [root]
            while len(stack) != 0:
                tmp = stack.pop()
                print(tmp.val, end=' ')
                if tmp.right is not None:
                    stack.append(tmp.right)
                if tmp.left is not None:
                    stack.append(tmp.left)
    
        def recur_inorder(self, root: TreeNode) -> None:
            """
            show inorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                self.recur_preorder(root.left)
                print(root.val, end=' ')
                self.recur_preorder(root.right)
    
        def iter_inorder(self, root: TreeNode) -> None:
            """
            show inorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            stack = []
            while len(stack) != 0 or root is not None:
                # add node until no left child
                while root is not None:
                    stack.append(root)
                    root = root.left
                root = stack.pop()
                print(root.val, end=' ')
                root = root.right
            return None
    
        def recur_postorder(self, root: TreeNode) -> None:
            """
            show postorder traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                self.recur_preorder(root.left)
                self.recur_preorder(root.right)
                print(root.val, end=' ')
    
        def level(self, root: TreeNode) -> None:
            """
            show level traversal
            :param root:the root of a binary tree
            :return:None
            """
            if root is not None:
                queue = [root]
                while len(queue) != 0:
                    n = len(queue)
                    for _ in range(n):
                        tmp = queue.pop(0)
                        print(tmp.val, end=' ')
                        if tmp.left is not None:
                            queue.append(tmp.left)
                        if tmp.right is not None:
                            queue.append(tmp.right)
                    print()
    
        def height(self, root) -> int:
            """
            calculate the height of a binary tree
            :param root: the root of a binary tree
            :return: the height of a binary tree
            """
            if root is None:
                return 0
            if root.left is None and root.right is None:
                return 1
            return max(self.height(root.left), self.height(root.right)) + 1
    
        # advanced
        def zigzagLevelOrder(self, root: TreeNode) -> None:
            """
            https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/
            it need to return a List in problem, I just show answer in this function to avoid that main function is too long
            :param root: the root of a binary tree
            :return: None
            """
            ans = []
            if root is not None:
                queue = [root]
                left = True
                while len(queue) != 0:
                    n = len(queue)
                    d = deque()
                    for _ in range(n):
                        tmp = queue.pop(0)
                        if left:
                            d.append(tmp.val)
                        else:
                            d.appendleft(tmp.val)
                        if tmp.left is not None:
                            queue.append(tmp.left)
                        if tmp.right is not None:
                            queue.append(tmp.right)
                    ans.append(list(d))
                    left = not left
            for level in ans:
                for node in level:
                    print(node, end=' ')
                print()
    
        def zigzagLevelOrder2(self, root: TreeNode) -> None:
            """
            like zigzagLevelOrder, but don't save the result
            :param root: the root of a binary tree
            :return: None
            """
            if root is not None:
                d = deque([root])
                left = True
                while len(d) != 0:
                    n = len(d)
                    for _ in range(n):
                        if left:
                            tmp = d.popleft()
                            if tmp.left is not None:
                                d.append(tmp.left)
                            if tmp.right is not None:
                                d.append(tmp.right)
                        else:
                            tmp = d.pop()
                            if tmp.right is not None:
                                d.appendleft(tmp.right)
                            if tmp.left is not None:
                                d.appendleft(tmp.left)
                        print(tmp.val, end=' ')
                    left = not left
                    print()
            return None
    
    
    def node_gen(para: List[str]):
        """
        :param para: node's value with space
        :return: the parameters one by one
        """
        for node in para:
            yield node
    
    
    def menu():
        print('--------------------Menu--------------------')
        print('1.Create                2.Traversal')
        print('3.Height')
        print('e.Exit')
    
    
    def traversal_menu():
        print('--------------Traversal Menu----------------')
        print('1.preorder                2.inorder')
        print('3.postorder               4.level')
        print('5.zigzag level')
    
    
    if __name__ == '__main__':
        s = Solution()
        seq = input('please enter a binary tree in preorder separated by white space, "n" means null:')
        gen = node_gen(seq.split())
        # use seq to create a binary tree t
        t = s.create(gen)
        while True:
            menu()
            choice = input('please select an option：')
            if choice == 'e':
                break
            if choice == '1':
                seq = input('please input a binary tree with preorder sequence "n" means null, "#" means stop:')
                gen = node_gen(seq.split())
                t = s.create(gen)
            elif choice == '2':
                traversal_menu()
                choice = input('please select an option：')
                if choice == '1':
                    print('preorder sequense:')
                    s.recur_preorder(t)
                    print()
                elif choice == '2':
                    print('inorder sequense:')
                    s.recur_inorder(t)
                    print()
                elif choice == '3':
                    print('postorder sequense:')
                    s.recur_postorder(t)
                    print()
                elif choice == '4':
                    print('level order sequense:')
                    s.level(t)
                elif choice == '5':
                    print('zigzag level order sequense:')
                    s.zigzagLevelOrder2(t)
            elif choice == '3':
                print(f'the height of binary tree is {s.height(t)}.')
            else:
                print(f'{choice} is a wrong option.')

更多python相关内容：[【python总结】python学习框架梳理][python_python]

本人b站账号:[lady\_killer9][lady_killer9]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。如果您感觉有所收获，自愿打赏，可选择支付宝18833895206（小于），您的支持是我不断更新的动力。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: /images/20221120/0ca21603aeaf4c30b7320cb551b4b6cf.png
[20201223220207771.PNG]: https://img-blog.csdnimg.cn/20201223220207771.PNG
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201223220247980.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201223220347447.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ==,size_16,color_FFFFFF,t_70
[20201223220428347.PNG]: https://img-blog.csdnimg.cn/20201223220428347.PNG
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201223220651777.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ==,size_16,color_FFFFFF,t_70
[python_python]: https://blog.csdn.net/lady_killer9/article/details/108763489
[lady_killer9]: https://space.bilibili.com/374432302