树结构是一种非常重要的非线性结构,该结构中一个数据元素可以有两个或两个以上的直接后继元素,树可以用来描述客观世界中广泛存在的层次结构关系。

树与二叉树的定义

• 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-14class 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))

原著是一个有趣的人,若有侵权,请通知删除