【資料結構——樹和二叉樹】

一、樹和二叉樹的定義

樹是n個結點的有限集，它或為空樹（n=0）;或為非空樹
在這里插入圖片描述

在這里插入圖片描述

二叉樹是n（n>=0）個結點所構成的集合，他或為空樹（n=0）,或為非空樹，對于非空樹：T
（1）有且只有一個稱之為根的結點；
（2）除根結點之外的其余結點分為兩個互不相交的子集T1和T2，分別稱為T的左子樹和右子樹，且T1和T2本身都是二叉樹，
在這里插入圖片描述

（1）結點的度小于等于2；
（2）有序樹（子樹有左右之分，且其次序不能任意顛倒）
在這里插入圖片描述

在這里插入圖片描述
滿二叉樹：一棵深度為K且有2的K次方-1個結點的二叉樹，（特點：每層都充滿了結點）

完全二叉樹：深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應，

在這里插入圖片描述

實作：按完全二叉樹的結點層次編號，依次存放二叉樹中的資料元素，
特點：
（1）結點間關系蘊含在其存盤位置中；
（2）浪費空間，適于存滿二叉樹和完全二叉樹，

結點i:
雙親結點：【i/2】
左兒子：2i
右兒子：2i + 1

在這里插入圖片描述

#define MAXTSIZE 100   //二叉樹的最大結點數
typedef TElemType SqBiTree[MAXTSIZE];//0號單元存盤根結點
SqBiTree bt;

（1）二叉鏈表

在這里插入圖片描述

typedef struct BiNode
{
	TElemType data;   //資料域
	struct BiNode* lchild, * rchild;   //左右孩子指標
}BiNode,*BiTree;   //二叉樹結點
BiTree root;

在這里插入圖片描述
在n個結點的二叉鏈表中，有n+1個空指標域

（2）三叉鏈表
在這里插入圖片描述

typedef struct TriTNode
{
	TElemType data;   //資料域
	struct TriTNode* lchild,* parent * rchild;   //左右孩子指標
}TriTNode,*TriTree;   //二叉樹結點

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/194577.html

標籤：python

上一篇：Oracle