找外包公司做网站,台州网站制作策划,徐州网站设计价位,西安网站优化效果目录 什么是遍历二叉树 根据遍历序列确定二叉树
例题#xff08;根据先序中序以及后序中序求二叉树#xff09; 遍历的算法实现
先序遍历
中序遍历
后序遍历
遍历算法的分析
二叉树的层次遍历
二叉树遍历算法的应用
二叉树的建立
复制二叉树 计算二叉树深度 计算二…目录 什么是遍历二叉树 根据遍历序列确定二叉树
例题根据先序中序以及后序中序求二叉树 遍历的算法实现
先序遍历
中序遍历
后序遍历
遍历算法的分析
二叉树的层次遍历
二叉树遍历算法的应用
二叉树的建立
复制二叉树 计算二叉树深度 计算二叉树结点总数 什么是遍历二叉树
遍历定义-- 顺着某一条搜索路径巡访二叉树中的结点使得每个结点均被访问一次而且仅被访问一次(又称周游)。
“访问”的含义很广可以是对结点作各种处理如输出结点的信息、修改结点的数据值等但要求这种访问不破坏原来的数据结构。
遍历目的-- 得到树中所有结点的一个线性排列。
遍历用途--它是树结构插入、删除、修改、查找和排序运算的前提是二又树一切运算的基础和核心。
遍历方法 依次遍历二叉树的三个组成部分便是遍历了整个二叉树。
若规定先左后右则只有三种情况 由二叉树的递归定义可知遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。
先序DLR遍历二叉树的操作定义
(1)访问根结点
(2)先序遍历左子树
(3)先序遍历右子树。
注根的左子树遍历完左子树的左子树、左子树的右子树...才轮到根的右子树进行遍历。 示例如下 中序遍历二叉树的操作定义
若二叉树为空则空操作否则
1中序遍历左子树
2访问根结点
3中序遍历右子树。
示例 后序遍历二叉树的操作定义
若二叉树为空则空操作;否则
(1)后序遍历左子树
(2)后序遍历右子树
(3)访问根结点。 示例
例题 解析
先序 先根结点A再遍历根A的左子树左子树遍历完才轮到遍历右子树左子树的根B再根B的左子树以D为根再根D的左子树没有就根D的右子树G根G的左子树和右子树都没有根D的树遍历完再根B的右子树没有就可以遍历根A的右子树了根C的左子树先遍历以根E的树根E的左子树没有遍历根E的右子树以H为根的左子树和右子树都没有遍历根C的右子树以F为根的左右子树都没有先序遍历结束。
中序先以A为根的左子树再B为根的左子树再以D为根的左子树没有就输出根D再根D的右子树G输出以B为根的左子树结束就输出根B再遍历B的右子树没有就输出根A再遍历根A的右子树以C为根的左子树再以E为根的左子树没有就输出根E根E的右子树H根H的左子树没有输出根H根H的右子树没有根C的左子树遍历完毕输出根C再遍历根C的右子树以F为根的左子树没有输出根F根F的右子树没有。
后序以A为根的左子树先遍历以B为根的左子树先遍历以D为根的左子树先遍历没有就遍历根D的右子树根G的左子树不存在右子树也不存在后序输出根结点G根D的左右子树都遍历完了输出根结点DB的左子树遍历完遍历其右子树右子树不存在输出根结点B根A的左子树遍历完遍历其右子树根C的左子树先遍历根E的左子树先遍历不存在遍历根E的右子树根H的左右子树都不存在输出根结点HE的左右子树都遍历完输出根结点EC的左子树遍历完遍历其右子树根F的左右子树都不存在输出根结点F根C的左右结点都遍历完输出根结点C根A的左右子树都遍历完输出根结点A。
请写出下图所示二叉树的先序、中序和后序遍历顺序。 根据遍历序列确定二叉树
若二叉树中各结点的值均不相同则二叉树结点的先序序列、中序序列和后序序列都是唯一的。由二叉树的先序序列和中序序列或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树
例题根据先序中序以及后序中序求二叉树
已知先序和中序序列求二叉树
例已知二叉树的先序和中序序列构造出相应的二叉树
先序A B C D E F G H I J
中序C D B F E A I H G J 首先从先序中可以知道这棵大树的根为A已知根A后从中序序列中可以得知C D B F E是这棵大树的左子树I H G J是这棵大树的右子树再从先序序列中B C D E F得知B是左子树的根G H I J是右子树的根再从中序序列中可以知道C D是根为B的树的左子树F E是右子树以此类推可以构造相对应的二叉树。
已知后序和中序序列求二叉树 例已知一棵二叉树的
中序序列B D C E A F H G
后序序列D E C B H G F A请画出这棵二叉树。 类似的我们可以先从后序序列中知道这棵大树的根结点为A再从中序序列中得知B D C E是以A为根结点的左子树F H G是其右子树再从后序序列D E C B中知道B是左子树的根结点F是左子树H G F的根结点再从中序序列可以得出以B为根结点的树没有左子树其右子树为D C E以F为根结点的左子树不存在其右子树为H G以此类推可以画出完整的二叉树。 遍历的算法实现
先序遍历 步骤 先序的遍历序列为ABCD
算法实现
Status PreOrderTraverse(BiTree T)
{if (T NULL)return OK;//空二叉树else{visit(T);//访问根结点PreOrderTraverse(T-lchild);//递归遍历左子树PreOrderTraverse(T-rchild);//递归遍历右子树}
} 过程指针T指向我们的二叉树的根结点把根结点的指针T传递给前序遍历判断T是否为空此时不为空输出A结点的数据域上的值然后对左子树进行先序遍历将当前结点的左孩子的地址传递给它自身调用自身函数后输出当前指针的数据域的值也就是B结点的值接下来访问B结点的左子树为空返回然后再访问B的右子树此时T指向D结点不为空输出其值D结点的左右子树都为空返回依次返回到以A结点的树其左子树遍历完毕继续遍历其右子树。 中序遍历 步骤 中序遍历序列BDAC
算法实现
Status InOrderTraverse(BiTree T)
{if (T NULL)return OK;else{InOrderTraverse(T-lchild);//递归遍历左子树visit(T);//访问根结点InOrderTraverse(T-rchild);//递归遍历右子树}
}
后序遍历 步骤 后序遍历序列DBCA
算法实现
Status PostOrderTraverse(BiTree T)
{if (T NULL)return OK;else{PostOrderTraverse(T-lchild);//递归遍历左子树PostOrderTraverse(T-rchild);//递归遍历右子树visit(T);//访问根结点}
}
遍历算法的分析 如果去掉输出语句从递归的角度看三种算法是完全相同的或说这三种算法的访问路径是相同的只是访问结点的时机不同。 从虚线的出发点到终点的路径上每个结点经过3次。
第1次经过时访问先序遍历
第2次经过时访问中序遍历
第3次经过时访问后序遍历 二叉树的层次遍历 第一个访问根结点a然后从左到右访问第二层a的孩子b和f再访问孩子的孩子。 对于一棵二叉树从根结点开始按从上到下、从左到右的顺序访问每一个结点。
每一个结点仅仅访问一次。 算法设计思路使用一个队列 1、将根结点进队 2、队不空时循环从队列中出列一个结点*p访问它
若它有左孩子结点将左孩子结点进队若它有右孩子结点将右孩子结点进队。 遍历描述首先根结点a入队 队列开始出队第一个结点是
aa出队然后把a的左右孩子b、f入队再从队列中拿出最前一个结点b出队把它的左右孩子c、d入队再拿出f出队把它的左孩子g入队现在队列中还有cdg把c出队它的左右孩子入队没有就拿下一个结点出队以此类推。
代码实现 使用队列类型定义如下
typedef struct
{BTNode data[MaxSize];//存放队中元素int front, rear;//队头和队尾指针
}SqQueue; //顺序循环队列类型
二叉树层次遍历算法
void LevelOrder(BTNode* b)
{BTNode* p;SqQueue* qu;InitQueue(qu);//初始化队列enQueue(qu,b);//根结点指针进入队列while (!QueueEmpty(qu)){deQueue(qu,p);//出队结点printf(%c,p-data);//访问结点pif (p-lchild ! NULL)enQueue(qu,p-lchild);//有左孩子时将其出队if (p-rchild ! NULL)enQueue(qu, p-rchild);//有右孩子时将其出队}
}
二叉树遍历算法的应用
二叉树的建立
按先序遍历序列建立二叉树的二叉链表
例已知先序序列为ABCDEGF
1从键盘输入二叉树的结点信息建立二叉树的存储结构
2在建立二叉树的过程中按照二叉树先序方式建立 用#表示空字符
代码实现
Status CreateBiTree(BiTree T)//链式存储
{scanf(ch);//cinch;if (ch #)T NULL;else{if (!(T(BiTNode*)malloc(sizeof(BiTree))))//从内存当中分配一个结点空间exit(OVERFLOW);//Tnew NiTNode;T-data ch;CreateBiTree(T-lchild);//构造左孩子CreateBiTree(T-rchild);//构造右孩子}return OK;
}//CreateBiTree
复制二叉树
如果是空树递归结束
否则申请新结点空间复制根结点
递归复制左子树递归复制右子树
代码实现
int Copy(BiTree T, BiTree NewT)
{if (T NULL){NewT NULL;return 0;//如果是空树返回0}else{NewT new BiTNode; NewT-data T-data;//复制结点数据Copy(T-lchild, NewT-lchild);//递归复制左子树Copy(T-rchild, NewT-rchild);//递归复制右子树}
} 计算二叉树深度
如果是空树则深度为0否则递归计算左子树的深度记为m递归计算右子树的深度记为n二叉树的深度则为m与n的较大者加1。
代码实现
int Depth(BiTree T) {if (T NULL)return 0;else {m Depth(T-lchild);//求左子树的深度n Depth(T-rchild);//求右子树的深度if (m n)return (m 1);else return (n 1);}
} 计算二叉树结点总数 如果是空树则结点个数为0否则结点个数为左子树的结点个数右子树的结点个数再1。
代码实现
int NodeCount(BiTree T) {if (T NULL)return 0;else return NodeCount(T-lchild) NodeCount(T-rchild) 1;
}
计算二叉树叶子结点数
如果是空树则叶子结点个数为0否则为左子树的叶子结点个数右子树的叶子结点个数。
代码实现
int LeadCount(BiTree T) {if (T NULL) return 0;if (T-lchild NULL T-rchild NULL)return 1;//如果是叶子结点返回1elsereturn LeafCount(T-lchild) LeafCount(T-rchild);
}
