7. 数据结构—二叉树(链式存储)

2024-08-23 04:28

本文主要是介绍7. 数据结构—二叉树(链式存储),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 内容

包括链式存储二叉树的 递归与非递归实现的先序、中序以及后序遍历、层序遍历、创建二叉树、计算深度、总节点数。

2. 实现代码

注意:只是伪代码,如果想要运行的话在细节方面需要自己修正,栈和队列的方法实现需要引进或者使用其C++自带的功能函数。

#include<bits/stdc++.h>
using namespace std;typedef char ElemType;typedef struct BiTNode{ElemType data;       //数据域 struct BiTNode *lchild,*rchild;  //左右孩子指针 
}BiTNode,  *BiTree;//1. 先序遍历(根左右)->递归实现 
void PreOrderTraverse(BiTree T){if(T){cout<<T->data;PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);} 
}// 先序遍历(根左右)-> 栈实现
void PreOrderTraverse(BiTree T){BiTree p=T;  //指向当前访问数的位置InitStack(S);  //存储根,便于回溯while(p||!StackEmpty(S)){if(p){cout<<p->data;Push(S,p);p=p->lchild;}else{   //需要将p指针进行回溯 Pop(S,p);p=p->rchild; } } 
} //2.中序遍历(左根右)->递归实现 
void InOrderTraverse(BiTree T){if(T){InOrderTraverse(T->lchild);cout<<T->data;InOrderTraverse(T->rchild);} 
}//中序遍历(左根右)->栈实现
//思路:找到最左边的节点输出之后,通过栈找到最近的根,修改指针回溯 
void InOrderTraverse(BiTree T){InitStack(S);   //初始化栈S,用于记录最近的根,便于回溯BiTree p=T;     //记录遍历位置while(p||!StackEmpty(S)){if(p){    //找到最左边的节点 Push(S,p);p=p->lchild;}else{       Pop(S,p);cout<<p->data;   //输出最左边节点的值p=p->rchild;     //实现回溯 }} 
}//3.后序遍历(左右根)->递归实现 
//使用栈实现和前面先中序逻辑差不多,但是必须得左子树和右子树访问完了之后才能访问根,更麻烦(有时间再写) 
void PostOrderTraverse(BiTree T){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);cout<<T->data;}
}//4.层序遍历(使用队列)
void LevelOrderTraverse(BiTree T){BiTree p;InitQueue(Q);EnQueue(Q,T);while(!QueueEmpty(Q)){DeQueue(Q,p);cout<<p->data;if(p->lchild!=NULL)EnQueue(p->lchild);if(p->rchild!=NULL)EnQueue(p->rchild);}
}//5. 使用先序遍历创建二叉树(不存在左右子树需要输入#表示) 
//其余遍历只需将位置改变一下即可,不再赘述 
void CreateBiTree(BiTree &T){char ch;cin>>ch;if(ch=='#')T=NULL;else{T=new BiTNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
} //6.计算二叉树的深度
//递归左子树和右子树的深度,选择最大的+1即可
int Depth(BiTree T){if(T==NULL) return 0;int m=Depth(T->lchild);int n=Depth(T->rchild);return max(m,n)+1;
} //7.统计二叉树节点的个数
int NodeCount(BiTree T){if(T==NULL) return 0;return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} 

这篇关于7. 数据结构—二叉树(链式存储)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1098342

相关文章

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

【数据结构】——原来排序算法搞懂这些就行,轻松拿捏

前言:快速排序的实现最重要的是找基准值,下面让我们来了解如何实现找基准值 基准值的注释:在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分。 在此我们采用三数取中法,也就是取左端、中间、右端三个数,然后进行排序,将中间数作为枢纽值。 快速排序实现主框架: //快速排序 void QuickSort(int* arr, int left, int rig

6.1.数据结构-c/c++堆详解下篇(堆排序,TopK问题)

上篇:6.1.数据结构-c/c++模拟实现堆上篇(向下,上调整算法,建堆,增删数据)-CSDN博客 本章重点 1.使用堆来完成堆排序 2.使用堆解决TopK问题 目录 一.堆排序 1.1 思路 1.2 代码 1.3 简单测试 二.TopK问题 2.1 思路(求最小): 2.2 C语言代码(手写堆) 2.3 C++代码(使用优先级队列 priority_queue)

《数据结构(C语言版)第二版》第八章-排序(8.3-交换排序、8.4-选择排序)

8.3 交换排序 8.3.1 冒泡排序 【算法特点】 (1) 稳定排序。 (2) 可用于链式存储结构。 (3) 移动记录次数较多,算法平均时间性能比直接插入排序差。当初始记录无序,n较大时, 此算法不宜采用。 #include <stdio.h>#include <stdlib.h>#define MAXSIZE 26typedef int KeyType;typedef char In

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树: 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr

速了解MySQL 数据库不同存储引擎

快速了解MySQL 数据库不同存储引擎 MySQL 提供了多种存储引擎,每种存储引擎都有其特定的特性和适用场景。了解这些存储引擎的特性,有助于在设计数据库时做出合理的选择。以下是 MySQL 中几种常用存储引擎的详细介绍。 1. InnoDB 特点: 事务支持:InnoDB 是一个支持 ACID(原子性、一致性、隔离性、持久性)事务的存储引擎。行级锁:使用行级锁来提高并发性,减少锁竞争

【408数据结构】散列 (哈希)知识点集合复习考点题目

苏泽  “弃工从研”的路上很孤独,于是我记下了些许笔记相伴,希望能够帮助到大家    知识点 1. 散列查找 散列查找是一种高效的查找方法,它通过散列函数将关键字映射到数组的一个位置,从而实现快速查找。这种方法的时间复杂度平均为(

PHP实现二叉树遍历(非递归方式,栈模拟实现)

二叉树定义是这样的:一棵非空的二叉树由根结点及左、右子树这三个基本部分组成,根据节点的访问位置不同有三种遍历方式: ① NLR:前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR:中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN:后序遍历(PostorderT

浙大数据结构:树的定义与操作

四种遍历 #include<iostream>#include<queue>using namespace std;typedef struct treenode *BinTree;typedef BinTree position;typedef int ElementType;struct treenode{ElementType data;BinTree left;BinTre