织梦dede建站教程视频,活动策划书模板范文,网站建设app小程序,自己做网站创业目录
一. 遍历二叉树
#xff08;1#xff09;三种遍历方式
#xff08;2#xff09;递归遍历算法
#xff08;3#xff09;非递归遍历算法
#xff08;4#xff09;层次遍历算法
二. 基于递归遍历算法的二叉树有关算法
#xff08;1#xff09;二叉树的建立 …目录
一. 遍历二叉树
1三种遍历方式
2递归遍历算法
3非递归遍历算法
4层次遍历算法
二. 基于递归遍历算法的二叉树有关算法
1二叉树的建立
2二叉树的复制
3二叉树的深度计算
4计算二叉树中的结点数
5计算二叉树中的叶子结点数
三. 线索二叉树 一. 遍历二叉树
遍历定义——顺着某一条搜索路径巡访二叉树中的结点使得每个结点均被访问一次而且仅被访问一次又称周游。这里“访问”的含义很广可以是对结点作各种处理如输出结点的信息、修改结点的数据值等但要求这种访问不破坏原来的数据结构。
遍历目的——得到树中所有结点的一个线性排列。
遍历用途——它是树结构插入、删除、修改、查找和排序运算的前提是二叉树一切运算的基础和核心。
1三种遍历方式
由于二叉树有根结点D左子树L右子树R只要依次访问这三部分就可以遍历这个二叉树。规定先左后右即必须先访问左子树再访问右子树则根据什么时候访问根结点有DLR——先根序遍历LDR———中根序遍历LRD———后根序遍历三种遍历方式。 由二叉树的递归定义可知遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。 先序遍历的过程图解1 先序遍历的过程图解2 中序遍历的过程图解 后序遍历的过程图解 若二叉树中各结点的值均不相同则二叉树结点的先序序列、中的序列和后序列都是唯一的。 下面我们考虑逆过程由二叉树的先序序列和中序序列或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树只知道前序和后序序列不可以。
原理先序后序序列的第一个最后一个一定是根结点根结点在中序序列中把整个序列分为两部分左边序列是左子树右面序列是右子树。依此类推。 2递归遍历算法
下面以先序遍历为例写出递归算法代码。具体解释如下 首先判断二叉树是否为空即 TNULL如果为空则直接返回return OK因为空树没有节点可遍历。 如果二叉树不为空首先对当前节点 T 进行访问操作visit(T)即对根节点进行处理。 然后通过递归调用 PreOrderTraverse 函数来遍历当前节点的左子树T-Ichild即对左子树进行前序遍历。 接着再通过递归调用 PreOrderTraverse 函数来遍历当前节点的右子树T-rchild即对右子树进行前序遍历。
这样通过递归的方式可以依次访问二叉树的根节点、左子树和右子树实现了前序遍历。
需要注意的是visit(T) 表示对节点 T 进行访问操作具体的操作可以根据实际需求来定义。
void PreOrderTraverse(BiTree T){ //前序遍历if(TNULL) return OK; //空二叉树这里OK理解为退出到上一层else{visit(T);//访问根结点PreOrderTraverse(T-Ichild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}
}同样我们可以很容易的写出中序遍历和后序遍历的算法代码
void PreOrderTraverse(BiTree T){ //中序遍历if(TNULL) return OK; //空二叉树else{PreOrderTraverse(T-Ichild);//递归遍历左子树visit(T);//访问根结点PreOrderTraverse(T-rchild);//递归遍历右子树}
}void PreOrderTraverse(BiTree T){ //后序遍历if(TNULL) return OK; //空二叉树else{PreOrderTraverse(T-Ichild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树visit(T);//访问根结点}
}如果去掉输出语句从递归的角度看三种算法是完全相同的或说这三种算法的访问路径是相同的只是访问结点的时机不同。从图中虚线出发白点代表左子树或者右子树为空每个结点都经过了3次。第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历。 遍历算法的时间复杂度O3nOn每个结点访问一次
空间复杂度On对每一个经过但不访问的结点我们都要找个空间存起来最坏的情况就是除了根结点外其他所有结点都在右子树上这时候存全部n个结点。
3非递归遍历算法
以中序遍历为例二叉树中序遍历的非递归算法的关键在中序遍历过某结点的整个左子树后如何找到该结点的根以及右子树。 基本思想中序遍历左子树根结点后进先出
建立一个栈根结点进栈遍历左子树左子树全部访问完毕根结点出栈输出根结点遍历右子树。 栈的变化情况A进-B进-B出-D进-D出-A出-C进-C出
写出代码具体步骤解释如下 首先声明一个辅助指针 p 和一个栈 S用于存储节点和辅助遍历。 初始化栈 S即将栈置空。 将根节点 T 赋值给指针 p即将 p 指向根节点。 进入循环判断条件为 p 非空或者栈 S 非空。只要满足这个条件就继续遍历二叉树。 在循环中首先判断当前节点 p 是否非空。如果非空则将其入栈Push(S,p)并将 p 指向其左子树p p-lchild。 如果当前节点 p 为空即左子树为空说明已经到达最左边的叶子节点。此时需要从栈中弹出一个节点Pop(S,q)。 对弹出的节点 q 进行访问操作这里使用 printf 打印出节点的数据printf(%c,q-data)。 将指针 p 指向节点 q 的右子树p q-rchild继续遍历右子树。 重复步骤 4-8直到遍历完整个二叉树。 最后当指针变量p指向NULL且工作栈中没有元素说明整个二叉树遍历结束跳出整个while循环返回状态值 OK表示函数执行成功。
Status InOrderTraverse(BiTree T){BiTree p,q; //弄两个指针 InitStack(S); //初始化一个工作栈pT; //让p指向树的根结点while(p||!StackEmpty(S)){ //StackEmpty()栈为空返回TRUE否则返回FALSEif(p){Push(S,p);p p-lchild;}else{Pop(S,q); printf(“%c”,q-data);p q-rchild;}}//while
return OK;
}4层次遍历算法
二叉树的层次遍历对于一颗二叉树从根结点开始按从上到下、从左到右的顺序访问每一个结点。每一个结点仅仅访问一次。 算法设计思路使用队列。 I. 将根结点进队 II. 队不空时循环从队列中出列一个结点*p访问它依次执行下面两步
若它有左孩子结点将左孩子结点进队;若它有右孩子结点将右孩子结点进队。
队列变化过程a进队-a出队b,f依次进队-b出队c,d依次进队-f出队g进队-c出队-d出队e进队-g出队h进队-e出队-h出队
使用队列定义类型如下
typedef struct{BTNode data[MaxSize]; //存放队中元素int front,rear; //队头和队尾指针
}SqQueue; //顺序循环队列类型给出算法代码解释如下 首先声明一个指针 p 和一个队列 qu用于存储节点和辅助遍历。 初始化队列 qu即将队列置空。 将根结点 b 入队列enQueue(qu,b)即将根节点放入队列中。 进入循环判断条件为队列 qu 非空。只要队列非空就继续遍历二叉树。 在循环中首先从队列中出队列一个节点deQueue(qu,p)并对该节点进行访问操作这里使用 printf 打印出节点的数据printf( %c, p-data)。 然后判断当前节点 p 的左子节点是否非空。如果非空则将其入队列enQueue(qu,p-lchild)。 接着判断当前节点 p 的右子节点是否非空。如果非空则将其入队列enQueue(qu,p-rchild)。 重复步骤 4-7直到遍历完整个二叉树。 最后返回结果。
void LevelOrder(BTNode *b) {BTNode *p; //p指向队列头部用于出队列SqQueue qu;InitQueue(qu); //初始化队列enQueue(qu,b); //根结点指针进入队列while(!QueueEmpty(qu)){ //队不为空则循环deQueue(qu,p); //出队结点pprintf( %c, p-data); //访问结点pif (p-Ichild!NULL) enQueue(qu,p-lchild); //有左孩子时将其进队if (p-rchild!NULL) enQueue(qu,p-rchild); //有右孩子时将其进队}
}二. 基于递归遍历算法的二叉树有关算法
1二叉树的建立
以先序遍历为例分两步进行(1)从键盘输入二叉树的结点信息建立二叉树的存储结构(2)在建立二叉树的过程中按照二叉树先序方式建立 先序遍历ABCDEGF有不同的树所以加上空结点就有唯一的树结构 Status CreateBiTree(BiTree T){ //建立二叉树传入指针类型scanf(ch); //从键盘输入C中cinch;if(ch “#”) TNULL;else{if(!(T(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW); //C中Tnew BiTNode;T-data ch; //生成根结点CreateBiTree(T-Ichild); //构造左子树CreateBiTree(T-rchild); //构造右子树}return OK; //同理这里return到上一层调用
} //CreateBiTree这段代码是用来创建二叉树的函数。函数的输入参数是一个指向二叉树根节点的指针T。首先通过scanf函数读取一个字符ch作为输入。如果ch等于#表示当前节点为空将T指向NULL。否则进入else语句块。在else语句块中首先通过malloc函数为当前节点分配内存空间并将分配的地址赋值给T。如果分配内存失败则程序退出。然后将当前节点的数据域赋值为ch。接下来递归调用CreateBiTree函数创建当前节点的左子树将左子树的根节点地址赋值给T-lchild。然后再次递归调用CreateBiTree函数创建当前节点的右子树将右子树的根节点地址赋值给T-rchild。最后函数返回OK表示创建二叉树成功。
利用上面的代码输入ABC##DE#G##F###就可建立下面的二叉树链表。 2二叉树的复制
int Copy(BiTree T,BiTree NewT){if(T NULL){ //如果是空树返回0NewT NULL;return 0;}else{NewT new BiTNode; //建立新结点NewT指针指向它NewT-data T-data; //传入数据Copy(T-lChild,NewT-lchild); //递归调用复制左子树Copy(T-rChild,NewT-rchild); //递归调用复制右子树}
}这段代码是一个递归函数用于复制二叉树。函数的参数是原始二叉树T和目标二叉树NewT通过引用传递返回值为0表示复制成功。需要注意的是在函数中使用了引用传递来传递目标二叉树NewT的地址这是为了能够在函数内部修改目标二叉树NewT的指针以便将复制得到的子树链接到正确的位置上。
3二叉树的深度计算
int Depth(BiTree T){if(TNULL) return 0; //如果是空树返回0else{m Depth(T-lChild);n Depth(T-rChild);if(mn) return (m1);else return(n1);}
}这段代码是一个递归函数用于计算二叉树的深度。函数的参数是二叉树T返回值为二叉树的深度。首先函数会检查二叉树T是否为空即是否为叶子节点。如果是空树即T为NULL那么二叉树的深度为0函数直接返回0。
如果二叉树T不为空那么函数会递归调用自身分别计算左子树和右子树的深度并将结果分别赋值给变量m和n。接下来函数会比较左子树的深度m和右子树的深度n的大小。如果m大于n说明左子树更深那么函数返回m1表示整个二叉树的深度为左子树的深度加1。如果n大于等于m说明右子树更深或者左右子树深度相等那么函数返回n1表示整个二叉树的深度为右子树的深度加1。
最终当递归调用完成后函数会返回整个二叉树的深度。
4计算二叉树中的结点数
int NodeCount(BiTree T){if(T NULL)return 0;elsereturn NodeCount(T-lchild)NodeCount(T-rchild)1;
}如果是空树即T为NULL那么二叉树中节点的数量为0函数直接返回0。
如果二叉树T不为空结点个数左子树结点数量右子树结点数量当前节点即加1。
5计算二叉树中的叶子结点数
int LeadCount(BiTree T){if(TNULL) //如果是空树返回0return 0;if (T-Ichild NULL T-rchild NULL)return 1; //如果是叶子结点返回1elsereturn LeafCount(T-lchild) LeafCount(T-rchild);
}如果是空树则叶子结点个数为0 否则为左子树的叶子结点个数右子树的叶子结点个数。
三. 线索二叉树
当用二叉链表作为二叉树的存储结构时可以很方便地找到某个结点的左右孩子但一般情况下无法直接找到该结点在某种遍历序列中的前驱和后继结点。为了解决这个问题一般有以下解决方案
通过遍历寻找——费时间再增设前驱、后继指针域——增加了存储负担。利用二叉链表中的空指针域。
这里我们重点介绍最后一种。首先回忆下二叉树链表中空指针域的数量具有n个结点的二叉链表中一共有2n个指针域每个结点有左右指针域两个因为n个结点中有n-1个孩子即2n个指针域中有n-1个用来指示结点的左右孩子其余n1个指针域为空。
如果某个结点的左孩子为空则将空的左孩子指针域改为指向其前驱如果某结点的右孩子为空则将空的右孩子指针域改为指向其后继。这种改变指向的指针称为“线索加上了线索的二叉树称为线索二叉树(Threaded Binary Tree)。 为区分lrchid和rchild指针到底是指向孩子的指针还是指向前驱现白后继的指针对二叉链表中每个结点增设两个标志域Itag 和rtag并约定
ltag 0 lchild指向该结点的左孩子ltag 1 lchild指向该结点的前驱rtag 0 rchild指向该结点的右孩子rtag 1 rchild指向该结点的后继
这样结点的结构就由5部分组成 typedef struct BiThrNode{int data;int Itag, rtag;struct BiThrNode *Ichild,*rchild;
}BiThrNode,*BiThrTree;先序遍历的线索二叉树 后序遍历的线索二叉树 为避免有些指针处于悬空状态增设了一个头结点这个头结点还是BiThrNode类型 ltag0, lchild指向根结点 rtag1, rchild指向遍历序列中最后一个结点 遍历序列中第一个结点的lc域和最后一个结点的rc域都指向头结点
这样改进完的线索二叉树如下
