文章目录
- 二叉树的基本概念
- 二叉树的性质(特性)
- 二叉树的节点表示以及二叉树的创建
-
二叉树的基本概念
二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)
二叉树的性质(特性)
性质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 时为根,除外)
(1)完全二叉树——若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
![在这里插入图片描述](https://img-blog.csdnimg.cn/b263c087b2c34dd9a0efe19680102e85.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASnVseUxpMjAxOQ==,size_13,color_FFFFFF,t_70,g_se,x_16)
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
![在这里插入图片描述](https://img-blog.csdnimg.cn/36e8fcfd503543448318b80c8a4a2712.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBASnVseUxpMjAxOQ==,size_10,color_FFFFFF,t_70,g_se,x_16)
二叉树的节点表示以及二叉树的创建
1.二叉树的节点表示
通过使用Node类中定义三个属性,分别为elem本身的值,还有lchild左孩子和rchild右孩子
class Node(object):
"""节点类"""
def __init__(self, elem=-1, lchild=None, rchild=None):
self.elem = elem
self.lchild = lchild
self.rchild = rchild
2.二叉树的创建
树的创建,创建一个树的类,并给一个root根节点,一开始为空,随后添加节点
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)
if cur.lchild == None:
cur.lchild = node
return
elif cur.rchild == None:
cur.rchild = node
return
else:
queue.append(cur.lchild)
queue.append(cur.rchild)
如果阅读本文对你有用,欢迎一键三连呀!!!
2022年3月22日16:51:31
![在这里插入图片描述](https://img-blog.csdnimg.cn/2dab9919d343486ab4b1f1ae2fdb7f82.gif#pic_center)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)