XShell 高阶函数 OpenCV4 微服务 哨兵模式 EasyCVR charts 网络营销推广 model cron pyqt cuda jvm nginx视频教程 excel太长的文字隐藏 java解析json数组 字符串中包含某个字符串 solidworks图库 json转object linux查看jdk安装路径 linux撤销 excel加减混合求和 kubernetes官网 mysqlinsert python中time python抛异常 random函数用法 python服务器开发 java编译 java中的string java中的继承 java安装 修改tomcat端口 ps怎么插入表格 pr缩放 彩虹岛小草黑暗之矛 修改ip地址软件 火萤壁纸下载 c4d挤压怎么用 js字符串比较
当前位置: 首页 > 学习教程  > 编程语言

树数据结构

2021/1/28 23:56:16 文章标签:

树的数据结构定义树的数据结构树的基本知识二叉树基本概念二叉树存储结构性质二叉树的遍历二叉搜索树性质二叉搜索树的方法平衡二叉树完整代码参考树的数据结构 typedef struct BinaryTreeNode {int data;struct BinaryTreeNode* left;struct BinaryTreeNode* right; }Node; N…

树的数据结构定义

    • 树的数据结构
    • 树的基本知识
    • 二叉树基本概念
    • 二叉树存储结构性质
    • 二叉树的遍历
    • 二叉搜索树性质
    • 二叉搜索树的方法
    • 平衡二叉树
    • 完整代码
    • 参考

树的数据结构

typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}Node;
Node* createBinaryTree()
{
	Node* p;
	int ch;
	cin >> ch;
	if (ch == 0)
	{
		p = NULL;
	}
	else
	{
		p = (Node*)malloc(sizeof(Node));
		p->data = ch;
		p->left = createBinaryTree();//先序创建树
		p->right = createBinaryTree();
	}
	return p;
}

void inOrderTraverse(Node* root)
{
	if (root)
	{
		inOrderTraverse(root->left);
		cout << root->data << ' ';
		inOrderTraverse(root->right);
	}
}

void preOrderTraverse(Node* root)
{
	if (root)
	{
		cout << root->data << ' ';
		preOrderTraverse(root->left);
		preOrderTraverse(root->right);
	}
}

void lastOrderTraverse(Node* root)
{
	if (root)
	{
		lastOrderTraverse(root->left);
		lastOrderTraverse(root->right);
		cout << root->data<<' ';
	}
}
int Nodenum(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return 1 + Nodenum(root->left) + Nodenum(root->right);
	}
}

int DepthofTree(Node* root)
{
	if (root)
	{
		return DepthofTree(root->left) > DepthofTree(root->right) ? DepthofTree(root->left) + 1 : DepthofTree(root->right) + 1;
	}
	if (root == NULL)
	{
		return 0;
	}
}

int Leafnum(Node* root)
{
	if (!root)
	{
		return 0;
	}
	else if ((root->left == NULL) && (root->right == NULL))
	{
		return 1;
	}
	else
	{
		return (Leafnum(root->left) + Leafnum(root->right));
	}
}
int main()
{
	Node* p;
	p = createBinaryTree();
	preOrderTraverse(p);
	//preOrderTraverse(p);
	//cout << endl;
	//inOrderTraverse(p);
	//cout << endl;
	//lastOrderTraverse(p);
	//cout << endl;
	//cout << Nodenum(p) << endl;
	//cout << DepthofTree(p)<<endl;
	//cout << Leafnum(p);
}

树的基本知识

森林:对于根节点Root,森林是根节点所有的子树。
结点的度:结点的度是其子树的个数。
树的度:树中所有结点中最大的度数。
兄弟结点:有同一个父节点的结点。
祖先结点:沿着根节点到某个结点路径上的点都是某个节点的祖先结点
子孙结点:某一结点的子树中的所有结点。
结点的层次:结点的层数,根节点为1层,往下一层加1
树的深度:结点中的最大层次
树的高度:从叶子结点从下往上计数,叶子结点高度为1
树的高度=树的深度

二叉树基本概念

二叉树定义:由根节点和其左右两棵子树Tl和TR构成
满二叉树:所有的分支结点都有左右子树,叶子结点都在同一层上。
完全二叉树:树中所有的结点号都和满二叉树的结点号相同。

