树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。本篇博客将详细为大家解析二叉树。
首先介绍两个概念:
满二叉树:在一棵二叉树中,如果所有分支结点都有左孩子和右孩子结点,并且叶子结点都集中在二叉树的最下层,这样的树叫做满二叉树
如:
完全二叉树:若二叉树中最多只有最下面两层的结点的度数可以小于2,并且最下面一层的叶子结点都是依次排列在该层最左边的位置上,则称为完全二叉树
如:
区别:满二叉树是完全二叉树的特例,因为满二叉树已经满了,而完全并不代表满。所以形态你也应该想象出来了吧,满指的是出了叶子节点外每个节点都有两个孩子,而完全的含义则是最后一层没有满,并没有满。
二叉树的链式存储结构是一类重要的数据结构,定义结果为:
//定义树的结构 struct node { node * lchild; node * rchild; string data; //初始化 node() { lchild=rchild=NULL; } };
二叉树的建立
首先我们用户输入生成一棵二叉树,要生的的二叉树如下图所示:
#代表空结点。
下面我们根据上面图中所示的二叉树,利用先序依次输入ABDG###E#H##C#F##(即先序遍历)
生成二叉树的代码如下:
//二叉树生成--先序遍历输入要生成的二叉树数据,#代表空结点 void CreateTree(node * & root) { char data; cin>>data; if(data!='#') { root=new node; root->data=data; CreateTree(root->lchild); CreateTree(root->rchild); } }
二叉树节点查找
采用递归的方法在二叉树root里查找只为aim的结点,若找到此节点则返回其指针,否则返回NULL
查找代码如下:
//检查二叉树是否包含数据aim,有则返回其指针 node * Findnode(node * & root,string aim) { node * p; if(root==NULL)//空树 return NULL; else if(root->data==aim) return root; else { p=Findnode(root->lchild,aim); if(p!=NULL) return p; else return Findnode(root->rchild,aim); } }
这里解释一下递归中的return的意思:
return 对当前函数来说是结束了,对调用它的父函数来说你这个函数执行完成了,父函数就会接着执行下一语句。
没想到父函数马上又遇到一个return,父函数结束了,对爷爷函数来说父函数执行完成了,爷爷函数就接着执行下一个语句
二叉树遍历
1.先序遍历
先序遍历过程是:
1)访问根结点
2)先序遍历左子树
3)先序遍历右子树
先序遍历代码为:
void PreOrder(node * root)//先序遍历 { if(root!=NULL) { cout<<root->data; PreOrder(root->lchild); PreOrder(root->rchild); } }
2.中序遍历
中序遍历过程是:1)中序遍历左子树
2)访问根结点
3)中序遍历右子树
中序遍历的代码:
void InOrder(node * root)//中序遍历 { if(root!=NULL) { InOrder(root->lchild); cout<<root->data; InOrder(root->rchild); } }
3.后续遍历后序遍历过程是:
1)后序遍历左子树
2)后序遍历右子树3)访问根结点
后序遍历代码为:
void PostOrder(node * root)//后序遍历 { if(root!=NULL) { PostOrder(root->lchild); PostOrder(root->rchild); cout<<root->data; } }
二叉树高度计算
递归解法:
(1)如果二叉树为空,二叉树的深度为0
(2)如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1
代码如下:
int NodeHeight(node * root)//计算二叉树高度 { int lchild,rchlid; if(root==NULL) return 0; else { lchild=NodeHeight(root->lchild); rchlid=NodeHeight(root->rchild); return (lchild>rchlid)?(lchild+1):(rchlid+1); } }
输出二叉树叶子节点
递归解法:
参考代码如下:
void Showleaf(node * root) { if(root!=NULL) { if(root->lchild==NULL&&root->rchild==NULL) cout<<root->data; Showleaf(root->lchild);//输出左子树叶子节点 Showleaf(root->rchild);//输出右子树叶子节点 } }
运行结果为:
附上源代码地址:https://github.com/longpo/algorithm/tree/master/Btree
递归分析
上面源代码中,大量运用了递归算法,
下面我们来分析其中一个递归的过程。
二叉树结构为:
利用先序遍历,即代码为:
void PreOrder(node * root)//先序遍历 { if(root!=NULL) { cout<<root->data; PreOrder(root->lchild); PreOrder(root->rchild); } }
画出其运行状态图:
相关推荐
### 二叉树详解 #### 一、二叉树结构简介 ##### 1.1 定义与概念 二叉树(Binary Tree)是一种常见的数据结构,由一系列节点组成,每个节点包含左指针、右指针以及数据元素。在二叉树中,“根”指针指向树的最顶层...
这篇博文的压缩包文件"二叉树详解(C语言版).rar"包含了对二叉树的详细讲解和相关的C语言实现代码。 首先,我们需要了解二叉树的基本概念。二叉树是由节点构成的非线性数据结构,每个节点包含两个子节点,分别称为...
线索二叉树是一种在二叉树中添加线索以方便遍历的数据结构,它主要用于实现二叉树的前序、中序和后序遍历。在C语言中,线索二叉树的实现通常涉及到指针的高级操作和结构体的设计。下面我们将详细探讨线索二叉树的...
线索二叉树是一种特殊形式的二叉树,其目的是为了在二叉链表结构中方便地查找结点的前驱和后继。在标准的二叉链表中,只有通过特定的遍历(如前序、中序或后序遍历)才能找到结点的前驱或后继。然而,线索二叉树通过...
在IT领域,数据结构是计算机科学的基础,而二叉树作为一种重要的抽象数据类型,被广泛应用于各种算法设计和系统实现中。本资源包是针对C/C++编程语言的二叉树学习材料,涵盖了多种类型的二叉树及其操作,适合作为...
在IT领域,数据结构是计算机科学的基础,而堆和完全二叉树是其中的重要概念。本文将深入探讨这两种数据结构的原理、特性以及C++实现的源码分析。 首先,让我们来理解堆的概念。堆是一种特殊的树形数据结构,通常...
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回...
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
### 平衡二叉树详解:AVL树与伸展树 #### 一、平衡二叉树概述 平衡二叉树是一种特殊的二叉搜索树,它通过维持树的高度平衡来确保树的操作(如查找、插入、删除)具有较高的效率。在非平衡的二叉搜索树中,如果树...
二叉树是一种特殊的树结构,其中每个节点最多有两个子节点,分别称为左子节点和右子节点。在Java中,我们可以用类来表示二叉树的节点,通常包含数据域(存储节点的数据)以及指向左右子节点的引用。在给定的代码中,...
在学习数据结构和算法的过程中,二叉树是一个核心概念,它在计算机科学中有广泛的应用,尤其是在搜索和排序的算法中。本文将深入探讨JavaScript中实现的二叉树概念、特点、节点定义、五种基本形态、特殊二叉树类型、...
《使用Graphviz绘制二叉树详解》 在计算机科学领域,二叉树是一种常见的数据结构,它被广泛应用于各种算法和问题解决中。为了更好地理解和分析二叉树,可视化工具显得尤为重要。Graphviz是一个强大的开源图形渲染库...
二叉树的创建与遍历二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法详解及实例二叉树的创建与遍历算法...
**排序二叉树详解** 排序二叉树,也被称为有序二叉树,是二叉树数据结构的一个特殊类型。在排序二叉树中,每个节点的左子树只包含小于当前节点值的节点,而右子树则包含大于当前节点值的节点。这种特性使得排序...