Java教程

数据结构与算法 12.二叉树 Binary Tree

本文主要是介绍数据结构与算法 12.二叉树 Binary Tree,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

二叉树 Binary Tree

二叉树的特点
    每个节点的度最大为2(最多拥有2棵子树)
    左子树和右子树是有顺序的
    即使某个节点只有一棵子树,也要区分左右子树

二叉树的性质
    非空二叉树的第i层最多有 2^(i-1) 个节点(i >= 1)
    高度为h的二叉树上最多有 2^h - 1 个节点(h >= 1)
    对于任何一棵非空二叉树,如果叶子节点个数为n0,度为2的节点个数为n2,则有 n0 = n2 + 1
        推导:设度为1的节点个数为n1,总节点数 n = n0 + n1 + n2
              边数 T = n1 + 2*n2 ,T = n - 1
              =>    n1 + 2*n2 = n - 1 = n0 + n1 + n2    =>    n0 = n2 + 1

二叉树节点表示
    每个节点node包含三部分:数据域elem,指向左子树的的指针lchild,指向右子树的指针rchild

二叉树遍历
    深度优先,一般用递归
        先序 Preorder
        中序 Inorder
        后序 Postorder
    广度优先,一般用队列

真二叉树 Proper Binary Tree
    所有节点的度都为0或2

满二叉树 Full Binary Tree
    所有节点的度都为0或2,且所有叶子节点都在最后一层
    设高为h(h>=1),则:第i层节点:2^(i-1),叶子节点:2^(h-1),总节点:n = 2^h - 1
                      =>    h = log2(n+1)

完全二叉树 Complete Binary Tree
    叶子节点只会出现在最后2层,且最后1层的叶子节点都靠左对齐
    完全二叉树从根节点至倒数第2层是一棵满二叉树;满二叉树一定是一棵完全二叉树
    性质:
        度为1的节点只有左子树;度为1的节点要么是0个,要么是1个
        节点数相同的二叉树中,完全二叉树的高度最小

        设完全二叉树高度为h,则:
            至少有 2^(h-1) 个节点
            最多有 2^h - 1 个节点
            总结点数为n,则有 h = floor( log2n ) + 1
                推导:2^(h-1) <= n < 2^h
                    =>    h - 1 <= log2n < h
                    =>    h = floor( log2n ) + 1

        一棵有n个节点的完全二叉树,从上到下、从左到右对节点从1开始进行编号,对任意第i个节点,有:
            如果 i = 1 ,它是根节点
            如果 i > 1 ,它的父节点编号为 floor(i // 2)
            如果 2i <= n ,它的左子节点编号为 2i
            如果 2i > n ,它没有左子节点
            如果 2i + 1 <= n ,它的右子节点编号为 2i + 1
            如果 2i + 1 > n ,它没有右子节点

二叉树定义、深度优先遍历、广度优先遍历

定义单位元素
class Node(object):
    def __init__(self,elem):
        self.elem = elem
        self.lchild = None
        self.rchild = None
定义二叉树
class Tree(object):
    def __init__(self,root=None):
        self.root = root

    # 添加节点
    # 对树逐层从左到右遍历,当出现空位时加入节点
    def add(self,elem):
        node = Node(elem)

        # 若为空树,添加的节点就是根节点
        if self.root == None :
            self.root = node
        else :
            # 创建空队列,把树中的节点逐层从左到右加入队列
            queue = []
            queue.append(self.root)
            while queue :
                # 每次取出队列中的第一个元素,即每层节点从左到右的顺序
                cur = queue.pop(0)
                # 当有节点度不为2时,执行添加
                if cur.lchild == None :
                    cur.lchild = node
                    return
                elif cur.rchild == None :
                    cur.rchild = node
                    return
                # 若该节点度为2,则将它的两个子节点先左后右加入队列
                else :
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)
  
  
    # 深度优先遍历,使用递归

    # 先序遍历,1,2,4,8,9,5,10,3,6,7
    # 对于一个节点,先访问自己,再访问左子树,最后访问右子树
    def Preorder(self,root):
        if root == None :
            return
        else :
            print(root.elem)
            self.Preorder(root.lchild)
            self.Preorder(root.rchild)

    # 中序遍历,8,4,9,2,10,5,1,6,3,7
    # 对于一个节点,先访问左子树,再访问自己,最后访问右子树
    def Inorder(self,root):
        if root == None :
            return
        else :
            self.Inorder(root.lchild)
            print(root.elem)
            self.Inorder(root.rchild)

    # 后续遍历,8,9,4,10,5,2,6,7,3,1
    #对于一个节点,先访问左子树,再访问右子树,最后访问自己
    def Postorder(self,root):
        if root == None :
            return
        else :
            self.Postorder(root.lchild)
            self.Postorder(root.rchild)
            print(root.elem)

    # 广度优先遍历
    def breadth_search(self,root):
        if root == None :
            return

        queue = []
        queue.append(root)
        while queue :
            cur = queue.pop(0)
            print(cur.elem)
            if cur.lchild != None :
                queue.append(cur.lchild)
            if cur.rchild != None :
                queue.append(cur.rchild)
这篇关于数据结构与算法 12.二叉树 Binary Tree的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!