“特殊二叉树”的版本间的差异

来自姬鸿昌的知识库
跳到导航 跳到搜索
第8行： 第8行：
  
 
右子树大于根
 
右子树大于根
 +
 +
 +
  
  
 
对每一个结点而言，它的左孩子小于它自身，右孩子大于它自身。
 
对每一个结点而言，它的左孩子小于它自身，右孩子大于它自身。
 +
  
  
第20行： 第24行：
  
 
3）每一层从左到右进行遍历的序列为从小到大排列的序列。
 
3）每一层从左到右进行遍历的序列为从小到大排列的序列。
 +
 +
 +
  
  
 
插入结点：序列（89，48，56，48，20，112，51）
 
插入结点：序列（89，48，56，48，20，112，51）
  
−
1、若查找二叉树为空数，则以新节点为查找二叉树；
+
1、若查找二叉树为空树，则以新结点为查找二叉树；
  
 
2、将要插入结点值与父结点值比较，确定要放左子树还是右子树中，若子树为空，则作为子树的根结点插入；
 
2、将要插入结点值与父结点值比较，确定要放左子树还是右子树中，若子树为空，则作为子树的根结点插入；
  
 
3、若该键值结点已存在，则不再插入。
 
3、若该键值结点已存在，则不再插入。
 +
 +
 +
 +
 +
二叉查找树为空树，以新结点89为查找二叉树
 +
{| class="wikitable"
 +
!89
 +
|}
 +
 +
 +
将要插入结点值48与父结点值89比较，48<89，放左子树，左子树为空，作为子树的根结点插入；
 +
{| class="wikitable"
 +
! colspan="2" |89
 +
|-
 +
!48
 +
!
 +
|}
 +
 +
 +
 +
将要插入结点值56与根结点值89比较，56<89，放左子树；
 +
 +
左子树不为空，将要插入结点值56与左子树的根结点值48比较，56>48，放右子树；
 +
 +
右子树为空，作为右子树的根结点插入；
 +
{| class="wikitable"
 +
! colspan="3" |89
 +
|-
 +
! colspan="2" |48
 +
!
 +
|-
 +
!
 +
!56
 +
!
 +
|}
 +
 +
 +
 +
键值48的结点已存在，不再插入
 +
{| class="wikitable"
 +
! colspan="4" |89
 +
|-
 +
! colspan="2" |48
 +
! colspan="2" |
 +
|-
 +
!
 +
!56
 +
!
 +
!
 +
|}
 +
 +
 +
 +
将要插入结点值20与根结点值89比较，20<89，放左子树；
 +
 +
左子树不为空，将要插入结点值20与左子树的根结点值48比较，20<48，放左子树；
 +
 +
左子树为空，作为左子树的根结点插入；
 +
{| class="wikitable"
 +
! colspan="4" |89
 +
|-
 +
! colspan="2" |48
 +
! colspan="2" |
 +
|-
 +
!20
 +
!56
 +
!
 +
!
 +
|}
 +
 +
 +
将要插入结点值112与根结点值89比较，112>89，放右子树；
 +
 +
右子树为空，作为右子树的根结点插入；
 +
{| class="wikitable"
 +
! colspan="4" |89
 +
|-
 +
! colspan="2" |48
 +
! colspan="2" |112
 +
|-
 +
!20
 +
!56
 +
!
 +
!
 +
|}
 +
 +
 +
将要插入结点值51与根结点值89比较，51<89，放左子树；
 +
 +
左子树不为空，将要插入结点值51与左子树的根结点值48比较，51>48，放右子树；
 +
 +
右子树不为空，将要插入结点值51与右子树的根结点值56比较，51<56，放左子树；
 +
 +
左子树为空，作为左子树的根结点插入；
 +
{| class="wikitable"
 +
! colspan="5" |89
 +
|-
 +
! colspan="3" |48
 +
! colspan="2" |112
 +
|-
 +
!20
 +
! colspan="2" |56
 +
!
 +
!
 +
|-
 +
!
 +
!51
 +
!
 +
!
 +
!
 +
|}

2022年9月20日 (二) 00:28的版本

https://www.bilibili.com/video/BV1hg411V7Bm?p=61

1）二叉查找树

二叉查找树.png

二叉排序/查找树

左子树小于根

右子树大于根



对每一个结点而言，它的左孩子小于它自身，右孩子大于它自身。


特点：

1）二叉查找树的中序遍历序列为从小到大排列的序列。

2）值最小的结点无左子树，值最大的结点无右子树。

3）每一层从左到右进行遍历的序列为从小到大排列的序列。



插入结点：序列（89，48，56，48，20，112，51）

1、若查找二叉树为空树，则以新结点为查找二叉树；

2、将要插入结点值与父结点值比较，确定要放左子树还是右子树中，若子树为空，则作为子树的根结点插入；

3、若该键值结点已存在，则不再插入。



二叉查找树为空树，以新结点89为查找二叉树

89


将要插入结点值48与父结点值89比较，48<89，放左子树，左子树为空，作为子树的根结点插入；

89
48


将要插入结点值56与根结点值89比较，56<89，放左子树；

左子树不为空，将要插入结点值56与左子树的根结点值48比较，56>48，放右子树；

右子树为空，作为右子树的根结点插入；

89
48
56


键值48的结点已存在，不再插入

89
48
56


将要插入结点值20与根结点值89比较，20<89，放左子树；

左子树不为空，将要插入结点值20与左子树的根结点值48比较，20<48，放左子树；

左子树为空，作为左子树的根结点插入；

89
48
20 56


将要插入结点值112与根结点值89比较，112>89，放右子树；

右子树为空，作为右子树的根结点插入；

89
48 112
20 56


将要插入结点值51与根结点值89比较，51<89，放左子树；

左子树不为空，将要插入结点值51与左子树的根结点值48比较，51>48，放右子树；

右子树不为空，将要插入结点值51与右子树的根结点值56比较，51<56，放左子树；

左子树为空，作为左子树的根结点插入；

89
48 112
20 56
51
取自“https://www.jihongchang.top/index.php?title=特殊二叉树&oldid=2101”