数据结构与算法-树

🎈1.树和二叉树

树结构是一类重要的非线性结构，树型结构是结点之间有分支，并且具有明显的层次关系的结构，它类似于自然界中的树。树结构在客观世界是大量存在的，例如行政组织机构和人类社会的家谱都可以用树来形象表示。

🎈2.树

🔭2.1树的定义

树是n(n>=0)个结点的有限集T。
若n=0，称为空树。
若n>0，则它满足以下两个条件：
（1）.有且仅有一个特定的称为根的结点。
（2）.其余结点可以分为m（m>=0）个互不相交的有限集T1,T2,T3......Tm,其中，每个集合本身又是一棵树，并称为根的子树。

🔭2.2树的4种表示方法

🔭2.3树的基本术语

---

• 结点：树中每个元素对应一个结点。每个结点包含一个数据元素及若干指向子树的分支。例如，图中的树有11个结点，结点D包含3个分支。
• 结点的度：结点所拥有的子树的个数称为结点的度。例如，结点A和D的度均为3，结点B的度为2，结点C的度为1，结点F的度为0。
• 叶子结点：度为0的结点称为叶子结点（或称树叶），又称终端结点。例如，上图所示，E,F,G,H,I,K都是叶子结点。
• 分支结点：度不为0的结点称为分支结点，又称非终端结点。例如，上图所示的树，A,B,C,D,J都是分支结点。
• 树的度：树中所有结点的最大度数称为树的度。例如，图所示的树的度为3.
• 双亲结点：若结点X有孩子，则X为孩子的双亲结点，简称双亲。例如，在图所示的树中，结点H,I,J的双亲是D,根结点A没有双亲，树中只有根结点没有双亲。
• 孩子结点：若结点X由子树，则子树的根结点即为结点X的孩子结点，简称孩子。例如，结点D有三个孩子H,I,J。
• 兄弟结点：同一双亲的孩子结点称为兄弟结点，简称兄弟。例如，结点H,I,J为兄弟。
• 堂兄弟结点：在树中的层次相同，但双亲不同的结点称为堂兄弟，简称堂兄。例如，结点F,G,H为堂兄弟。
• 祖先结点：从根结点到结点X所经过分支上的所有结点，都称为X的祖先结点，简称祖先。例如，K的祖先为A,D,J
• 子孙结点：结点X的孩子，以及这些孩子的孩子都是X的子孙结点。例如，结点D的子孙为H,I,J,K
• 结点的层次：根结点的层次为1，根结点的孩子的层次为2，根结点的孩子的孩子的层次为3，依次类推。
• 树的深度：树中结点的最大层次称为树的深度，也称树高。空树的深度为0，只有一个根结点的树的深度为1，图所示的树的深度为4.
• 路径：从树的某个结点X到其子孙结点Y所经过的路线叫做路径，路径上经过的边的数称为路径长度。由于树中无回路，所以树的路径是唯一的。如图所示的树中，从A到结点K的路径是A,D,J,K,路径长度为3.
• 森林：m(m>=)棵互不相交的树构成的集合称之为森林。

🔭2.4树的抽象数据类型定义

ADT Tree{
数据对象D:D为性质相同的数据元素的集合
数据关系R:
若D为空集，则称为空树。
若D仅有一个数据元素，则R=空集，否则R！=空集。
（1）.在D中存在唯一的称为根的数据元素root,它在关系R下无前驱。
（2）.存在D-{root}的一个划分{D1,D2,...,Dm}（m>0）,且对于（1<=i<=m），存在唯一的数据元素Xi属于Di,有(root,Xi)属于R.
（3）.对应于D-{root}的一个划分，r-{(root,x1),(root,x2),...,(root,Xm)}存在唯一的一个划分{R1,R2,...,Rm}(m>0),对于（1<=i<=m）,Ri是Di上的二元关系，（xi,Ri）（i=1,2,...,m）是一棵符合本定义的树，称为根root的子树。

---

基本操作：
InitTree(&t):构造一棵空树
DestroyTree(&t):销毁一棵树
Parent(t,e):求结点e的双亲结点
Sons(t,e):求结点e有所有孩子结点
LeftChild(t,e):返回结点e的右兄弟最左孩子
RightSibling(t,e):返回结点e的右兄弟结点
TraraverseTree(t,visit()):以visit()函数访问树中每个结点
DepthTree(t):返回树的深度
}ADT Tree

🎈3.二叉树

🔭3.1二叉树的定义

