数据结构—树和二叉树

数据结构—树和二叉树

数据结构—树和二叉树

• 前言
• 一、树的定义
• • 二、树的基本术语
• 二叉树
• • 二叉树的定义
• 总结

---

前言

  我们知道线性结构的特点是，线性结构它存储的逻辑元素是一对一的，什么是一对一呢？就是元素的前驱和后继的个数都是唯一的，那么对于非线性结构，元素的前驱和后继的个数是不唯一的。对于树形结构来说它的前驱是唯一的，后继就不一定唯一了。图形元素则前驱不唯一，后继也不唯一。本章介绍属性结构

---

一、树的定义

• 树的定义是一个递归的定义（嵌套的定义）

• 树是 n ( n > = 0 ) n(n>=0) n(n>=0)个结点组成的有限集合（记为 T T T）。
    （1）如果 n = 0 n=0 n=0,它是一棵空树，空树中不包含任何结点。
    （2）如果 （ n > 0 ） （n>0） （n>0），此时有且仅有一个特定的称为 根 （ r o o t ） （root） （root） 的结点；当 n > 1 n>1 n>1时，其余结点可以分为 m ( m > = 0 ) m(m>=0) m(m>=0)个互不相交的有限集 T 1 , T 2 , … , T m T1,T2,…,Tm T1,T2,…,Tm，其中每一个子集本身又是一棵树，称为根结点的子树 （ s u b t r e e ） （subtree） （subtree）。

树的表现形式：

二、树的基本术语

树的层数(结点)：根节点的层数为1，其他结点的层数为根节点到该结点的分支数+1
树的高度(深度)：树中结点的最大层数

二叉树

二叉树的定义

总结

期待大家和我交流，留言或者私信，一起学习，一起进步！