树Tree

作者: carry_xz | 来源:发表于2019-06-23 00:23 被阅读0次

    节点类

    class Node(object):
        def __init__(self,data=None):
            self.val = data
            self.left = None 
            self.right = None 
    

    二叉树前、中、后、按层遍历

    class MyTree(object):
        def __init__(self):
            self.root = Node()
        def add(self,data):
            if self.root.val is None:
                self.root.val = data
                return self.root
            tempList = []
            tempList.append(self.root)
            while len(tempList):
                curNode = tempList.pop(0)
                if curNode.left is None:
                    curNode.left = Node(data)
                    return self.root
                if curNode.right is None:
                    curNode.right = Node(data)
                    return self.root
                tempList.append(curNode.left)
                tempList.append(curNode.right)
    
        def per_order_recurise(self,node):
            if node is None:
                return
            print(node.val)
            self.per_order_recurise(node.left)
            self.per_order_recurise(node.right)
    
        def per_order_stack(self,node):
            if node is None:
                return
            stack = []
            nodeTemp = node
            while nodeTemp or len(stack):
                while nodeTemp:
                    print(nodeTemp.val)
                    stack.append(nodeTemp)
                    nodeTemp = nodeTemp.left
                nodeTemp = stack.pop(0)
                if nodeTemp:
                    nodeTemp = nodeTemp.right
    
        def in_order_recurise(self,node):
            if node is None:
                return
            self.in_order_recurise(node.left)
            print(node.val)
            self.in_order_recurise(node.right)
        
        def post_order_recurise(self,node):
            if node is None:
                return
            self.post_order_recurise(node.left)
            self.post_order_recurise(node.right)
            print(node.val)
    
        def level_recursion(self,node):
            if node is None:
                return 
            tempList = []
            tempList.append(node)
            tempNode = node
            count = 0
            while len(tempList):
                curNode = tempList.pop(0)
                if curNode:
                    print(curNode.val)
                if curNode==tempNode:
                    count += 1
                    tempNode = curNode.right
                    print('level :',count)
                if curNode.left is None:
                    continue 
                tempList.append(curNode.left)
                if curNode.right is None:
                    continue 
                tempList.append(curNode.right)
    

    二叉搜索树

    class SearchTree():
        def __init__(self):
            self.root = None
            
        def insert(self, root, val):
            '''二叉搜索树插入操作'''
            if root == None:
                root = TreeNode(val)
            elif val < root.val:
                root.left = self.insert(root.left, val)
            elif val > root.val:
                root.right = self.insert(root.right, val)
            return root
    
        def query(self, root, val):
            '''二叉搜索树查询操作'''
            if root == None:
                return False
            if root.val == val:
                return True
            elif val < root.val:
                return self.query(root.left, val)
            elif val > root.val:
                return self.query(root.right, val)
    
        def findMin(self, root):
            '''查找二叉搜索树中最小值点'''
            if root.left:
                return self.findMin(root.left)
            else:
                return root
    

    最大、最小深度

    class Solution:
        def maxDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root==None:
                return 0
            if root.left==None or root.right==None:
                return 1+ self.maxDepth(root.left)+self.maxDepth(root.right)
            return 1+ max(self.maxDepth(root.left),self.maxDepth(root.right))
    
    class Solution(object):
        def minDepth(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if root is None:
                return 0
            if root.left is None or root.right is None:
                return 1 + min(self.minDepth(root.left)+self.minDepth(root.right))
                # 只有叶子节点才能用于计算深度,为空不是在叶子,不能用于计算深度。
                # 不知道那个为空,所以都加上,反正为0.
            else:
                return 1  + min(self.minDepth(root.left),self.minDepth(root.right))
    
    # 层遍历
    # 建立一个空列表,待遍历 temp_list,建立一个标记节点temp_node
    # 将树的根节点放入temp_list,temp_node=root
    # while temp_list 不为空,弹出list的0位节点,打印节点值,并将该节点的子节点加入(append)temp_list中。
    # 如果弹出节点==temp_node,则层数加一,并将temp_list最后的节点赋值给temp_node
    
    # 非递归的先、中、后序遍历
    # 建立一个待遍历temp_list,将根节点放入
    # while temp_list 不为空,弹出0位置节点,打印值,将子节点append到temp_list中。
    
    # 递归建二叉搜索树的过程
    # 传入根节点,无节点建立节点
    # 有节点,比较值,小于则将左节点作为根节点,递归
    # 大于则将右节点作为根节点,递归
    # 搜索过程
    # 与根节点比较,如果小于则递归查找左侧,如果大于则递归查找右侧,直到找到或者,没找到。可以返回最近的叶子节点。
    

    相关文章

      网友评论

          本文标题:树Tree

          本文链接:https://www.haomeiwen.com/subject/qcvkaqtx.html