ADT

Note

ADT 二叉树(Binary tree) Data

Binary tree是一种n(n >= 0)个节点的有限集。该集合或者为空集(n=0) 或者由一个根节点和两颗互不相交的、分别称为根节点的左子树和右子树的二叉树构成。

每个节点最多两颗子树，二叉树不存在度数大于二的节点。(但有一颗或没有也行)

左右子树有次序。

Operation

endADT

二叉树状态

空树
只有根节点
根节点加左子树
根节点加右子树
根节点加左右子树

Note

二叉树五状态图解
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

A

B

A

C

A

B

C
指向原始笔记的链接

特殊二叉树

斜树

Note

斜树图解
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

B

C

A

B

C
指向原始笔记的链接

满二叉树

又称完美二叉树

所有分支节点都有左子树和右子树(度数一定是2)
叶子都在同一层(最下一层)
同样深度的二叉树中,满二叉树的节点个数最多,同时叶子也最多

Note

满二叉树图解
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

B

C

D

E

F

G
指向原始笔记的链接

严格二叉树

对一颗具有n个结点的二叉树，其节点度数要么是2要么是0

完全二叉树

对一颗具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的节点与同样深度的满二叉树中编号为i的节点位置完全相同，则这个二叉树称为完全二叉树。
叶子节点只会在最下两层
最下层叶子一定集中在左部连续位置
倒数第二层，若有叶子节点，一定都在右部连续位置
完全二叉树是满二叉树的生成树，满二叉树一定是完全二叉树，反之不一定
如果节点度为1，则该节点只有左孩子
同样结点树的二叉树，完全二叉树深度最小

Note

完全二叉树图解
⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠

Text Elements

A

B

D

E

C
指向原始笔记的链接

性质

二叉树的第i层至多有2
深度为k的二叉树至多有(2^k) - 1个节点(k>=1)
任意二叉树T，终端节点n0，度为2的节点数为n2，则n0 = n2+1
具有n个节点的完全二叉树的深度为 $lo g_{2} n + 1$

二叉树存储结构

顺序存储：即用数组存储，但顺序存储方式适用性不强。
二叉树链式存储，二叉链表

具体实现

树体

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

创建

//前序遍历输入数据
void createBinTree(BiTree **T)
{
    char c;
    scanf("%c", &c);
    if(' ' == c)
    {
        *T = NULL;
    }
    else
    {
        *T = (BinTNode*)malloc(sizeof(BiTNode));
        (*T)->data = c;
        CreateBinTree(&(*T)->lchild);
        CreateBinTree(&(*T)->rchild);
    }
}
 
createBinTree(&T);

node* root = NULL;
 
node* insert(root)
 
node* create(int *arr, int n)
{
	for(int i = 0; i < n; i++)
	{
		insert(root, data[i]);
	}
	//return root;
}
 
/*root =*/create(arr, n);

二叉树的遍历

(traversing binary tree)

前序

又可以是树的深度优先搜索(DFS, Depth-first Search) 根->左->右

void preOrderTraverse(BiTree T, int level)
{
    if(T)
    {
        visit(T->data, level);//访问节点的具体操作
        preOrderTraverse(T->lchild, level + 1);
        preOrderTraverse(T->rchild, level + 1);
    }
}

中序左->根->右

void inOrderTraverse(BiTree T, int level)
{
    if(T)
    {
        inOrderTraverse(T->lchild, level + 1);
        visit(T->data, level);//访问节点的具体操作
        inOrderTraverse(T->rchild, level + 1);
    }
}

后序左->右->根

void proOrderTraverse(BiTree T, int level)
{
    if(T)
    {
        proOrderTraverse(T->lchild, level + 1);
        proOrderTraverse(T->rchild, level + 1);
        visit(T->data, level);//访问节点的具体操作
    }
}

层序层序遍历属于广度优先搜索(BFS, Breadth-first Search)，但是广度优先搜索(可以从右子树开始)不一定是树的层序遍历

void levelOrder(Node* t_root)
{
	if(t_root == NULL)return;
	queue<Node*> Q;
	Q.push(t_root);
	while(!Q.empty())
	{
		Node* curr = Q.front();
		cout << curr->data << " ";
		if(curr->left != NULL)
			Q.push(curr->left);
		if(curr->right != NULL)
			Q.push(curr->right);
		Q.pop();
	}
}

获取树的高度

int FindHeight(Node* t_root)
{
	if(t_root == NULL)
	{
		return -1;
	}
	return max(FindHeight(t_root->left), FindHeight(t_root->right)) + 1;
}

树的深度优先搜索

特殊实现

Morris 遍历：用最小的开支完成树的前中后序遍历

线索二叉树

二叉搜索树(BST)

struct BstNode
{
	int data;
	BstNode* left;
	BstNode* right;
};
 
BstNode* GetNewNode(int data)
{
	BstNode* newNode = new BstNode();
	newNode->data = data;
	newNode->left = newi->right = NULL;
}
 
BstNode* Insert(BstNode* t_root, int t_data)
{
	if(root == NULL)
	{
		root = GetNewNode(t_data);
		return root;
	}
	/*
void Insert(BstNode** t_root, int t_data)
{
	if(*t_root == NULL)
	{
		*t_root = GetNewNode(t_data);
	}
	
}
 
Insert(&root, data);
	*/
	else if(t_data <= t_root->data)
	{
		t_root->left = Insert(t_root->left, t_data);
	}
	else
	{
		t_root->right = Insert(t_root->right, t_data);
	}
	return root;
}
 
bool Search(BstNode* t_root, int t_data)
{
	if(t_root = NULL)
		return false;
	else if(t_root->data == t_data)
		return true;
	else if(t_data <= t_root->data)
		return Search(t_root->left, t_data);
	else
		return Search(t_root->right, t_data);
}
 
int main()
{
	BstNode* root;
	root = NULL;
	Insert(root, 15);
	Insert(root, 10);
	Insert(root, 20);
}

查找最大最小值

int findMin(BstNode* t_root)
{
	if(t_root == NULL)
	{
		cout << "Error:Tree is Empty\n";
		return -1;
	}
	BstNode* curr = t_root;
	while(curr->left != NULL)
	{
		curr = curr->left;
	}
	return curr->data;
	/*
	else if(t_root->left == NULL)
	{
		return t_root->data;
	}
	return t_root->data;
	*/
}
 
int findMax(BstNode* t_root)
{
	if(t_root == NULL)
	{
		cout << "Error:Tree is Empty\n";
		return -1;
	}
	BstNode* curr = t_root;
	while(curr->right != NULL)
	{
		curr = curr->right;
	}
	return curr->data;
}

探索

二叉树

ADT

二叉树状态

二叉树五状态图解

Text Elements

特殊二叉树

斜树

斜树图解

Text Elements

满二叉树

满二叉树图解

Text Elements

严格二叉树

完全二叉树

完全二叉树图解

Text Elements

性质

二叉树存储结构

具体实现

树体

创建

二叉树的遍历

获取树的高度

树的深度优先搜索

特殊实现

线索二叉树

二叉搜索树(BST)

查找最大最小值

平衡二叉树

关系图谱

目录

最近的笔记

反向链接