[Python]树基础

2021/6/14 20:24:42

本文主要是介绍[Python]树基础,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

关于树

树是一种数据结构,由n个有限节点组成的一个具有层次关系的集合。二叉树则是每个节点最多有两个子树的树结构。二叉树一般有以下性质:

  • 二叉树第k层上的节点数目最多为 $2^{k-1}$
  • 深度为 h 的二叉树至多有 $2^{h-1}$ 个节点。
  • 包含 n 个节点的二叉树的高度至少为 $log_2(n+1)$
  • 在任意一棵二叉树中,若叶子节点的个数为$n_0$,度为2的节点数为$n_2$,则$n_0 = n_2 + 1$

二叉树的简单实现

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

class Tree(object):
    def __init__(self,node=None):
        self.root = node

    def add(self,item=None):
        node =Node(val=item)
        if not self.root or self.root.val is None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            while True:
                current_node = queue.pop(0)
                if current_node.val is None:
                    continue
                if not current_node.left:
                    current_node.left = node
                    return
                elif not current_node.right:
                    current_node.right = node
                    return
                else:
                    queue.append(current_node.left)
                    queue.append(current_node.right)

tree = Tree()
for i in range(10):
    if i == 3:
        i = None
    tree.add(i)

树的结构如下:



这篇关于[Python]树基础的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程