数据结构——二叉树的python实现

我不是女神ヾ 2023-02-14 02:43 12阅读 0赞

### 二叉树的python实现 ###

*   *   *  一、二叉树的定义与基本性质
         *  二叉树的实现&遍历
         *   *   *  二叉树的实现
                 *  二叉树的遍历
                 *  二叉树的先序遍历（leetcode）非递归
                 *  二叉树的中序遍历（LeetCode）非递归

### 一、二叉树的定义与基本性质 ###

二叉树（Binary Tree）是一种特殊的树型结构，它的特点是每个结点至多有两棵子树（即二叉树中不存在度大于2的结点），且二叉树的子树有左右之分，其次序不能任意颠倒（有序树）。  
  根据二叉树的定义，其具有下列重要性质：

1.  在二叉树的第`i`层上至多有`2^{i-1}`个结点`(i≥1)`。
2.  深度为`k`的二叉树至多`2^k-1`有个结点`(k≥1)`。
3.  对任何一棵二叉树，如果其叶子节点数为`n0`,度为2的结点数为`n2`，则`n0=n2+1`。

一棵深度为`k`且有`2^k-1`个结点的二叉树称为**满二叉树**。深度为`k`，结点数为`n`的二叉树，当且仅当其每一个结点都与深度为`k`的满二叉树中编号为1至n的结点一一对应时，称之为完全二叉树。在下图2中，（a）**为满二叉树**，（b）为**完全二叉树**。  
  ![在这里插入图片描述][format_png]

图2 特殊形态的二叉树  
  下面介绍完全二叉树的两个特性：

性质4）具有个结点的完全二叉树的深度为`[log_{2}n]+1`,其中`[x]`表示不大于x的最大整数。  
性质5）如果对一棵有n个结点的完全二叉树的结点按层序编号（从第一层到最后一层，每层从左到右），则对任一结点`i(1≤i≤n)`,有：  
（1）如果`i=1`，则结点i是二叉树的根，无双亲；如果`i>1`,则其双亲结点为`[1/2]`。  
（2）如果`2i>n`，则结点i无左孩子；否则其左孩子是结点`2i`。  
（3）如果`2i+1>n`，则结点i无右孩子；否则其右孩子是结点`2i+1`。

介绍完了二叉树的定义及基本性质，接下来，我们需要了解二叉树的遍历。所谓二叉树的遍历，指的是如何按某种搜索路径巡防树中的每个结点，使得每个结点均被访问一次，而且仅被访问一次。对于二叉树，常见的遍历方法有：先序遍历，中序遍历，后序遍历，层序遍历。这些遍历方法一般使用递归算法实现。  
  **先序遍历**的操作定义为：  
  若二叉树为空，为空操作；否则1. 访问根节点；2. 先序遍历左子树；3. 先序遍历右子树。  
    
  **中序遍历**的操作定义为：  
  若二叉树为空，为空操作；否则1. 中序遍历左子树；2. 访问根结点；3. 中序遍历右子树。  
    
  **后序遍历**的操作定义为：  
  若二叉树为空，为空操作；否则1. 后序遍历左子树；2. 后序遍历右子树；3. 访问根结点。  
    
  **层序遍历**的操作定义为：  
  若二叉树为空，为空操作；否则从上到下、从左到右按层次进行访问。

### 二叉树的实现&遍历 ###

##### 二叉树的实现 #####

#二叉树的定义
    class BTree(object):
        def __init__(self,value):
            self.data = value
            self.left = None
            self.right = None
        # 向左子树插入节点
        def insertLeft(self,value):
            self.left = BTree(value)
            return self.left
        # 向右子树插入节点
        def insertRight(self,value):
            self.right = BTree(value)
            return self.right
        # 输出节点数据
        def show(self):
            print(self.data)

##### 二叉树的遍历 #####

# 先序遍历
    def preOrder(node):
        if node.data:
            node.show()
            if node.left:
                preOrder(node.left)
            if node.right:
                preOrder(node.right)
    # 中序遍历
    def midOrder(node):
        if node.data:
            if node.left:
                midOrder(node.left)
            node.show()
            if node.right:
                midOrder(node.right)
    # 后序遍历
    def postOrder(node):
        if node.data:
            if node.left:
                postOrder(node.left)
            if node.right:
                postOrder(node.right)
            node.show()
    
    if __name__=='__main__':
        Root = BTree('Root')  # 构建树
        A = Root.insertLeft('A')
        C = A.insertLeft('C')
        D = A.insertRight('D')
        F = D.insertLeft('F')
        G = D.insertRight('G')
        B = Root.insertRight('B')
        E =B.insertRight('E')
        print('*************************')
        print('Binary Tree pre-traversal')
        preOrder(Root)
        print('*************************')
        print('Binary Tree mid-traversal')
        midOrder(Root)
        print('*************************')
        print('Binary Tree post-traversal')
        postOrder(Root)

运行结果：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70 2]

##### 二叉树的先序遍历（leetcode）非递归 #####

# Definition for a binary tree node.
    # class TreeNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution:
        def preorderTraversal(self, root):
            ans = []
            stack = []
            if root == None:
                return ans
            p = root
            while(p or len(stack)):
                if p:
                    ans.append(p.val)
                    stack.append(p)
                    p = p.left
                else:
                    p = stack[-1]
                    stack.pop(-1)
                    p = p.right
            return ans

输入：\[1,null,2,3\]  
输出：\[1,2,3\]

##### 二叉树的中序遍历（LeetCode）非递归 #####

# class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
     
    class Solution(object):             
        def inorderTraversal(self, root):    
            stack=[]
            ans=[]
            if not root:
                return ans
            while root or stack:
                while root:
                    stack.append(root)
                    root=root.left
                if stack:
                    a=stack.pop()
                    root=a.right
                    ans.append(a.val)
            return ans

输入：\[1,null,2,3\]  
输出：\[1,3,2\]

[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85NDE5MDM0LTg3ZDNmNzZlY2Q4ZTFmYTYuanBn?x-oss-process=image/format,png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020053116572197.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200531165744216.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200531165753465.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMwMTA4MjM3,size_16,color_FFFFFF,t_70