二叉树是由n(n>=0)个结点构成的有限集合，该集合或者为空集，此时称为空二叉树，或由一个根结点及两棵互不相交的左右子树组成，并且左右子树均是二叉树。二叉树的子树有左右之分，其次序不能颠倒。

二叉树的定义也是一个递归定义，二叉树可以是空集合，根可以有空的左子树或空的右子树。。二叉树不是树的特殊情况，它们是两个概念。二叉树中即使只有一棵子树也要进行区分，说明它是左子树，还是右子树，这是二叉树与树的最主要的差别。“二叉树是结点度为2的树”的说法是错误的。二叉树的5种基本形态：

🔭3.2二叉树的抽象数据类型定义

🔭3.3满二叉树

一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层上结点数都是最大结点数。如图所示，是一棵深度为4的满二叉树。

🔭3.4完全二叉树

可以对满二叉树的结点进行顺序编号，约定编号从根结点开始，自上而下，从左至右（称为层序编号）。
如果一棵深度为k且具有n个结点的二叉树，它的每个结点都与深度为k的满二叉树中的顺序编号1~n的结点一一对应，则称这棵二叉树为完全二叉树。

🔭3.5完全二叉树的特点

1. 叶子结点只能在第k层和第k-1层上出现。
2. 对于任意结点，若其右子树的深度为l,则其左子树的深度为l或l+1。
3. 度为1的结点数为0或1。当结点的总数为奇数时，度为1的结点数为0，当结点的总数为偶数时，度为1的结点数为1.

🔭3.6二叉树的性质

1. 二叉树的第i层上至多有2^i-1（i>=1）个结点。
2. 深度为k的二叉树最多有2^k-1（k>=1）个结点。
3. 对于任何一棵二叉树，如果其叶子结点数为n0,度为2的结点数为n2，则n0=n2+1.
   性质3推论：对于任何一棵k叉树，如果叶子结点数为n0，度为1,2，...k的结点数分别为n1,n2,...,nk,则n0=n2+2n3+3n4+...(k-1)nk+1.

---

例：一棵三叉树中，已知度为3的结点数等于度为2的结点数，且叶子结点数为10，则度为3的结点为多少？
n0 = n2+2n3+1=3n3+1
n3 = 3

---

4. 一棵具有n个结点的完全二叉树的深度为[log2n]+1(以2为底，n的对数)。
5. 

🔭3.7二叉树的存储结构

二叉树的顺序存储结构是用一组地址连续的存储单元来存放二叉树的数据元素。

📝二叉树的顺序存储结构类型定义如下：

#define MaxSize 100  //二叉树的最大存储容量
typedef ElemType SqBiTree[MaxSize]  //用数组存储二叉树的数据元素
SqBiTree bt;

🔭3.8完全二叉树的顺序存储

在用数组存储二叉树时，必须确定树中各数据元素的存放次序，使各数据元素的相应位置反映出数据元素之间的逻辑关系用一组地址连续的存储单元依次自上而下、自左而右地存储完全二叉树的结点元素。

🔭3.9一般二叉树的存储结构

在采用顺序存储时，应采用完全二叉树的编号方式，没有编号的结点在对应的位置上用#表示。

注：对于完全二叉树而言，采用顺序存储结构方式是十分合理的，它能够充分利用存储空间，但对于一般的二叉树而言，这种存储方式必然会造成大量空间浪费。在最坏的情况下，一棵深度为k且只有k个单分支二叉树，却需要长度为2^k-1的一维数组来存储。因此，一般二叉树常采用链式存储方式。

🔭3.10二叉树的链式存储结构

根据二叉树的定义，二叉树的每个结点可以有两个分支，分别指向及诶单的左子树和右子树。在二叉树中，标准存储方式的结点结构如图所示：

其中，data表示数据域，用来存放数据元素信息。
lchild表示左指针域，用来存放指向左孩子的指针，当左孩子不存在时为空指针。
rchild表示右指针域，用来存放指向右孩子的指针，当右孩子不存在时为空指针。
这种链式存储结构通常称为二叉链表。

二叉链表的结点类型定义:
typedef struct BitNode
{ElemType data;//数据元素信息BitNode *lchild;//指向左孩子结点BitNode *rchild;//指向右孩子结点
}BitNode;

由二叉树的链式存储结构可知，对于具有n个结点的二叉树，每个结点有两个指针域，共有2n个指针域，其中n-1个非空链域，n+1个空链域。

🎈4.二叉树的类定义及其实现

