1.什么是树
属于非线性数据结构结构的一种，树的定义：n个节点组成的有限集合。n=0，空树；n>0,1个根节点，m个互不相交的有限集，每个子集为根的子树。
2.树的基本术语
路径长度：路径经过节点数目减1
二叉树
1. 二叉树简介
二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。
每一个结点中最多拥有一个左结点和一个右结点，并没有多余的结点，这是很明显的二叉树的特征
image.jpeg
2. 二叉树的特点
由二叉树定义以及图示分析得出二叉树有以下特点：
1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
2）左子树和右子树是有顺序的，次序不能任意颠倒。
3）即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
3. 二叉树的性值
二叉树具有以下几种特征
性质1：二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
性质2：深度为k的二叉树至多有2{k}-1个结点(k≥1)。
性质3：包含n个结点的二叉树的高度至少为log2 (n+1)。
性质4：在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1。
4. 几种特殊的二叉树
- 斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。
- 满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
- 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
构建二叉树
一颗二叉树的结点设计一定要有如下内容：
a)结点元素，data域，用来存储数据，其可以是int，char等基本的类型，同时也可以是struct等这些复杂的复合数据类型。
b)左孩子结点，left指针，总是用来指向当前结点的下一层的左边结点，其属于一种指针。
c)右孩子结点，right指针，总是用来指向当前结点的下一层的右边结点，其属于一种指针。
d)父结点（可选），parent指针，总是指向当前结点的前一个结点，简称父亲结点，其不属于必须结点设计，省略掉可以打扰节省内存的效果，而使用则可以更方便进行定向搜索。
python实现二叉树
随机生成的tree二叉树,结果可以自己执行查看
from binarytree import tree
from binarytree import bst
from binarytree import heap
from binarytree import build
# tree 随机生成的二叉树，默认height=3, is_perfect=False
my_tree= tree()
print(my_tree)
# bst 随机生成的二叉树，默认深度为3，不是完全二叉树
my_bst = bst()
print(my_bst)
# heap 随机生成的二叉树，默认height=3, is_max=True, is_perfect=False
my_heap = heap()
print(my_heap)
# 自己随机生成的二叉树,注意有子节点的地方不能是None，否则会报错'parent node missing at index {}'.format(parent_index))
list_a = [1,2,3,4,5,6,None,None,8,None,None,9]
res = build(list_a)
print(res)
使用binarytree.Node该类来构建自己的树
from binarytree import Node
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.left.left.left = Node(7)
print(root)
Node代码的初始方法：
def __init__(self, value, left=None, right=None):
if not isinstance(value, numbers.Number):
raise NodeValueError('node value must be a number')
if left is not None and not isinstance(left, Node):
raise NodeTypeError('left child must be a Node instance')
if right is not None and not isinstance(right, Node):
raise NodeTypeError('right child must be a Node instance')
self.value = self.val = value
self.left = left
self.right = right
输出如图：
image.png
检查树属性
from binarytree import Node
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(9)
root.right.left = Node(6)
root.left.left.left = Node(7)
print(root)
# 树的高度
h = root.height
print("树的高度是：{0}".format(h))
# 树是否是平衡二叉树
r = root.is_balanced
print("树是否是平衡二叉树：{0}".format(r))
# Return the total number of leaf nodes
l = root.leaf_count
print("叶子节点数：{0}".format(l))
m1 = root.max_leaf_depth
print("最大叶子深度：{0}".format(m1))
m2 = root.max_node_value
print("最大节点值：{0}".format(m2))
m3 = root.min_leaf_depth
m4 = root.min_node_value
print("最小叶子深度：{0}".format(m3))
print("最小节点值：{0}".format(m4))
# Return the total number of nodes in the binary tree
s = root.size
print("总节点数：{0}".format(s))
# "Return the leaf nodes of the binary tree,返回列表
r1 = root.leaves
# Return the nodes in the binary tree level by level,返回列表
r2 = root.levels
print(r1)
print(r2)
使用不同的算法遍历树
from binarytree import Node
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(9)
root.right.left = Node(6)
root.left.left.left = Node(7)
print(root)
# 先序(前序)遍历 先根再左再右
b2 = root.preorder
print(b2)
# 中序遍历 先左再根再右
b1 = root.inorder
print(b1)
# 后序遍历 先左再右再根
b3 = root.postorder
print(b3)
# 层序遍历
b4 = root.levelorder
print(b4)
print(list(root))
网友评论