数据结构和算法第四天~树 ，二叉树

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了数据结构和算法第四天~树 ，二叉树，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3721字，纯文字阅读大概需要6分钟。

内容图文

 

树

树（英文Tree）：它是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它具有以下的特点：

1.   每个节点有零个或多个子节点
2.   没有父节点的节点称为根节点
3.   每一个非根节点有且只有一个父节点
4.   除了根节点外，每个子节点可以分为多个不相交的子树

树的术语：

1. 节点的度：一个节点含有的子树的个数称为该节点的度
2. 树的度：一棵树中，最大的节点的度称为树的度
3. 叶节点或终端节点：度为零的节点
4. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
5. 孩子节点活子节点：一个节点含有的子树的根节点称为该节点的子节点
6. 兄弟节点：具有相同父节点的节点互称为兄弟节点
7. 节点的层次：从根节点开始定义起，根为一层，根的子节点为第二层，以此类推
8. 树的高度或深度：树中节点的最大层次
9. 堂兄弟节点：父亲节点在同一层的节点互为堂兄弟
10. 节点的祖先：从根到该节点所经分支上的所有的节点
11. 子孙：以某节点为根的子树中任意节点都称为该节点的子孙
12. 森林：由m(m>=0)棵互不相交的树的集合称为森林

无序树：树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；
有序树：树中任意节点的子节点之间有顺序关系，这种树称为有序树；
      二叉树：每个节点最多含有两个子树的树称为二叉树；
             完全二叉树：对于一个二叉树，假设其深度d(d > 1)，除了第d层外，其他各层的节点数目均已达到最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树呗称为完全二叉树，其中满二叉树的定义是所有叶节点都在最底层的完全二叉树；下图是一个完全二叉树

平衡二叉树（AVL）树：当且仅当任何节点的两颗子树的高度差不大于1的二叉树
           排序二叉树（二叉查找树，Binary Search Tree ,也称为二叉搜索树，有序二叉树）：对于任何一个节点，节点左边的子节点都会比二叉树小，节点右边的子节点都比这个节点的值大
霍夫曼树（用于信息编码）：带全路径最短的二叉树称为哈夫曼树或最优二叉树
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多余两个子树

树的存储：

 

二叉树

 

二叉树的基本概念：二叉树的每个节点最多有两个子树的树结构，通常子树被称作“左子树”和“右子树”

二叉树的性质：

性质1：在二叉树的第i层上至多有2^(i-1)个节点（i>0）

性质2：深度为k的二叉树至多有2^k-1(k>0)个节点

性质3：对于任意一颗二叉树，如果其叶节点数为N0，而度数为2的节点总数为N2，则N0=N2+1;

性质4：具有n个节点的完全二叉树的深度必为log2(n+1)

性质5：对完全二叉树，若从上至下、从左至右编号，则编号为i的节点，其左孩子编号必为2i，其右孩子编号必为2i+1；其双亲编号必为i/2（i=1时为根）

 

class  Node(object):
    def __init__(self,item):
        self.elem=item
        self.lchild=None
        self.rchild=None
class Tree(object):
    """二叉树"""
    def __init__(self):
        self.root=None

    def add(self,item):
        node=Node(item)
        if self.root is None:
            self.root=node
            return
        queue=[self.root]
        while queue:
            cur_node=queue.pop(0)
            if cur_node.lchild is None:
                cur_node.lchild=node
                return
            else:
                queue.append(cur_node.lchild)
            if cur_node.rchild is None:
                cur_node.rchild=node
                return
            else:
                queue.append(cur_node.rchild)
    def breadth_travel(self):
        """"广度遍历"""
        if self.root is None:
            return
        queue=[self.root]
        while queue:
            cur_node=queue.pop(0)
            print(cur_node.elem)
            if cur_node.lchild is not None:
                queue.append(cur_node.lchild)
            if cur_node.rchild is not None:
                queue.append(cur_node.rchild)

    def preorder(self,node):
        """先序遍历 根左右"""
        if node is None:
            return
        print(node.elem,end=" ") #先打印根节点在处理根节点的左右子树
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def inorder(self,node):
        """中序遍历 左根右"""
        if node is None:
            return
        self.inorder(node.lchild)
        print(node.elem,end=" ") #
        self.inorder(node.rchild)
    def postorder(self,node):
        """后序遍历 左右根"""
        if node is None:
            return
        self.postorder(node.lchild)  #左
        self.postorder(node.rchild)  #右
        print(node.elem,end=" ")           #根
if __name__ == '__main__':

    tree=Tree()
    tree.add(0)
    tree.add(1)
    tree.add(2)
    tree.add(3)
    tree.add(4)
    tree.add(5)
    tree.add(6)
    tree.add(7)
    tree.add(8)
    tree.add(9)
    tree.breadth_travel()
    print(" ")
    tree.preorder(tree.root)
    print(" ")
    tree.inorder(tree.root)
    print(" ")
    tree.postorder(tree.root)
    print(" ")

 

内容总结

以上是互联网集市为您收集整理的数据结构和算法第四天~树 ，二叉树全部内容，希望文章能够帮你解决数据结构和算法第四天~树 ，二叉树所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---