性质:1.二叉树第i层的最大节点数为2^i-1
2.深度为k的二叉树最大的结点总数为(2^k)-1 k>=1
3.n0表示叶子结点个数,n1度为1的结点个数,n2表示度为2的结点个数,则有n0=n2+1

二叉树存储结构性质

在N个结点的完全二叉树中,对于下标为i的结点:
1.当i/2>=1时,i/2是它的父节点。当i/2=0时,该节点是树的根节点。
2.当2i<=N时,2i是它的左孩子。
3.当2i+1<=N时,2i+1是它的右孩子。
(以上性质i的起始下标是1)

二叉树的遍历

以此图为例
在这里插入图片描述
任何树的中序和先序遍历唯一(两种遍历确定一棵树)
先序遍历(中左右)
6 2 1 4 3 8
中序遍历(左中右)
1 2 3 4 6 8
后序遍历(左右中)
1 3 4 2 8 6

二叉搜索树性质

定义:
1.非空左子树的所有键值小于根节点键值
2.非空右子树的所有键值大于根节点键值
3.左右子树都是二叉搜索树
Ex:
在这里插入图片描述

二叉搜索树的方法

1.搜索:如果查找的值x比结点大则搜索结点的右子树,反之搜索左子树。如果相等则输出
2.搜索最小:根据二叉搜索树性质,最小值是树的最左叶子结点。迭代搜索深度最大、最靠左的叶子结点
3.搜索最大:根据二叉搜索树性质,最大值是树的最右叶子结点。迭代搜索深度最大、最靠右的叶子结点
4.删除
删除分3种情况:
4.1删除的结点是叶子结点:直接删除
4.2删除的结点有一个子结点:将删除结点的父节点指针指向删除结点的子结点
4.3删除的结点有两个子节点:有两种方法
法1:选择删除结点的左子树中最大结点替代删除结点
法2:选择删除结点的右子树中最小结点替代删除结点(以下采用法2)
法1示例:
在这里插入图片描述

//二叉查找指定数值
Node* Find(Node* tree, int x)
{
	while (tree)
	{
		if (x > tree->data)
		{
			tree = tree->right;
		}
		else if (x < tree->data)
		{
			tree = tree->left;
		}
		else
			break;
	}
	return tree;
}
//二叉查找最小
Node* FindMin(Node* tree)
{
	if (!tree)return NULL;
	else if (!tree->left) return tree;
	else return FindMin(tree->left);
}
//二叉查找最大
Node* FindMax(Node* tree)
{
	if (tree)
	{
		while (tree->right)
			tree = tree->right;
		return tree;
	}
}
//二叉树插入算法
Node* Insert(Node* tree, int x)
{
	if (!tree)
	{
		tree = (Node*)malloc(sizeof(struct BinaryTreeNode));
		tree->data = x;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (x < tree->data)
		{
			tree->left = Insert(tree->left, x);
		}
		else if (x > tree->data)
		{
			tree->right = Insert(tree->right, x);
		}
	}
	return tree;
}
//二叉树删除算法
Node* Delete(Node* tree, int x)
{
	Node* tmp;
	if (!tree)
	{
		printf_s("删除失败");
	}
	else
	{
		if (x < tree->data)
			tree->left = Delete(tree->left, x);
		else if (x > tree->data)
			tree->right = Delete(tree->right, x);
		else
		{
			if (tree->left && tree->right)
			{
				tmp = FindMin(tree->right);
				tree->data = tmp->data;
				tree->right = Delete(tree->right, tree->data);
			}
			else
			{
				tmp = tree;
				if (!tree->left)
				{
					tree = tree->right;
				}
				else
					tree = tree->left;
				free(tmp);
			}
		}
	}
	return tree;
}

平衡二叉树

定义:1.任意结点的左右子树均为AVL树
2.根据点左右子树高度差的绝对值不超过1
平衡因子:任意结点的平衡因子BF(T)=hL-hR,hL,hR分别代表结点T的左右子树的高度。

平衡二叉树的调整
1.单旋转
1.1当结点A在右子树结点B插入右结点C时,A的高度为-2,不在{-1,0,1}之间。此时三个结点右斜,需要通过右单旋调整。
在这里插入图片描述

1.2当结点A在子树结点B插入左结点C时,A的高度为2,不在{-1,0,1}之间。此时三个结点右斜,需要通过左单旋调整。
在这里插入图片描述

2双旋转
当结点A在右子树结点B插入左结点C时,A的高度为-2,不在{-1,0,1}之间。此时三个结点右斜,需要通过右-左双旋调整。
在这里插入图片描述

