树和森林(森林的部分已经看不懂了)

￡神魔★判官ぃ 2022-12-26 08:26 106阅读 0赞

树和二叉树  
树的概念:  
结构特点:有且仅有一个根节点无前驱,有一个或多个叶节点无后继  
其余结点有唯一前驱和若干后继

递归描述:空是树,不空时,树由唯一根节点和若干子树组成,  
每个子树满足树的定义

int NodeCount(Tree T)
    {
        
    	if (T == NULL) return 0;
    	else 
    	{
        
    		return 1 + NodeCount(T->lTree) + NodeCount(T->rTree);
    	}
    }

树的相关术语  
空树:  
根节点:  
叶子结点:  
结点的子树  
树的子树  
结点的度:孩子结点的个数(和图有区别)  
树的度  
终端结点  
非终端结点  
内部节点  
结点的层次(从1开始)  
树的深度  
树的宽度  
无序树 有序树  
Tree = (root, F) F = \{T1, …, Tm\}  
Ti = (ri, Fi)  
路径与路径长度(边的个数)  
从根节点到任意节点存在唯一路径

树的抽象数据类型定义  
数据对象  
具有相同特性的数据元素的集合  
数据关系  
若D为空集,则称为空树  
否则:D中存在唯一的称为根的数据元素root  
当 n > 1 时,其余结点可分为m个互不相交的有限集  
其中每一个子集本身又是一棵符合本定义的树,称为根root的子树

操作合集
    InitTree(&T)
    Destroy(&T)
    InsertChild(&T, &p, i, c)
    //插入c为T中p所指结点的第i子树
    CreateTree(&T, definition)
    CreateTree(&T)
    Assign(T, &cure_e, value)
    TreeEmpty(T)
    TreeDepth(T)
    Root(T)
    Value(T, cur_e)
    Parennt(T, cur_e)`在这里插入代码片`
    LeftChild(T, cur_e)
    RightSibling(T, cur_e)
    //求cur_e结点的右兄弟
    TraverseTree(T,visit())

2.1 二叉树  
二叉树:度不大于2的有序树(空树也是二叉树)

2.2 二叉树的性质  
性质1 二叉树 第i层上最多有 2^(i - 1)个结点  
性质2 深度为k的二叉树最多有2^k - 1 个结点  
性质3 对任意二叉树 如果度为0的结点个数为n0,  
度为2的结点个数为n2,则n0 = n2 + 1  
满二叉树:每层结点个数都是最大值  
完全二叉树:满二叉树的最后一层最右边缺少了几个叶子结点  
性质4 含n个结点的完全二叉树的深度为 下取整\[log2n\] + 1  
下取整只能得到 去掉叶子结点的 满二叉树 的层数 还需要再 +1  
性质5 一个节点的编号为i(从1开始), 则左子树根节点的编号为 2 \* i  
右子树根节点的编号为 2 \* i + 1  
双亲结点的编号为 下取整\[i/2\]

二叉树的存储和基本操作  
二叉树的连式存储–二叉链表

