二叉树

布满荆棘的人生 2021-09-10 23:56 214阅读 0赞

二叉树

二叉树是结点有限集合，它必须满足

它是空集，它由一个根结点的左右子树构成，且其左右子树满足二叉树定义

二叉树每个结点的度不大于2

二叉树的子树有左右之分

二叉树的五种基本形态

空

一个结点

只有右子树

只有左子树

有左、右子树

二叉树的性质

二叉树中层数为i的结点之多有2^i个 （i>=0）

高度为k的二叉树中至多有2^k+1个结点（k>=0）

设t是由n个结点构成的二叉树

叶子结点的个数为n0,

度为2的结点的个数为n2

则n0 = n2 +1

满二叉树

一棵树高度为k的满二叉树，是具有(2^k+1)-1个结点且高度为k的二叉树

完全二叉树

一颗具有n个结点，高度为k的二叉树

树种所有结点对应高度为k的满二叉树中编号由1至的那些结点

设若将一颗具有n个结点的完全二叉树按层次次序从1开始编号，则队编号为i（i<=i<=n）的结点有

若i<>1，则编号为i的结点的父节的编号为i/2

若2i<=n，则编号为i的结点的左孩子的编号为2i，否则无左孩子

若2i+1<=n,则i结点的右孩子结点编号为2i+1，否则i无右孩子

具有n个结点的完全二叉树的高度是 ![Center][]

二叉树的实现

顺序存储结构

完全二叉树的顺序存储

一般二叉树的顺序存储

链式存储

二叉树的结点结构

<table> 
 <tbody> 
  <tr> 
   <td>left</td> 
   <td>data</td> 
   <td>right</td> 
  </tr> 
 </tbody> 
</table>

![20160519192814096][]

class BinTreeNode//结点结构

\{

friend class BinTree;

private:

BinTreeNode \*left;

BinTreeNode\*right;

public:

T data;

\}

//构造函数

BinTreeNode(cont T&item, BinTreeNode \*lptr = NULL,BinTreeNode \*rptr = NULL:data(item),left(lptr),right(rptr))\{\}

BinTreeNode \*getleft()

\{return left;\}//返回左孩子

BinTreeNode \*right()

\{return right;\}//返回右孩子

//更新结点

void setleft(BinTreeNode \*l)

\{left = l;\}

void setright(BinTreeNode \*l)

\{right = R;\}

class BinTree

\{

private:

BinTreeNode \*root; //指向根节点

T stop ; // 输入stop时，终止节点的输入

BinTreeNode \*father (BinTreeNode \*begin,BinTreeNode \*current)

\}

//从结点begin开始搜索，返回结点current的父结点

[Center]: /images/20210813/89f5d9effbd54130ba973346d73fb86d.png
[20160519192814096]: /images/20210813/2439beba2379448fbc3bb16269cf800d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，214人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】基础二叉树、真二叉树、满二叉树、完全二叉树、二叉树的遍历

目录树的介绍树（Tree）的基本概念二叉树（Binary Tree）真二叉树（Proper Binary Tree）满二叉树（Fu

柔情只为你懂/ 2022年12月27日 14:28/ 0 赞/ 217 阅读

相关二叉树二叉树遍历通过二叉树遍历求得二叉树

什么是二叉树 > > 二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且

偏执的太偏执、/ 2022年12月04日 01:08/ 0 赞/ 206 阅读

相关数据结构_满二叉树、完全二叉树、二叉排序树、平衡二叉树

一、满二叉树除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。或者说：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。或者说，如

客官°小女子只卖身不卖艺/ 2022年11月05日 11:00/ 0 赞/ 198 阅读

相关二叉树中完全二叉树、满二叉树、二叉排序树、平衡二叉树的区别和联系

1，完全二叉树：只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置。 2，满二叉树：是一颗完全二叉树；除了叶结点外每一个结

╰半橙微兮°/ 2022年09月24日 14:23/ 0 赞/ 196 阅读

相关二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B数，B-树，B+树，B*树（二）

二叉树，完全二叉树，满二叉树，二叉排序树，平衡二叉树，红黑树，B数，B-树，B+树，B\树（一）： [http://blog.csdn.net/yuxin6866/ar

左手的ㄟ右手/ 2022年07月17日 02:09/ 0 赞/ 211 阅读

相关二叉树（四）---查找二叉树

上次我说了如何去遍历一棵二叉树，今天我来说一说查找二叉树是怎样实现的。首先我来介绍一下查找二叉树是怎样生成的。这个是我为我的二叉树设置的一些基础的组成数据结构

深碍√TFBOYSˉ_/ 2022年05月25日 09:37/ 0 赞/ 189 阅读

相关二叉树应用_打印二叉树

题目：从上往下打印二叉树的每个节点，同一层的节点按照从左往右的顺序打印。分析：每次打印一个节点的时候，如果该节点有子节点，就把该节点的子节点放到一个队列的末尾。每次打印队

谁践踏了优雅/ 2022年05月22日 02:46/ 0 赞/ 201 阅读

相关二叉树应用_重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8

喜欢ヅ旅行/ 2022年05月22日 02:37/ 0 赞/ 167 阅读

相关二叉树,完全二叉树,满二叉树,完美二叉树（有图干货）

二叉树：树中每个节点至多有两个子节点【最普通的二叉】 ![70][] 二叉搜索树：对于树中任何节点，如果其左子节点不为空，那么该节点的value值永远 `>=`

柔光的暖阳◎/ 2022年05月14日 02:40/ 0 赞/ 2283 阅读

相关二叉树、满二叉树、完全二叉树、平衡二叉树（AVL树）

二叉树： -------------------- 二叉树由节点（node）和边组成。节点分为根节点、父节点、子节点。二叉树是每个结点最多有两个子树的树结构。 ![

柔情只为你懂/ 2021年12月23日 23:37/ 0 赞/ 431 阅读