本文共 1765 字,大约阅读时间需要 5 分钟。
立即学习:
1.2 树和二叉树
树:
1、树定义:是n(>=0)个结点的有限集合,n=0时称为空树。
任一非空树的特点:
有且仅有一个称为根的结点;
其余的结点可分为m(m>=0)个互不相交的子集T1,T2,...,Tm,其中每个子集本身又是一棵树,并称为根结点的子树。
2、其他基本概念:
- 双亲和孩子
- 兄弟:具有相同双亲的结点互为兄弟。
- 结点的度:一个结点的子树的个数记为该结点的度。
- 树的度:树中各结点的度的最大值。
- 叶子结点:也称为终端结点,指度为零的结点。
- 内部结点:度不为零的结点称为分支结点或非终端结点。除根结点外,分支结点也称为内部结点。
- 结点的层次:根为第一层,根的孩子为第二层,以此类推。
- 树的高度:一棵树的最大层次数记为树的高度(或深度)。
- 有序(无序)树:若将树中的结点的各子树看成是从左到右具有次序的,即不能交换,则称该树为有序树,否则称为无序树。
- 森林:是m(m>=0)棵互不相交的树的集合。
3、树的存储结构:(了解)
- 标准存储结构:结点的数据,指向子结点的指针
- 带逆存储结构:结点的数据,指向子结点的指针,指向其父结点的指针
4、树的遍历
遍历是指对树中所有结点信息的访问,即依次对树中每个结点访问一次且仅访问一次。
ps:树没有中序遍历。二叉树才有。
- 前序遍历(先根遍历):从根节点开始,从左向右依次访问子树(递归的定义)
- 后序遍历(后根遍历)
- 层次遍历:从上到下,从左到右依次访问
二叉树(非常重要)
1、定义:二叉树(BinaryTree)是n(n>=0)个结点的有限集合,它或者是空树(n=0),或者是一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树所组成。
二叉树与树的区别:
- 二叉树的结点的最大度为2,而树不限制结点的度。
- 二叉树的结点的子树要区分左子树和右子树
2、二叉树的性质(记住,非常重要)
若2i>n,则结点i无左孩子,否则其左孩子为2i。
若2i+1>n,则结点无右孩子,否则其右孩子为2i+1。
若深度为k的二叉树有2的k次方个结点,则称其为满二叉树。
深度为k、有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树编号从1至n的结点一一对应时,称之为完全二叉树。
- 二叉树第i层上的结点数目最多为2的(i-1)(i>=1)
- 深度为k的二叉树至多有2的k次方-1个结点(k>=1)
- 在任意一棵二叉树中,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1
- 具有n个结点的玩去二叉树的深度为log以2为底n的下限+1
- 对一棵有n个结点的完全二叉树的结点按层次自左至右进行编号,则对任一结点i有: 若i=1,则结点i是二叉树的根,无双亲,若i>1,则其双亲为i/2取下限。
3、二叉树的存储结构
- 顺序存储结构 对完全二叉树既简单又节省空间,而对于一般二叉树则不适用。
- 链式存储结构 由于二叉树中结点包含有数据元素、左子树根、右子树根及双亲等信息,因此可以用三叉链表或二叉链表来存储二叉树。链表的头指针指向二叉树的根节点。
4、二叉树的遍历(必须掌握,自己能写出二叉树的各个遍历)
- 前序遍历(先根,根结点,从左到右)
- 后序遍历(先根节点,再根,从左到右)
- 中序遍历(也叫中根遍历)(先左子树(左根节点-根,右根节点),再根,再右子树)
5、二叉排序树
又称为二叉查找树,定义:或者是一棵空树,或者具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于它的根节点的值;
- 若右子树不空,则右子树上所有结点的值均大于或等于他的根节点的值;
- 左右子树也分别俄日二叉排序树。
6、平衡二叉树
又被称为AVL树,具有以下的性质:
它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。
7、线索树
n个结点的二叉树链表中含有n+1个(2n-(n-1)=n+1)个空指针域。利用二叉链表中的空指针域,存放指向结点在某种遍历次序下的前趋和后继结点的指针(这种附近的指针称为“线索”)。
8、最优二叉树
给定n个权值作为n的叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈弗曼树(Huffman tree)。哈弗曼树是带权路径长度最短的树,权值较大的结点离根较近。(用处:城市安排管道)
转载地址:https://blog.csdn.net/z583706/article/details/104161964 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!