typedef struct BiTNode
    {
        
    	TElemType data;
    	struct BiTNode *lTree, *rTree;
    }BiTNode, *BiTree;
    二叉树的常见操作
    创建
    Status CreatBiTree(BiTree T)
    {
        
    	TElemType e;
    	cin >> e;
    	if (e == 0) T == NULL;
    	else
    	{
        
    		T = (BiTNode*)malloc(sizeof(BiTNode));
    		if (!T) exit(OVERFLOW);
    		T->data = e;
    		CreatBiTree(T->lTree);
    		CreatBiTree(T->rTree);
    	}
    	return OK;
    }
    
    销毁
    (没写, 再说)
    
    求树的结点数
    int NodeCount(BiTree T)
    {
        
    	if (T == NULL) return 0;
    	else return 1 + NodeCount(T->lTree) + NodeCount(T->rTree);
    }
    
    求叶子节点数
    int LeafCount(BiTree T)
    {
        
    	if (T->lTree == NULL && T->rTree == NULL) return 1;
    	else 
    	{
        
    		LeafCount(T->rTree) + LeafCount(T->rTree);
    	}
    }
    
    求深度
    int getTreeDepth(BiTree T)
    {
        
    	if (T == NULL) return 0;
    	else
    	{
        
    		return 1 + max(getTreeDepth(T->lTree), getTreeDepth(T->rTree));
    	}
    }
    二叉树的连式存储--三叉链表
    为了方便求一个节点的双亲
    typedef struct TriTNode
    {
        
    	struct TriTNode *parent;
    	TElemType data;
    	struct TriTNode *lTree, *rTree;
    }TriTNode, *TriTree;
    
    二叉树的顺序存储
    [注意]千万不能只将有值的结点存入顺序表,这样会丢失结构信息
    正确的做法是将所有结点,包括无值的结点都要保存
    #define MAX_TREE_SIZE 100
    typedef struct SqBiTree[MAX_TREE_SIZE];
    //鲁老师的办法是零号元素存根节点,但是我认为还是将0号空出来,
    //1号位置存根节点比较好
    
    二叉树的遍历
    Stauts PreOrderTraverse(BiTree T, Status(*visit)(TElemType))
    {
        
    	if (T == NULL) return OK;
    	else
    	{
        
    		visit(T->data);
    		PreOrderTraverse(T->lTree, visit);
    		PreOrderTraverse(T->rTree, visit);
    		return OK;
    	}
    }
    
    Status InOrderTraverse(BiTree T, Status(*visit)(TElemType))
    {
        
    	if (T == NULL) return OK;
    	else 
    	{
        
    		InOrderTraverse(T->lTree, visit);
    		visit(T->data);
    		InOrderTraverse(T->rTree, visit);
    		return OK;
    	}
    }
    
    Status PostOrderTraverse(BiTree T, Staus(*visit)(TElemType))
    {
        
    	if (!T) return OK;
    	else 
    	{
        
    		PostOrderTraverse(T->lTree);
    		PostOrderTraverse(T->rTree);
    		visit(T->data);
    		return OK;
    	}
    }

表达式树:  
从左到右扫描表达式,找到最后一个优先级最低的运算符  
将其放在根节点,左侧子表达式作为左子树,右侧子表达式作为右子树:  
知道两个子树均为数字停止递归  
\[注意\]小括号的运算等级最高

有遍历序列还原二叉树  
先序 + 中序:先序第一个元素x为根,中序中x左侧为x的左子树,  
x的右侧必构成右子树;对子树的处理,第一个在先序序列中出现的元素Y  
为该左子树的根,中序序列中Y元素左侧构成Y的左子树

中序 + 后序:

先序 + 后序:不确定

二叉树的非递归遍历:
    Status InOrderTraverse_NonRec(BiTree T, Status(*visit)(TElemType))
    {
        
    	SqStack S;
    	InitStack(S);
    	Push(S, T);
    	while (!StackEmpty(S))
    	{
        
    		while (GetTop(S, p) && p) Push(S, p->lTree);
    		Pop(S,p);
    		if (!StackEmpty(p))
    		{
        
    			Pop(S, p);
    			(*visit)(p->data);
    			Push(S, p->rTree);
    		}
    	}
    	return OK;
    }

线索二叉树  
背景:如何提高遍历效率

中序线索化一般加头结点, 先序/后序可不加  
头结点: \[LINK\] + lTree + (data) + rTree + \[THREAD\]  
\[注意\]ppt上没写,但是我认为 头结点的结构和 线索二叉树的结点是一样的  
毕竟还是要满足 链式结构的 定义

线索二叉树的结点结构组成: LTag + lTree + data + rTree + RTag  
typedef enum\{LINK, THREAD\}PTag;  
LINK:代表指针值是孩子结点的地址(用来存储二叉树的结构信息的)  
THREAD:代表值是前驱/后继结点的地址(用来存储链表的结构信息的)  
线索二叉树存储结构定义:  
typedef struct BiThrNode  
\{  
TElemType data;  
struct BiThrNode \*lTree, \*rTree;  
PTag LTag, RTag;  
\}BiThrNode, \*BiThrTree;

中序二叉树的遍历:  
重复至p指向头结点  
\{  
找到第一一个应该遍历的点,记入p  
访问p->data  
只要p->RTag为THREAD(链表地址)则令p沿p->rTree前进  
否则,让p指向右子树的根  
\}  
\[\]个人感觉吧,这个遍历方式,其实应该是先访问中序的最左边的结点,然后  
依次访问右边的结点,若当前的结点的右指针是链表地址,那就直接访问该节点,  
并且转移到右指针指向的结点(也就是后驱结点),否则,就通过rTree返回到根节点,  
然后再判断

