树结构是一种非常重要的非线性结构,该结构中一个数据元素可以有两个或两个以上的直接后继元素,树可以用来描述客观世界中广泛存在的层次结构关系。
树与二叉树的定义
- 1.树的定义
树是n(n≥0)个节点的有限集合,当n=0时称为空树。在任一非空树(n>0)中,有且仅有一个称为根的节点;其余节点可分为m(m≥0)个互不相交的有限集T 1 ,T 2 ,...,T m ,其中每个T i 又都是一棵树,并且称为根节点的子树。
树的定义是递归的,它表明了树本身的固有特性,也就是一棵树由若
干棵子树构成,而子树又由更小的子树构成。
该定义只给出了树的组成特点,若从数据结构的逻辑关系角度来看,树中元素之间有明显的层次关系。对树中的某个节点,它最多只和上一层的一个节点(即其双亲节点)有直接的关系,而与其下一层的多个节点(即其孩子节点)有直接关系。通常,凡是分等级的分类方案都可以用具有严格层次关系的树结构来描述。
image.png
- 2.树的基本概念
(1)双亲、孩子和兄弟:节点的子树的根称为该节点的孩子;相应地,该节点称为其子节点的双亲。具有相同双亲的节点互为兄弟。
(2)节点的度:一个节点的子树的个数记为该节点的度。
(3)叶子节点:也称为终端节点,指度为0的节点。
(4)内部节点:度不为0的节点称为分支节点或非终端节点。除根节点之外,分支节点也称为内部节点。
(5)节点的层次:根为第一层,根的孩子为第二层,依此类推,若某节点在第i层,则其孩子节点在第i+1层。
(6)树的高度:一棵树的最大层次数记为树的高度(或深度)。
(7)有序(无序)树:若将树中节点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
- 3.二叉树的定义
二叉树是n(n≥0)个节点的有限集合,它或者是空树(n=0),或者是由一个根节点及两棵不相交的且分别称为左、右子树的二叉树所组成。可⻅,二叉树同样具有递归性质。
特别需要注意的是,尽管树和二叉树的概念之间有许多联系,但它们是两个不同的概念。树和二叉树之间最主要的区别是:二叉树节点的子树要区分左子树和右子树,即使在节点只有一棵子树的情况下,也要明确指出该子树是左子树还是右子树。另外,二叉树节点最大度为2,而树中不限制节点的度数。
image.png
实战：请实现二叉排序树及其中序遍历
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# 技术支持：dwz.cn/qkEfX1u0 项目实战讨论QQ群630011153 144081101
# CreateDate: 2020-1-14
class Node:
def __init__(self, data):
self.left = None
self.right = None
self.data = data
# Insert Node
def insert(self, data):
if self.data:
if data < self.data:
if self.left is None:
self.left = Node(data)
else:
self.left.insert(data)
elif data > self.data:
if self.right is None:
self.right = Node(data)
else:
self.right.insert(data)
else:
self.data = data
# Print the Tree
def print_tree(self):
if self.left:
self.left.print_tree()
print( self.data),
if self.right:
self.right.print_tree()
# Inorder traversal
# Left -> Root -> Right
def mid_traversal(self, root):
res = []
if root:
res = self.mid_traversal(root.left)
res.append(root.data)
res = res + self.mid_traversal(root.right)
return res
# Inorder traversal
# Left -> Root -> Right
def mid_traversal_stack(self, root):
stack = []
result = []
node = root
while node or stack:
if node:
stack.append(node)
node = node.left
else:
node = stack.pop()
result.append(node.data)
node = node.right
return result
root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.mid_traversal(root))
print(root.mid_traversal_stack(root))
网友评论