二叉树

别团等shy哥发育

发布于 2023-02-27 10:33:07

2040

发布于 2023-02-27 10:33:07

文章被收录于专栏：全栈开发那些事

一、二叉树的定义

二叉树是n(n≥0)个结点组成的有限集合。当n=0时，称为空二叉树；当n>0时，该集合由一个根节点及两颗互不相交的，被分别成为左子树和右子树的二叉树组成。二叉树可以理解为满足以下条件的树形结构。

每个结点的度不大于2
结点每颗子树的位置是明确区分左右的，不能随意改变。由上述定义可看出：二叉树中的每个结点只能有0、1、2个孩子，而且孩子有左右之分，即使仅有一个孩子，也必须区分左右。位于左边的孩子（或子树）叫左孩子(左子树)，位于右边的孩子（或子树）叫右孩子（右子树）

二、二叉树的性质

在二叉树的第i层上至多有2^(i-1)个结点(i≥1)。
深度为k的二叉树至多有2^k -1个结点(k≥1).
对任意一颗二叉树T,若终端结点数为n0,度为2的结点数为n2,则n0=n2+1.
具有n个结点的完全二叉树的深度为⌊logn⌋+1.
对于具有n个结点的完全二叉树，如果按照对满二叉树结点进行连续编号的方式，对所有结点从1开始顺序编号，则对任意序号为i的结点有： 1.如果i=1,则结点i为根，其无双亲结点；如果i>1，则结点i的双亲结点序号为⌊i/2⌋. 2.如果2i ≤n,否则，结点I无左孩子。 3.如果2i+1≤n,则结点i的右孩子结点序号为2I+1,否则，结点i无右孩子。

三、二叉树的存储

二叉树的存储结构主要有三种:顺序存储结构、链式存储结构和仿真指针存储结构。这里主要介绍链式存储结构。二叉树的链式存储结构就是用指针建立二叉树中结点之间的关系。二叉树最常用的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个指针域，分别是：数据域data、左孩子指针域letfchild和右孩子指针域rightChild.

四、二叉树的操作实现所有操作都针对下面这个二叉树

头文件:BiTree.h