当结点A在左子树结点B插入右结点C时,A的高度为2,不在{-1,0,1}之间。此时三个结点右斜,需要通过左-右双旋调整。
在这里插入图片描述

完整代码

#include<stdio.h>
#include<iostream>
using namespace std;

typedef struct BinaryTreeNode
{
	int data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}Node;

//二叉查找指定数值
Node* Find(Node* tree, int x)
{
	while (tree)
	{
		if (x > tree->data)
		{
			tree = tree->right;
		}
		else if (x < tree->data)
		{
			tree = tree->left;
		}
		else
			break;
	}
	return tree;
}
//二叉查找最小
Node* FindMin(Node* tree)
{
	if (!tree)return NULL;
	else if (!tree->left) return tree;
	else return FindMin(tree->left);
}
//二叉查找最大
Node* FindMax(Node* tree)
{
	if (tree)
	{
		while (tree->right)
			tree = tree->right;
		return tree;
	}
}
//二叉树插入算法
Node* Insert(Node* tree, int x)
{
	if (!tree)
	{
		tree = (Node*)malloc(sizeof(struct BinaryTreeNode));
		tree->data = x;
		tree->left = tree->right = NULL;
	}
	else
	{
		if (x < tree->data)
		{
			tree->left = Insert(tree->left, x);
		}
		else if (x > tree->data)
		{
			tree->right = Insert(tree->right, x);
		}
	}
	return tree;
}
//二叉树删除算法
Node* Delete(Node* tree, int x)
{
	Node* tmp;
	if (!tree)
	{
		printf_s("删除失败");
	}
	else
	{
		if (x < tree->data)
			tree->left = Delete(tree->left, x);
		else if (x > tree->data)
			tree->right = Delete(tree->right, x);
		else
		{
			if (tree->left && tree->right)
			{
				tmp = FindMin(tree->right);
				tree->data = tmp->data;
				tree->right = Delete(tree->right, tree->data);
			}
			else
			{
				tmp = tree;
				if (!tree->left)
				{
					tree = tree->right;
				}
				else
					tree = tree->left;
				free(tmp);
			}
		}
	}
	return tree;
}



Node* createBinaryTree()
{
	Node* p;
	int ch;
	cin >> ch;
	if (ch == 0)
	{
		p = NULL;
	}
	else
	{
		p = (Node*)malloc(sizeof(Node));
		p->data = ch;
		p->left = createBinaryTree();//先序创建树
		p->right = createBinaryTree();
	}
	return p;
}

void inOrderTraverse(Node* root)
{
	if (root)
	{
		inOrderTraverse(root->left);
		cout << root->data << ' ';
		inOrderTraverse(root->right);
	}
}

void preOrderTraverse(Node* root)
{
	if (root)
	{
		cout << root->data << ' ';
		preOrderTraverse(root->left);
		preOrderTraverse(root->right);
	}
}

void lastOrderTraverse(Node* root)
{
	if (root)
	{
		lastOrderTraverse(root->left);
		lastOrderTraverse(root->right);
		cout << root->data<<' ';
	}
}
int Nodenum(Node* root)
{
	if (root == NULL)
	{
		return 0;
	}
	else
	{
		return 1 + Nodenum(root->left) + Nodenum(root->right);
	}
}

int DepthofTree(Node* root)
{
	if (root)
	{
		return DepthofTree(root->left) > DepthofTree(root->right) ? DepthofTree(root->left) + 1 : DepthofTree(root->right) + 1;
	}
	if (root == NULL)
	{
		return 0;
	}
}

int Leafnum(Node* root)
{
	if (!root)
	{
		return 0;
	}
	else if ((root->left == NULL) && (root->right == NULL))
	{
		return 1;
	}
	else
	{
		return (Leafnum(root->left) + Leafnum(root->right));
	}
}
int main()
{
	Node* p;
	p = createBinaryTree();
	preOrderTraverse(p);
	cout << endl;
	inOrderTraverse(p);
	cout << endl;
	lastOrderTraverse(p);
	//cout << endl;
	//cout << Nodenum(p) << endl;
	//cout << DepthofTree(p)<<endl;
	//cout << Leafnum(p);
}

参考

https://blog.csdn.net/floating_fight/article/details/103016279


本文链接: http://www.dtmao.cc/news_show_650333.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?