当前位置: 首页 > 数据结构&&算法 > 正文

数据结构小结(六)树

第六章 树

前言

树的基本概念

为什么要使用树,或者说树有什么优势?

树的基本概念,背景知识。

树的定义

子树

树的表示方法

树的基本术语

结点

结点的度

树的度

叶子结点

内部结点

孩子结点

双亲结点

兄弟结点

堂兄弟

祖先结点

结点的层次

树的深度

前辈

后辈

森林

有序树与无序树

以上就是所有树的定义。

二叉树

二叉树的性质

性质1

性质2

性质3

满二叉树

满二叉树的连续编号

完全二叉树

性质4

性质5

以上性质完毕。

二叉树的存储方式

二叉树的递归方式遍历

先序遍历:

中序遍历:

后序遍历:

二叉树的其他操作

求二叉树的结点数:

求叶子结点的数目

求树的高度

打印叶子结点

使用递归也很方便

递归方法创建二叉树,简单创建

获得一个结点的双亲结点

判断相似二叉树

横向打印二叉树

反转二叉树

 

 

非递归遍历二叉树

先序遍历

中序遍历

后序遍历

按照层来遍历二叉树

方法:主要借助队列完成按照层次遍历二叉树

首先根结点入队,当队列非空

1.队头结点出队,并访问出队结点

2.出队结点的非空左,右孩子依次入队

关于线索二叉树

其实二叉树也可以在逻辑上变成一个链表,我们只需要把所有的结点按照一定的规律排出来。当然在该序列中,每一个结点都有自己的唯一前驱就是它的父结点,并且有唯一后继结点,其实根据遍历的方式不同它的后继结点会有变化。

由以上的思考我们进一步思考如何表示一棵线索二叉树,以前使用的是二叉链表,只有左右孩子并没有可以表示父结点的东西,所以我们对结构体做出修改。

当ltag = 0 指针lchild 指示左孩子,否则指向前驱

当rtag = 0 指针rchild 指示右孩子,否则指向后继

一个中序线索化的示例

在线索二叉树中找结点

这里举个例子就好,其实在线索二叉树中寻找结点已经很类似在链表中查找元素了,逻辑上此时它就是一条链表。

关于树与森林

treetobintree

森林转换二叉树

forsttobintree

二叉树转换为树

bintotree.png

二叉树转换为森林

bintoforst

 

本文固定链接: http://zmrlinux.com/2015/12/20/%e6%95%b0%e6%8d%ae%e7%bb%93%e6%9e%84%e5%b0%8f%e7%bb%93%ef%bc%88%e5%85%ad%ef%bc%89%e6%a0%91/ | Kernel & Me

该日志由 root 于2015年12月20日发表在 数据结构&&算法 分类下, 你可以发表评论,并在保留原文地址及作者的情况下引用到你的网站或博客。
原创文章转载请注明: 数据结构小结(六)树 | Kernel & Me