树和二叉树

2018-04-24 本文已影响54人 _Caesar

什么是树？

树状图是一种数据结构，它是由(n>=1）个有限节点组成一个具有
层次关系的集合，把它叫做"树"把它们叫做“树”是因为它看起来像一颗倒挂的树,也就是说它是根朝上，而叶朝下的它具有这些特点;
每个节点都有零个或多个子节点；没有父节点的称为根节点；除了根节点外,每个子节点可以分为多个不相交的子树；

图片.png

树是包含n(n>0)个节点的有穷集,其中；

每个元素称为节点
有一个特定的结点被称为根或者树根
除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree).

二叉树

什么是二叉树？
二叉树，就是度不差过2的树（节点最多有两个叉）

图片.png

三.两种特殊的二叉树

1.满二叉树
一个二叉树，如果每一个层的节点数都到达最大值，则这个二叉树就
是满二叉树.
2.完全二叉树
叶节点只能出现在最下层,并且最下面一层的节点都集中在该层最左边的
若干位置的二叉树

图片.png

满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树

三.二叉树的存储方式

1链式存储方式

二叉树的链式存储：将二叉树的节点定义为一个对象，节点之间通过类似链表的链接方式来连接.

from collections import deque   #双向队列
from queue import Queue    #单向队列

# import queue
# q = queue.Queue()
# q.put('ggg')
# q.get()
class BiTreeNode:
    def __init__(self,data):
        self.data = data
        self.lchild = None
        self.rchild = None

    @classmethod
    def pre_order(self,root):
        '''前序遍历(根左右)'''
        if root: #如果有根节点
            print(root.data,end='')
            self.pre_order(root.lchild)
            self.pre_order(root.rchild)

    @classmethod
    def in_order(self,root):
        '''中序遍历(左根右)'''
        if root:
            self.in_order(root.lchild)
            print(root.data,end='')
            self.in_order(root.rchild)

    @classmethod
    def out_order(self, root):
        '''后序遍历(左右根)'''
        if root:
            self.out_order(root.lchild)
            self.out_order(root.rchild)
            print(root.data, end='')

    @classmethod
    def level_order(self,root):
        '''层次遍历(第一层，第二层，第三层...借助队列来实现)'''
        queue = deque()
        queue.append(root)
        while len(queue) > 0:
            node = queue.popleft()
            print(node.data,end='')
            if node.lchild:
                queue.append(node.lchild)
            if node.rchild:
                queue.append(node.rchild)



#创建二叉树
a = BiTreeNode("A")
b = BiTreeNode("B")
c = BiTreeNode("C")
d = BiTreeNode("D")
e = BiTreeNode("E")
f = BiTreeNode("F")
g = BiTreeNode("G")
e.lchild = a
e.rchild = g
a.rchild = c
c.lchild = b
c.rchild = d
g.rchild = f
root = e

#查看前序遍历的结果
BiTreeNode.pre_order(root)   #EACBDGF
print('')
BiTreeNode.in_order(root)    #ABCDEGF
print('')
BiTreeNode.out_order(root)  #BDCAFGE
print('')
BiTreeNode.level_order(root)  #EAGCFBD

2顺序存储方式

图片.png

1.父节点和左孩子节点编号下标有什么关系？
如果已知父亲节点为i，那么他的左孩子节点为2i+1

图片.png

2.父节点和右孩子节点的编号下标有什么关系？

图片.png
3,，反过来知道孩子找父亲

(n-1）/2=i
(n-2)  /2=i

四.二叉搜索树

1.定义

二叉搜索树是一颗二叉树切满足性质：设x是二叉树的一个节点.如果y是x左子树的一个节点，那么y.key<=x.key,如果y是x右子树的一个节点,那么y.key>=X.ky(x.ky代表x节点对应的值）
通俗的说也就是若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

图片.png

2,原理

二叉树查找过程和次优二叉树类似,通常采用二叉链表作为二叉树的存储
结构,中序遍历二叉树可得到一个关键字的有序序列，一个无序序列，可以通过构造一颗二叉排序树变成一个有序序列,构造树的过程即为对无序序列进行排序的过程,每次插入的新的节点都是二叉树上新的叶子节点，在进行插入操作时，不必移动其它节点，只需要改动某一个节点的指针，由空变为非空既可，搜索，插入，删除的复杂度等于树高.o(log(n)