void InOrderTraverse(BiThrTree T, Status(*visit)(TElemType))
    {
        
    	p = T->child;
    	while (p != T)
    	{
        
    		//找到第一一个应该遍历的点,记入p
    		while (p->LTag == LINK) p = p->lTree;
    		if (!visit(p->data)) return ERROR;
    		while (p->RTag == THREAD && p->rTree != T)
    		{
        
    			p = p->rTree;
    			if (!visit(p->data)) return ERROR;
    		}
    		p = p->rTree;
    	}
    }

树与森林

1.  树和森林的存储表示  
    1.1 树的表示法-双亲表示法  
    typedef char TElemType;  
    \#define MAX\_TREE\_SIZE 100  
    typedef struct PTNode  
    \{  
    TElemType data;  
    int parent;  
    \}PTNode;

typedef struct  
\{  
PTNode nodes\[MAX\_TREE\_SIZE\];  
int r, n;  
\}PTree;

1.1 树的表示法-多重链表表示法  
(1)  
typedef struct TNode  
\{  
TElemType data;  
struct TNode\[childMAX\];  
\}TNode, \*Tree;

typedef struct TNode\{  
TElemType data;  
int degree;  
struct TNode \*child;  
\}TNode, \*Tree;

1.1 输的表示法-多重链表表示法  
//链表结点的定义: 孩子的信息 + 下一个孩子  
typedef struct CTNode  
\{  
int child;  
struct CTNode \*next;  
\}\*ChildPtr;

树的结点: 该节点的信息 + 双亲 + 孩子链表的指针  
typedef struct\{  
TElemType data;  
int parent;  
ChilPTr firstchild;  
\}CTBox;

//树的定义  
typedef struct\{  
CTBox nodes\[MAX\_TREE\_SIZE\];  
int n, r;  
\}CTree;

1.1 树的表示法-孩子兄弟表示法(二叉树表示)  
与二叉树的二叉链表存储结构同构,  
但指针含义不同  
typedef struct CSNode  
\{  
TElemType data;  
struct CSNode \*firstchild;  
struct CSNode \*nextsibling;  
\}CSTNode, \*CSTree;

抽象一下:  
结点的左孩子保存第一个结点的地址,  
右孩子保存孩子结点的兄弟结点  
既然存在这种结构,那就认为他有存在的道理吧

1.2 森林的表示法  
typedef struct CSNode  
\{  
TElemType data;  
struct CSNode \*firstchild;  
struct CSNode \*nextsibling;  
\}CSTNode, \*CSTree;

把两个分开的树开成是 兄弟  
那么根据 孩子兄弟表示法 第一个树的根节点的右孩子  
保存了下一个树的根节点, 然后 依次保存 下一棵树的 根节点  
每棵树再用孩子兄弟表示法保存其子树

2 树/森林与二叉树之间的转化  
2.1 树-二叉链表-二叉树  
一棵二叉树 可以转化成 普通的 二叉树  
也可以通过孩子兄弟表示法 转换成 多叉树  
其中 用孩子兄弟表示法 时:  
结点的 右子树的右子树的…都是这个结点的 兄弟  
左子树 是该节点的 第一个孩子  
再用上述的方法确定 所有 的孩子

2.2 森林-二叉链表-二叉树

1.  树和森林的操作实现  
    3.1 树的遍历  
    遍历 的话 用 孩子兄弟表示法 存储 树  
    树的先根遍历: 遍历二叉链表(先序遍历)  
    程序:同二叉树的先序遍历, lchild 与 rchild 换做  
    firstchild 和 nextsibling  
    遍历序列: 可以直接根据先跟规则写先写根, 然后在一直往下走到底  
    在返回上一个结点,到下一个孩子结点, 继续往下走到底

树的后根遍历:遍历孩子兄弟表示的树 = 遍历二叉链表(中序)  
程序:同二叉树的中序遍历:lchild与rchild 换做 firstchild 和 nextsibling  
遍历序列:可以直接根据后根规则写

3.2 森林的遍历  
森林的先序遍历:比那里孩子兄弟表示的森林 = 遍历二叉链表(先序)  
程序:同二叉树先序遍历, lchild与rchild换做firstchild和nextsibling  
遍历序列:可直接根据先序遍历规则写

森林的中序遍历: (不会,没看懂)

3.3 森林(含树)求深度-分而治之  
递归边界:空森林深度为0  
递归关系:大参林深度为首棵树的深度和余数森林的深度取最大值  
(没看懂)