二叉树的定义:
二叉树是n个结点的有限集合,该集合或者为空集,或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树具有五种基本的形态:
特殊的二叉树
二叉树的顺序存储结构:
二叉树的顺序存储结构就是用一维数组存储二叉树中的结点,并且结点的存储位置,也就是数组的下标要能体现结点之间的逻辑关系,比如双亲与孩子的关系,左右兄弟的关系。
使用顺序存储结构表现二叉树的时候,在其线性结构中,会存在一些空结点,但是其会占据一定的内存空间,会造成存储空间的浪费;所以,顺序存储结构一般只用于完全二叉树。
二叉树的链式存储结构:
由于二叉树的每个结点最多有两个孩子,所以为每个结点设计一个数据域和两个指针域,通常将其称之为二叉链表。
二叉链表的结点结构定义代码:
- typedef char TElemType;
- typedef struct BinaryTreeNode{
- TElemType data;
- //lchild指向左结点的指针
- //rchild指向右结点的指针
- struct BinaryTreeNode *lchild,*rchild;
- }BinaryTreeNode,*BinaryTree;
二叉树的遍历
二叉树的遍历是指从根结点出发,按照某种次序一次访问二叉树中所有结点,使得每个结点被访问一次且仅被访问一次。
二叉树的遍历方法:
1.首先创建一棵二叉树
构建二叉树,向结点的数据域中添加字符。
- void CreateBinaryTree(BinaryTree *T){
- TElemType ch;
- cin>>ch;
- if (ch=='$'){
- *T=NULL;
- }else{
- *T=new BinaryTreeNode;
- if (!*T)return;
- (*T)->data=ch;
- CreateBinaryTree(&(*T)->lchild);
- CreateBinaryTree(&(*T)->rchild);
- }
- }
2.二叉树的前序遍历算法
- void PreOrderTraverse(BinaryTree T){
- if (T==NULL){
- cout<<"#"<<" ";
- return;
- }
- cout<<T->data<<" ";
- PreOrderTraverse(T->lchild);
- PreOrderTraverse(T->rchild);
- }
3.二叉树的中序遍历算法
- void InOderTraverse(BinaryTree T){
- if(T!=NULL){
- cout<<"#"<<" ";
- return;
- }
- InOderTraverse(T->lchild);
- cout<<T->data<<" ";
- InOrderTraverse(T->rchild);
- }
4.二叉树的后序遍历算法
- void PostOrderTraverse(BinaryTree T){
- if (T->NULL){
- cout<<"#"<<" ";
- return;
- }
- PostOrderTraverse(T->lchild);
- PostOrderTraverse(T->rchild);
- cout<<T->data<<" ";
- }
前序遍历、中序遍历和后序遍历算法的核心算法大致相同,都是利用了函数递归的原理。这里顺带补充一下关于函数递归调用的原理:
裴波那契数列的实现来讲解函数的递归调用,假设存在这样一个函数:
使用递归实现裴波那契数列代码如下:
- int Fibonacci(int i){
- if (i<2){
- return i==0?0:1;
- }
- return Fibonacci(i-1)+Fibonacci(i-2);
- }
通过二叉树的结构来分析递归调用的执行过程:(摘自大话数据结构 P103页)
主函数中的测试代码如下:
- //测试代码int main()
- {
- BinaryTree tree = new BinaryTreeNode;
- cout << "构建一颗由字符构成的二叉树,#代表空" << endl;
- CreateBinaryTree(&tree);
- cout << "二叉树的前序遍历输出" << endl;
- PreOderTraverse(tree);
- cout << endl;
- cout << "二叉树的中序遍历输出" << endl;
- InOderTraverse(tree);
- cout << endl;
- cout << "二叉树的后序遍历输出" << endl;
- PostOderTraverse(tree);
- cout << endl;
- return 0;
- }
输出如下图所示:
假设输入这样一个二叉树数据结构:
代表当前节点的数据域为空
ABD#J##EK###CFL###G##
距离上一轮Pre-A轮融资还不到8个月的时间,近日融合云服务商OneCloud(北京云联万...
海外服务器近些年受到许多用户的青睐,其中最受青睐的则是香港云服务器之类的香...
【51CTO.com快译】如果IT专业人士对于如何获得首席信息官的职位撰写简历而感到困...
本文转载自微信公众号「moon聊技术」,作者moon聊技术。转载本文请联系moon聊技...
很多人在租用香港服务器的时候都有考虑过要不要更新系统,在这里,香港服务器小...
日本 云服务器就是指服务器架设在日本地区,所使用的网络是日本网络的云服务器。...
近日,据媒体报道,2020年感恩节周末,富士康于2020年11月29日左右在位于墨西哥...
很多企业网站用户一年花了一两万租用一台服务器,居然是跟别人共享使用的虚拟VPS...
【51CTO.com快译】如果我们回顾过去的五年,我们会发现许多惊人的技术进步。智慧...
此前《中国区块链技术和应用发展白皮书》中显示,阿里巴巴以49的专区块链利总量*...