数据结构树

本文章的所有代码和相关文章， 仅用于经验技术交流分享，禁止将相关技术应用到不正当途径，滥用技术产生的风险与本人无关。 本文章是自己学习的一些记录。

开始

树的概念： 树是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点有零个或多个子节点； 没有父节点的节点称为根节点； 每一个非根节点有且只有一个父节点； 除了根节点外，每个子节点可以分为多个不相交的子树； 比如说： 中国就是根节点

树的术语

例如：

B的度是3，它下面有3个子节点；树的度为3，也就是B为最大的节点的度；K,J,L,O,P为叶节点；D的兄弟节点为E,F;树的高度和深度为5，就是一层一层的数就可以；D和H为堂兄弟节点。

数的种类

其中二叉树是最为常见的一种数的结构

完全二叉树： 除去第四层，其他各层的节点数目均已达到了最大值。

满二叉树： 所有的节点都满足最大值的条件

二叉树特性

例如： 性质1：在第2层最多有2*(2-1),也就是2个节点； 性质2：这棵树深度为4 ，最多的时候为满二叉树： 第0层为2的0次，第1层为2的1次，第2层为2的2次，第3层为2的3次 -1，所以至多有2^k - 1个结点（k>0） 性质3： 其叶节点数N0为5,分别为H,I,J,F,G. 度数为2的节点数N2为4，分别为：A,B,C,D. 则N0=N2+1 性质4： 例如这个满二叉树的节点数为7 所以完全二叉树的深度必为 log2(7+1) 为4 性质5： 编号为i为2的父节点B，其左孩子D的编号为2i为4，右孩子E的编号为2i+1为5

二叉树的建立以及插入操作

按照广度优先遍历的方式去在最末尾添加

#coding=utf-8 #@Time:2020/10/5 8:59 #@Author:csdn@hijacklei #@File:二叉树的实现.py #@Software:PyCharm # 树的插入操作 class Node(object): '''定义节点''' def __init__(self,item): self.elem=item #定义左孩子 self.lchild=None #定义右孩子 self.rchild=None class Tree(object): '''二叉树''' def __init__(self): self.root=None def add(self,item): #构造出节点node node=Node(item) # 如果是空树的话，直接让跟节点等于node if self.root is None: self.root=node return #队列操作 查找是队列操作 queue=[self.root] # 判断条件当队列中的元素不为空时，一直可以执行取出操作并且进行左孩子和右孩子的判断 while queue: #先从队列中取出来一个节点 从队列的头部去取 cur_node=queue.pop(0) #从队列中弹出元素 if cur_node.lchild is None: cur_node.lchild=node return else: queue.append(cur_node.lchild) if cur_node.rchild is None: cur_node.rchild=node return else: queue.append(cur_node.rchild) tree=Tree()

首先构建节点Node写为一个类，定义3个属性； 其次构建树的类Tree,遍历操作构建树；

参考资料：传智播客数据结构