树-二叉树
-
定义: 满足以下两个条件:
- 每个结点至多只有二颗子树(即度都不大于2)。
- 二叉树的子树有左右之分，其次序不能任意颠倒。
-
基本概念:
- 满二叉树：深度为k且2^k-1个结点的二叉树。
- 完全二叉树：深度为k,结点树为n的二叉树，其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一对应。
-
二叉树的性质:
-
性质1：在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。
-
性质2：深度为k的二叉树至多有2^k-1个结点(k>=1)。
-
性质3： 对任意一颗二叉树T，若叶子结点数目为n0,而度数为2的结点树为n2,则n0=n2+1。
-
性质4：具有n个结点的完全二叉树的深度为(log2n)(向下取整)+1。
-
性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对二叉树中的所有结点从1开始编号，则队友任意的序号为i的结点有:
-
当i=1, 则序号为i的结点是根结点，无双亲结点；当i>1,则序号为i的结点的双亲结点序号为i//2。
-
当2*i>n,则序号为i的结点无左孩子；当2*i<=n,则序号为i的结点的左孩子结点的序号为2*i。
-
当2*i + 1 > n,则序号为i的结点无右孩子；当2*i + 1 <=n,则序号为i的结点的右孩子的结点序号为2*i + 1;
-
-
-
二叉树的存储结构:
-
顺序存储结构:
- 定义：用一组地址连续的存储单元，依次自上而下、自左向右存储完全二叉树上的结点元素，即将完全二叉树编号为i的结点的元素存储在数组的第i-1个分量中。
-
链式存储结构：
在具体运用中，，需要根据二叉树的形态和需要进行的操作来决定二叉树的存储结构。
-
二叉链表存储结构:
typedef struct BiTNode { TElemType data; //数据域 struct BiTNode *LChild; //左孩子域 struct BiTNode *RChild; //右孩子域 ｝BiTNode,*BiTree; 若一个二叉树右n个结点，则它的二叉链表中必还有**2n**个指针域，其中必有**n+1**个空的链域。 -
三叉链表存储结构:
typedef struct BiTNode { TElemType data; //数据域 struct BiTNode *LChild; //左孩子域 struct BiTnode *RChild; //右孩子域 struct BiTnode *parent; //父结点域 ｝BiTNode,*BiTree; 有利于逆向搜索，方便找到孩子结点的父节点。
-
-
-
二叉树的建立
-
二叉链表方式存储的二叉树
-
前提：在创建二叉链表的时候，需要给定二叉树的遍历序列，且空树也要用特定的元素表示出来。叶子结点有两个空树。
- 算法描述：
- 1.给出树的遍历序列(包含空树）
- 2.若输入的值是空树的标记符，执行赋值为NULL，否则依次执行如下3个操作
- 1 创建该结点
- 2 按该方法创建左子树
- 3 按该方法创建右子树
- 具体代码
-
-
-
二叉树的遍历 符号注记:L、D、R分别表示遍历左子树、访问根结点、遍历右子树
-
深度遍历(线性遍历)
-
递归遍历
- DLR(先序遍历)
- 算法描述:若二叉树为空，执行空操作，否则依次执行如下三个操作:
- (1) 访问根结点
- (2) 按先序遍历左子树
- (3) 按先序遍历右子树
- 算法描述:若二叉树为空，执行空操作，否则依次执行如下三个操作:
- LDR(中序遍历)
- 算法描述:若二叉树为空，执行空操作，否者依次执行如下3个操作:
- (1) 按中序遍历左子树
- (2) 访问根结点
- (3) 按中序遍历右子树
- 算法描述:若二叉树为空，执行空操作，否者依次执行如下3个操作:
- LRD(后序遍历)
- 算法描述：若二叉树为空，执行空操作，否则依次执行如下3个操作:
- (1) 按后序遍历左子树
- (2) 按后序遍历右子树
- (3) 访问根结点
- 算法描述：若二叉树为空，执行空操作，否则依次执行如下3个操作:
-
剩下三种遍历是:LRD RDL RLD–>类似
- 具体实现
- DLR(先序遍历)
-
非递归遍历
- DLR(基于栈的递归消除)
- 算法描述: 根据先序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。
- 对于任一结点P：
- (1)访问结点P，并将结点P入栈;
- (2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P，循环至1;若不为空，则将P的左孩子置为当前的结点P;
- (3)直到P为NULL并且栈为空，则遍历结束。
- LDR(基于栈的递归消除)
- 算法描述: 根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。
- 对于任意结点P：
- (1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
- (2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
- (3)直到P为NULL并且栈为空则遍历结束。
- LRD(基于栈的递归消除)
- 算法描述: 根据后序遍历的顺序，对于任一结点，优先访问其右孩子，而右孩子结点又可以看作一根结点，然后继续访问其右孩子结点，直到遇到右孩子为空，才进行访问，然后按相同的规则访问其左子树。
- 对于任一结点P：
- (1) 先将其入栈。如果P不存在左孩子和右孩子,则可以直接访问它；或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点;
- (2) 若非上述两种情况，则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
- (3)直到栈为空，则遍历结束。
-
剩下三种遍历是:LRD RDL RLD–>类似
- 具体实现
- DLR(基于栈的递归消除)
-
-
广度遍历(层次遍历)
- 算法描述如下: 根据层次遍历的思想:从左到右，然后从上到下访问结点元素
- 对于任一结点P：
- (1) 根结点出队，并访问；
- (2) 根结点的左右孩子不能为空，然后依次入队；
- (3) 队列为空，则遍历结束。
- 具体实现
-
-
二叉的应用
- 基本运用
- 输出二叉树中的结点 遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的结点并无次序要求，因此可用上述任何遍历算法中的一种即可。
- 输出二叉树中的叶子结点 条件判断，若左子树或右子树为空，则该结点是叶子结点。
- 统计叶子结点的数目
- 方案1: 使用全局变量保存叶子结点的数目。
- 方案2： 使用静态变量，用返回值的方法把叶子结点个数返回。
- 方案3：使用递归算法，如果是空树，返回；如果只有一个结点；否则为左右子树的叶子结点树之后。
- 二叉树的高度
- 对于任意结点p：
- (1) 若结点为空，则高度为0；
- (2) 否则，其高度应为其左右子树高度的最大值加一。
- 对于任意结点p：
- 具体实现代码
- 拓展应用
- 基本运用