二叉树遍历算法的应用

心已赠人 2022-01-28 09:23 229阅读 0赞

今天开始复习数据结构，感觉基础的东西一点还不会

“遍历”是二叉树各种操作的基础，通过遍历操作可以把对节点的输出延伸到对节点的判别，计数等操作，可以解决一些关于二叉树其他实际问题，如果在遍历过程生成节点，这样就能建立二叉树的存储结构。  
于是就开始记录书上的基本操作。

1.先序遍历建立二叉链表  
先序遍历的访问顺序是：根左右。

void CreateBiTree(BiTree &T){
    	cin>>ch;
    	if(ch == '#') T=NULL;
    	else{
    	T = new BiTNode;
    	T->data = ch;
    	CreateBiTree(T->lchild);
    	CreateBiTree(T->rchild);
    	}
    }

思考：上面的代码利用的是**先序遍历**顺序来建立节点。并且利用&引用不断连接左右子节点的方向。

2.复制二叉树  
也是利用二叉树的先序遍历

void Copy(BiTree T,BiTree &NewT){
    	if(T==NULL)
    	{
    		NewT = NULL;
    		return;
    		}else{
    		NewT = new BiTNode;
    		NewT->data = T->data;
    		Copy(T->lchild,NewT->lchild);
    		Copy(T->rchild,NewT->rchild);
    		}
    	}

先序遍历

3.计算二叉树的深度  
利用后序遍历，即访问顺序是：**左右根**

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;

结论：利用先访问左子树，再右子树，再根的顺序。

4.统计二叉树种节点的个数  
利用后序遍历顺序

int NodeCount(BiTree T){
    	if(T == NULL)return 0;
    	else{
    	return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
    	}
    }

结论:利用后序遍历。

最好做一题 根据先序和中序构建二叉树的题目。记下。

发表评论取消回复

表情：

评论列表（有 0 条评论，229人围观）

还没有评论，来说两句吧...

相关阅读

相关算法-二叉树遍历

文章目录 * 1. 二叉树遍历 * 2. 二叉树遍历的实现 * * * 2.1 先序遍历 * * 2.1.1 非递归实现 ...

末蓝、/ 2024年04月18日 10:32/ 0 赞/ 87 阅读

相关【算法】二叉树遍历

目录 1.概述 2.代码实现 2.1.二叉树结点定义 2.2.前序遍历 2.2.1.递归算法

太过爱你忘了你带给我的痛/ 2023年10月07日 22:51/ 0 赞/ 35 阅读

相关遍历二叉树的应用

问题一.输出二叉树中的叶节点（左右子都为空）只需在遍历过程中增加一个if语句判断是否为空即可。 void preorderprintleaves(Bintree

淡淡的烟草味﹌/ 2023年07月02日 10:28/ 0 赞/ 9 阅读

相关二叉树遍历算法

文章目录前言二叉树遍历方法前序遍历中序遍历

短命女/ 2023年06月10日 10:23/ 0 赞/ 220 阅读

相关二叉树 n叉树遍历算法

二叉树 // 二叉树的遍历 class TreeNode { int val; TreeNode left;

灰太狼/ 2022年12月09日 05:19/ 0 赞/ 198 阅读

相关二叉树遍历算法总结

文章目录前提要素深度优先搜索DFS 经典遍历算法前序遍历

电玩女神/ 2022年10月08日 05:35/ 0 赞/ 218 阅读

相关二叉树遍历算法总结

二叉树遍历算法总结本文根据《数据结构与算法》(C语言版)(第三版) 整理。 A. 二叉树的遍历 1.前序遍历二叉树： (1)若二叉树为空，则为空操作，

女爷i/ 2022年07月29日 09:23/ 0 赞/ 234 阅读

相关二叉树遍历算法

写在前面二叉树是应用广泛的一类树，通过学习二叉搜索树（BST）、平衡二叉树(AVL)、伸展树(Splay Tree)以及二叉堆(Binary Heap)的相关概念、操作

太过爱你忘了你带给我的痛/ 2022年07月16日 13:20/ 0 赞/ 215 阅读

相关二叉树遍历算法的应用

今天开始复习数据结构，感觉基础的东西一点还不会 “遍历”是二叉树各种操作的基础，通过遍历操作可以把对节点的输出延伸到对节点的判别，计数等操作，可以解决一些关于二叉树其他实际问

心已赠人/ 2022年01月28日 09:23/ 0 赞/ 230 阅读

相关数据结构--二叉树遍历算法的应用

文章目录查询二叉树中的某个节点统计二叉树中叶子节点的个数参数形式全局变量形式返回值形式求二叉树的深度

落日映苍穹つ/ 2022年01月07日 23:27/ 0 赞/ 247 阅读