🔭4.1二叉树的类定义

#include <iostream>
using namespace std;
typedef struct BitNode
{char data;BitNode* lchild;BitNode* rchild;
}BitNode;
class BiTree
{
private:BitNode* bt;void Rcreate(BitNode*& t);//递归创建二叉树void PreTraverse(BitNode* t);//先序遍历递归函数void InTraverse(BitNode* t);//中序遍历递归函数void PostTraverse(BitNode* t);//后序遍历递归函数int BTNodeDepth(BitNode* t);//计算二叉树的树高递归函数int BTNodeLeaf(BitNode* t);//计算二叉树树叶数递归函数BitNode* SearchNode(BitNode* t, char x);//查找值等于x的结点递归函数
public:BiTree(){bt = NULL;//创建空树}void RcreateBiTree();//创建二叉树void PreTraverseBiTree();//先序遍历二叉树void InTraverse();//中序遍历二叉树void PostTraverse();//后序遍历二叉树int BTNodeDepthBiTree();//计算二叉树的树高int BTNodeLeafBiTree();//计算二叉树的叶子数BitNode* SearchNodeBit(char x);//查找值等于x的结点
};

🔭4.2二叉树的实现

📖4.2.1创建二叉树

Rcreate()函数递归创建二叉树，其过程为：读入字符ch，若ch=='.',则创建空二叉树，若ch!='.'，则先创建左子树，再创建右子树。

void BiTree::Rcreate(BitNode*& t)
{char ch;cin >> ch;if (ch == '.')t = NULL;else{t = new BitNode;//申请空间t->data = ch;Rcreate(t->lchild);//递归创建左子树Rcreate(t->rchild);//递归创建右子树}
}
void BiTree::RcreateBiTree()
{BitNode* t;Rcreate(t);//递归创建二叉树bt = t;//将根结点指针赋值给私有成员bt
}

📖4.2.2计算二叉树的高度

BTNodeDepth()函数递归计算二叉树的树高，其过程为：判断二叉树t是否为空树，若为空树，树高则为0。若为非空树，则计算左子树的高度m和右子树的高度n;m>=n,返回m，否则返回n.

int BiTree::BTNodeDepth(BitNode* t)
{if (t == NULL)return 0;else{int m = 1 + BTNodeDepth(t->lchild);//计算左子树树高度int n = 1 + BTNodeDepth(t->rchild);//计算右子树树高度if (m >= n)//比较左右子树高度return m;elsereturn n;}
}
int BiTree::BTNodeDepthBiTree()
{//计算二叉树的高度BitNode* p = bt;return BTNodeDepth(p);//调用计算二叉树高度的递归函数
}

📖4.2.3计算二叉树的树叶数

BTNodeLeaf()计算二叉树的树叶数，其过程为：判断t是否为空树，若为空树，则树叶数为0；若为非空树，则计算左子树的树叶数m和右子树的树叶数n，m+n=0时返回1，m+n!=0时返回m+n.

int BiTree::BTNodeLeaf(BitNode* t)
{//递归算法计算二叉树的树叶数if (t == NULL)return 0;else{int m = BTNodeLeaf(t->lchild);//计算左子树的树叶数int n = BTNodeLeaf(t->rchild);//计算右子树的树叶数if (m + n == 0)return 1;elsereturn m + n;}
}
int BiTree::BTNodeLeafBiTree()
{//计算二叉树的树叶数BitNode* p = bt;//读取私有成员指针btreturn BTNodeLeaf(p);//调用二叉树的树叶数的递归函数
}

📖4.2.4查找二叉树

SearchNode()函数在二叉树t中查找值等于x的结点，若找到该结点时返回其首地址，否则返回NULL.判断t是否为空树，若为空树，则返回NULL，若为非空树，则在t->data==x时返回t,在t->data!=x时，在左子树中查找，否则在右子树中查找。

BitNode* BiTree::SearchNode(BitNode* t, char x)
{BitNode* p;if (t == NULL)return NULL;if (t->data == x)return t;else{p = SearchNode(t->lchild,x);//递归查找左子树if (p != NULL)return p;elsereturn SearchNode(t->rchild, x);//递归查找右子树}
}
BitNode* BiTree::SearchNodeBit(char x)
{BitNode* p = bt;return SearchNode(p, x);
}

好啦，关于二叉树的知识到这里并没有结束，后期会继续更新二叉树的相关知识，欢迎大家持续关注、点赞和评论！❤️❤️❤️