#pragma once
#include<malloc.h>
typedef struct Node {
	DataType data;//数据域
	struct Node *leftchild;//左子树指针
	struct Node *rightchild;//右子树指针
}BiTreeNode;
//初始化
void Initiate(BiTreeNode **root) {
	*root = (BiTreeNode *)malloc(sizeof(BiTreeNode));
	(*root)->leftchild = NULL;
	(*root)->rightchild = NULL;
}
//做插入结点
//若当前结点curr非空，则在curr的左子树插入元素值为x的新节点
//原curr所指结点的左子树成为新插入结点的左子树
//若插入成功，则返回新插入结点的指针，否则返回空指针
BiTreeNode* InsertLeftNode(BiTreeNode *curr, DataType x) {
	BiTreeNode *s, *t;
	if (curr == NULL) {
		return NULL;
	}
	else {
		t = curr->leftchild;//保存原来curr所指结点的左子树指针
		s = (BiTreeNode*)malloc(sizeof(BiTreeNode));
		s->data = x;
		s->leftchild = t;//新插入结点的左子树成为为原来curr所指结点的左子树
		s->rightchild = NULL;
		curr->leftchild = s;//新结点成为curr的左子树
		return curr->leftchild;//返回新插入结点的指针
	}
}
//右插入结点
//若当前结点curr为空，则在curr的右子树插入元素值为x的新结点
//原curr所指结点的右子树成为新插入结点的右子树
//若插入成功，则返回新插入结点的指针，否则放回空指针
BiTreeNode *InsertRightNode(BiTreeNode *curr, DataType x) {
	BiTreeNode *s, *t;
	if (curr == NULL) {
		return NULL;
	}
	else {
		t = curr->rightchild;//保存原curr所指结点的右子树指针
		s = (BiTreeNode *)malloc(sizeof(BiTreeNode));
		s->data = x;
		s->rightchild = t;//新插入结点的右子树为原curr的右子树
		s->leftchild = NULL;
		curr->rightchild = s;//新结点成为curr的右子树
		return curr->rightchild;//返回新插入结点的指针
	}
}
//撤销二叉树操作设计
void Destroy(BiTreeNode **root) {
	if ((*root) != NULL && (*root)->leftchild != NULL) {
		Destroy(&(*root)->leftchild);
	}
	if ((*root) != NULL && (*root)->rightchild != NULL) {
		Destroy(&(*root)->rightchild);
	}
	free(*root);
}
//左删除子树
//若左子树非空，则删除curr所指结点的左子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteLeftTree(BiTreeNode *curr) {
	if (curr == NULL || curr->leftchild == NULL) {
		return  NULL;
	}
	else {
		Destroy(&curr->leftchild);
		curr->leftchild = NULL;
		return curr;
	}
}
//右删除子树
//若curr非空，则删除curr所指结点的右子树
//若删除成功，则返回删除结点的双亲结点指针，否则返回空指针
BiTreeNode *DeleteRightTree(BiTreeNode *curr) {
	if (curr == NULL || curr->rightchild == NULL) {
		return NULL;
	}
	else {
		Destroy(&curr->rightchild);
		curr->rightchild = NULL;
		return curr;
	}
}
void Visit(DataType item) {
	printf("%c ", item);
}
//前序遍历二叉树，访问操作为Visit()函数
void PreOrder(BiTreeNode *root, void Visit(DataType item)) {
	if (root != NULL) {
		Visit(root->data);
		PreOrder(root->leftchild, Visit);
		PreOrder(root->rightchild,Visit);
	}
}
//中序遍历二叉树，访问操作为Visit()函数
void InOrder(BiTreeNode *root, void Visit(DataType item)) {
	if (root != NULL) {
		InOrder(root->leftchild, Visit);
		Visit(root->data);
		InOrder(root->rightchild, Visit);
	}
}
//后续遍历二叉树，访问操作为Visit()函数
void PostOrder(BiTreeNode *root, void Visit(DataType item)) {
	if (root != NULL) {
		PostOrder(root->leftchild, Visit);
		PostOrder(root->rightchild, Visit);
		Visit(root->data);
	}
}
//打印二叉树
void PrintBiTree(BiTreeNode *root, int n) {
	//逆时针旋转90度打印二叉树root,n为缩进层数，初始值为0
	int i;
	if (root == NULL) {//递归出口
		return;
	}
	PrintBiTree(root->rightchild, n + 1);//遍历打印右子树
	//访问根节点
	for (i = 0; i < n - 1; i++) {
		printf("  ");
	}
	if (n > 0) {
		printf("---");
		printf("%c\n", root->data);
	}
	PrintBiTree(root->leftchild, n + 1);//遍历打印左子树
}
//查找数据元素
BiTreeNode *Search(BiTreeNode *root, DataType x) {
	//查找数据元素x是否再二叉树root中
	//查找到则返回该结点指针，未找到则返回空指针
	BiTreeNode *find = NULL;        //初始标记为查找失败
	if (root != NULL) {
		if (root->data == x) {
			find = root;
		}
		else {
			find = Search(root->leftchild, x);//在左子树中查找
			if (find == NULL) {
				find = Search(root->rightchild, x);//在右子树中找
			}
		}
	}
	return find;//返回查找标记
}
//统计二叉树结点总数
int Count(BiTreeNode *T)
{
	if (T == NULL) {
		return 0;
	}
	else {
		return Count(T->leftchild) + Count(T->rightchild) + 1;
	}
}
//输出二叉树中的叶子结点
void InOrder(BiTreeNode *T)//实际上是root->leftchild,root是头节点
{
	if (T) {
		InOrder(T->leftchild);
		if (T->leftchild == NULL && T->rightchild == NULL) {
			printf("%c ",T->data);
		}
		InOrder(T->rightchild);
	}
}
//统计二叉树中的叶子节点数目
int Leaf(BiTreeNode *T)
{
	int nl, nr;
	if (T == NULL)
		return 0;
	if ((T->leftchild == NULL) && (T->rightchild == NULL)) {
		return 1;
	}
	nl = Leaf(T->leftchild);//递归求左子树的叶子树
	nr = Leaf(T->rightchild);//递归求右子树的叶子树
	return (nl + nr);
}
//统计二叉树中度为2的结点数目
int leaf_2(BiTreeNode *T) {
	if (T ==NULL){
		return 0;
	 }
	 if((T->leftchild != NULL) && (T->rightchild != NULL)) {
		 return (leaf_2(T->leftchild) + leaf_2(T->rightchild) + 1);
	 }
	 else{
		 return 0;
	 }
}
//交换二叉树中各个节点得左右子树
void swap( BiTreeNode *T) {
	BiTreeNode *temp;
	if (T == NULL) {
		return;
	}
	else {
		temp = T->leftchild;
		T->leftchild = T->rightchild;
		T->rightchild = temp;
		swap(T->leftchild);
		swap(T->rightchild);
	}
}

源文件：

#include<stdio.h>
#include<stdlib.h>
typedef char DataType;
#include"BiTree.h"
int main() {
	BiTreeNode *root, *p, *find;
	char x = 'E';
	Initiate(&root);
	p = InsertLeftNode(root, 'A');
	p = InsertLeftNode(p, 'B');
	p = InsertLeftNode(p, 'D');
	p = InsertRightNode(p, 'G');
	p = InsertRightNode(root->leftchild, 'C');
	InsertLeftNode(p, 'E');
	InsertRightNode(p, 'F');
	printf("打印二叉树:\n");
	PrintBiTree(root, 0);
	printf("前序遍历: ");
	PreOrder(root->leftchild, Visit);
	printf("\n中序遍历: ");
	InOrder(root->leftchild, Visit);
	printf("\n后序遍历: ");
	PostOrder(root->leftchild, Visit);
	find = Search(root, x);
	if (find != NULL) {
		printf("\n数据元素%c在二叉树中", x);
	}
	else {
		printf("\n数据元素%c不在二叉树中", x);
	}
	int count = Count(root->leftchild);
	printf("\n二叉树中的结点总数为%d\n", count);
	printf("二叉树的叶子结点为:");
	InOrder(root->leftchild);
	printf("\n");
	int leaf = Leaf(root->leftchild);
	printf("二叉树中的叶子节点数目为:%d\n", leaf);
	int leaf2 = leaf_2(root->leftchild);
	printf("二叉树中度为2的结点数目为:%d\n", leaf2);

	/*交换二叉树各结的左右子树*/
	swap(root->leftchild);
	printf("前序遍历: ");
	PreOrder(root->leftchild, Visit);
	Destroy(&root);
	printf("\n");
	return 0;
	system("pause");
}

运行结果: