树是一种比较重要的数据结构,尤其是二叉树。二叉树是一种特殊的树,在二叉树中每个节点最多有两个子节点,一般称为左子节点和右子节点(或左孩子和右孩子),并且二叉树的子树有左右之分,其次序不能任意颠倒。本篇博客将详细为大家解析二叉树。
首先介绍两个概念:
满二叉树:在一棵二叉树中,如果所有分支结点都有左孩子和右孩子结点,并且叶子结点都集中在二叉树的最下层,这样的树叫做满二叉树
如:
完全二叉树:若二叉树中最多只有最下面两层的结点的度数可以小于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); } }
画出其运行状态图:
相关推荐
二叉树详解以及应用例子,需要的话可以下载来看看
堆、完全二叉树详解源码
博文测试用例,博文链接:https://blog.csdn.net/qq_44075108/article/details/115583744
线索二叉树
关于数据结构中树与二叉树相关内容详解,包括概念以及实例等等
这是stanford大学计算机专业一位教授写的,讲得非常清晰透彻,代码用C和Java来实现
学习数据结构的C++源码,包含AVL树、Treap、多个有序链表合并、二叉查找树、二项堆、红黑树、伸展树、跳表、栈与队列相互模拟以及最小(大)值求解,可做参考学习
博文配对测试代码 博文链接:https://blog.csdn.net/qq_44075108/article/details/115551237?spm=1001.2014.3001.5501
二叉树详解二叉树知识文档详解下载二叉树知识文档详解下载
主要介绍了JavaScript数据结构和算法之二叉树详解,本文讲解了二叉树的概念、二叉树的特点、二叉树节点的定义、查找最大和最小值等内容,需要的朋友可以参考下
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回...
平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
二叉树概念: java二叉树的每个根节点最多有两颗字数,不存在子树大于2的节点,也就是说,二叉树是节点的最大度数为2的树,通常子树分为左子树和右子树,次序不能颠倒。 创建二叉树: public void createTree...
二叉树是最基本的数据结构,这里我们在Python中使用类的形式来实现二叉树并且用内置的方法来遍历二叉树,下面就让我们一起来看一下Python实现二叉树结构与进行二叉树遍历的方法详解
6.1排序二叉树 详解 6.2售票系统 详解 6.3树的重量 详解 6.4信号放大器 简析 6.5“访问”术馆 简析 6.6聚会的快乐 简析 6.7重建道路 简析 6.8有线电视网 简析 6.9 TWO 简析 第七章 搜索 7.1最多因子数 ...
二叉树.doc 二叉树.doc 二叉树.doc 二叉树详解
二叉树的遍历
详解平衡二叉树:平衡二叉树的概念,算法思想,程序源码