树

树：树(Tree)是 n(n >= 0) 个节点的有限集。
    n=0时称为空树，在任意一棵空树中：
         ①有且仅有一个特定的被称为根(Root)的节点；
         ②当n>=1时，其余节点可以分为m(m>0)个互不相交的有限集 
    即：树的节点分为：根节点和叶节点，根节点没有前驱结点，叶节点没有后继结点 
    
   PS: ①树的根节点是唯一的
          ②子树的个数没有限制，但是他们一定是互不相交的
          ③树的定义具有递归性，即“树中还有树 ”  
          ④对于只有一个节点的树，那个节点既是根节点又是叶节点 

节点

节点的度：节点拥有的子树个数称作节点的度
节点的分类:   ①叶节点(Leaf)：度为0的节点
                      ②非终端节点/分支节点：度不为0的节点
            
    PS：树的度是树内各节点的度的最大值


节点间的关系: 

             ①双亲关系：节点的子树的根称为该节点的孩子(Child)，即该节点为孩子的双亲(Parent) 
             ②兄弟关系：同一个双亲的孩子之间是兄弟关系(Sibling)
             ③祖先关系：从树根到该节点所经分支上的所有节点都是该节点的祖先(Ancestor) 


节点的层次(Level)：从根开始算起，根为第一层，根的孩子为第二层，以此类推
PS:  ①双亲在同一层的节点互为堂兄弟
        ②树中节点的最大层次被称为树的深度或高度(方向向下数为深度，方向向上数为高度)
        ③如果树中节点的各子树有序，不能互换，则该树为有序树，否则称为无序树 

注：森林(Forest)是m (m >= 0)棵互不相交的树的集合 

树的存储结构

 1.双亲表示法

                            表示方法：结构体数组 
                            数据域：存储节点的值
                            双亲指针：存储父节点在数组中的下标
        优点：存储高效、查找父节点迅速、适合静态树
        缺点：查找子节点低效、插入/删除复杂、不支持森林

双亲表示法代码（C++）：

#include <iostream>
using namespace std;

//父亲表示法(数组存树)
//初始化树节点结构 
struct Node{
	char data;//数据域
	int f_i;//父亲节点的下标 
}t[105]; 
int size;//树中节点的个数

//初始化树的根节点
void initTree(char x){
	t[0].data = x;
	t[0].f_i = -1;//根节点没有父亲
	size++; 
}

//寻找节点fx并返回其下标
int Find(char fx){
	//遍历整个树寻找
	for(int i=0;i<size;i++){
		//查找成功
		if(t[i].data == fx){
			return i;
		} 
	}
	return -2;//该树中不存在节点fx 
} 
//插入节点x到树中
void Insert(char x,char fx){
	t[size].data = x;//更新节点数据域 
	
	int fx_i = Find(fx);//查找父亲节点下标 
	t[size].f_i = fx_i;//更新节点x的父亲下标
	 
	size++;//树中节点个数+1 
} 

//输出树中节点
void Print(){
	for(int i=0;i<size;i++){
		cout<<t[i].data<<" ";
	}
	cout<<endl;
}

int main(){
	//建树 
	int n;//树中节点个数 
	char root;//根节点 
	cin>>n;
	cin>>root;
	
	initTree(root);
	char x,fx;
	for(int i = 1;i<=n-1;i++){
		cin>>x>>fx;
		Insert(x,fx); 
	}
	Print();
	cout<<endl;
	
	initTree(root);
	char x,fx;
	for(int i = 1;i<=n-1;i++){
		cin>>x>>fx;
		Insert(x,fx); 
	}
	Print();
	cout<<endl;
	
	//找x的父亲和孩子
	cin>>x;
	int x_i=Find(x);//查找该节点在树中的下标 
	
	//确保节点存在 
	if(x_i!=-2){
		//找父亲
		int fx_i = t[x_i].f_i;//节点x的父亲节点下标 
		//非根节点 
		if(fx_i!=-1){
			cout<<"该节点的父亲节点是："<<t[fx_i].data<<endl;
		}
		//根节点 
		else{
			cout<<"该节点是根节点，没有父亲节点";
		}
		
		
		//找孩子
		int cnt = 0;//记录节点x的度
		for(int i=0;i<size;i++){
			if(t[i].f_i==x_i){
				if(cnt==0){
					cout<<"该节点的孩子节点是：";
				}
				cout<<t[i].data<<" ";
				cnt++;
			}
		}
		if(cnt==0){
			cout<<"该节点是叶节点，没有孩子节点！"<<endl;
		}
	}
	else{
		cout<<"该节点不存在！"<<endl;
	}
	return 0;
}
/*
10
R
A R
B R
C R
D A
E A
F C
G F
H F
K F
R A B C D E F G H K

C
该节点的父亲节点是：R
该节点的孩子节点是：F
*/

 2.孩子表示法

                  结构体数组 + 链表（数组存节点数据及孩子链表表头，链表存孩子节点下标及该节点的下一个孩子节点的地址）


        优点：遍历子节点高效、支持动态插入/删除、适合多叉树
        缺点：查找父节点低效、内存开销较大、实现较为复杂

孩子表示法代码（C++）：

#include <iostream>
using namespace std;

//孩子表示法(数组+链表存树)
//初始化孩子节点结构 
struct CHNode{
	int ch_i;//孩子节点下标
	struct CHNode* next;//该节点的下一个孩子节点 
};
//初始化树节点结构
struct Node{
	char data;//数据域
	CHNode* first;//指针域，指向第一个孩子 
}t[105]; 
int size;//树中节点的个数

//初始化树的根节点
void initTree(char root){
	t[0].data=root;//更新根节点数据域
	t[0].first=nullptr;//清空根节点指针域
	size++;//树中节点个数+1 
}

//寻找节点fx并返回其下标
int Find(char fx){
	//遍历整个树寻找
	for(int i=0;i<size;i++){
		//查找成功
		if(t[i].data == fx){
			return i;
		} 
	}
	return -2;//该树中不存在节点fx 
}
//插入节点x到树中
void Insert(char x,char fx){
	int fx_i=Find(fx);
	if(fx_i==-2){
		cout<<"节点"<<fx<<"不存在，插入失败！"<<endl;
		return;
	} 
	
	t[size].data=x;//更新节点数据域 
	t[size].first=nullptr;//节点指针域置空
	
	//将节点x存入fx的孩子链表中 
	CHNode* node = new CHNode();
	node->ch_i=size;
	//新孩子节点以头插方式加入孩子链表 
	node->next=t[fx_i].first;
	t[fx_i].first=node;
	
	size++;//节点个数+1
}

//找父亲
void Find_fa(int x_i){
	CHNode* p=nullptr;//指针p遍历孩子链表 
	bool flag = false;//表示是否找到父亲节点 
	
	//遍历每个节点的孩子链表寻找孩子下标与 x_i一致的下标
	for(int i=0;i<size;i++){
		p=t[i].first;
		while(p!=nullptr && p->ch_i!=x_i){
			p=p->next;
		}
		if(p!=nullptr && p->ch_i==x_i){
			flag=true;//表示节点x的父亲节点已经找到 
			cout<<"节点"<<t[x_i].data<<"的父亲节点是："<<t[i].data<<endl;
			break; 
		}
	}
	if(!flag){
		cout<<"节点"<<t[x_i].data<<"为根节点，没有父亲节点！"<<endl;
	}
} 

//找孩子
void Find_ch(int x_i){
	CHNode* p=t[x_i].first;//指针p指向结点x的孩子链表
	int ch_i;//孩子节点下标
	
	if(p==nullptr){
		cout<<"节点"<<t[x_i].data<<"没有孩子节点！"<<endl;
		return;
	}
	
	//遍历节点x的孩子链表
	cout<<"节点"<<t[x_i].data<<"的孩子节点是：";
	while(p!=nullptr){
		ch_i=p->ch_i;
		cout<<t[ch_i].data<<" ";
		p=p->next; 
	} 
	cout<<endl;
}

//输出树中节点
void Print(){
	for(int i=0;i<size;i++){
		cout<<t[i].data<<" ";
	}
	cout<<endl;
}

int main(){
	//建树 
	int n;//树中节点个数 
	char root;//根节点 
	cin>>n;
	cin>>root;
	
	initTree(root);
	char x,fx;
	for(int i = 1;i<=n-1;i++){
		cin>>x>>fx;
		Insert(x,fx); 
	}
	Print();
	cout<<endl;
	
	//找x的父亲和孩子
	cin>>x;
	int x_i=Find(x);//查找该节点在树中的下标
	
	//确保节点存在
	if(x_i!=-2){
		//找父亲
		Find_fa(x_i);
		
		//找孩子
		Find_ch(x_i);
	}
	return 0;
}
/* 
10
R
A R
B R
C R
D A
E A
F C
G F
H F
K F
R A B C D E F G H K

C
节点C的父亲节点是：R
节点C的孩子节点是：F
*/

3.孩子兄弟表示法

                                表示方法：二叉链表 
                                数据域：存储节点的值
                                左指针：存孩子的引用
                                右指针：存兄弟的引用
        优点：内存高效、操作灵活、将任意多叉树转换为二叉树
        缺点：查找父节点低效（所以本文代码不实现该功能）

孩子兄弟表示法代码（C++）：

#include <iostream>
using namespace std;

//孩子兄弟表示法
//初始化树节点结构
struct TreeNode{
	char data;//数据域
	struct TreeNode* left;//左指针存孩子
	struct TreeNode* right;//右指针存兄弟 
};
using TNode = TreeNode;

//初始化树的根节点
TNode* initTree(char root){
	TNode* node = new TNode();
	
	node->data=root;//更新根节点指针域 
	node->left=node->right=nullptr;//初始状态下左右指针均为空
	
	return node; 
}

//寻找节点fx并返回其下标(DFS搜索)
TNode* Find(TNode* root,char fx){
	if(root==nullptr) return root;//空树，直接返回
	if(root->data==fx) return root;//找到节点fx，返回
	
	//搜索左子树
	if(root->left!=nullptr){
		TNode *ans=Find(root->left,fx);
		if(ans!=nullptr&&ans->data==fx)return ans;
	}
	
	//搜索右子树
	if(root->right!=nullptr){
		TNode* ans=Find(root->right,fx);
		if(ans!=nullptr&&ans->data==fx)return ans;
	}
	
	return nullptr;//节点fx不存在，返回空
}

//插入节点x到树中
void Insert(TNode* root,char x,char fx){
	TNode *f=Find(root,fx);
	if(f==nullptr){
		cout<<"节点"<<fx<<"不存在，插入失败！"<<endl;
		return; 
	}
	
	//插入节点x做fx的第一个孩子节点(头插)
	TNode* node = new TNode();
	
	node->data=x;//更新节点x数据域
	node->left=nullptr;//节点x左指针(孩子指针)置空
	node->right=f->left;//将父亲节点的孩子信息更新到节点x的兄弟中 
	f->left=node;//更新父亲节点f的左指针(孩子指针)
}

//输出树中节点(DFS前序遍历：根->左->右)
void Print(TNode* root){
	if(root==nullptr) return;//空树，直接返回
	
	//输出当前节点 
	cout<<root->data<<" ";
	
	//遍历孩子
	Print(root->left);
	
	//遍历兄弟
	Print(root->right); 
}

int main(){
	//建树 
	int n;//树中节点个数 
	char r;//根节点 
	cin>>n;
	cin>>r;
	
	TNode* root=initTree(r);
	char x,fx;
	for(int i = 1;i<=n-1;i++){
		cin>>x>>fx;
		Insert(root,x,fx); 
	}
	
	//输出 
	cout<<"前序遍历输出树中节点如下："<<endl;
	Print(root);
	cout<<endl;
	cout<<endl;
	
	//找x的孩子
	cin>>x;
	TNode *f=Find(root,x);//查找节点x 
	TNode *p=f->left;//指针p遍历查找节点x的孩子
	cout<<"节点"<<x<<"的孩子节点是：";
	while(p!=nullptr){
		cout<<p->data<<" ";
		p=p->right;
	} 
	cout<<endl;	
	
	return 0;
}
/* 
10
R
A R
B R
C R
D A
E A
F C
G F
H F
K F
前序遍历输出树中节点如下：
R C F K H G B A E D

F
节点F的孩子节点是：K H G
*/

# 数据结构 # c++
Logo
DAMO开发者矩阵

DAMO开发者矩阵，由阿里巴巴达摩院和中国互联网协会联合发起，致力于探讨最前沿的技术趋势与应用成果，搭建高质量的交流与分享平台，推动技术创新与产业应用链接，围绕“人工智能与新型计算”构建开放共享的开发者生态。

更多推荐

VLA 系统学习第 2 课：Behavior Cloning——机器人究竟怎么从示范中学动作？

从这一课开始，我们第一次真正进入。

avatar DAMO开发者矩阵

VLA 系统学习第 3 课：从一次机器人示范，到真正送进神经网络的 Batch

因为训练数据里已经有“输入”和“正确答案”。对 BC 来说，一个最基本训练样本就是：\[ (o_t,a_t) \]其中：模型根据 \(o_t\) 预测：\[ \hat a_t=\pi_\theta(o_t) \]再把预测值：\[ \hat a_t \]和专家答案：\[ a_t \]比较。所以本质就是：\[ \boxed{\text{输入}\rightarrow\text{正确答案}} \]和图像分

avatar DAMO开发者矩阵

机器人学习必备核心技术

学习机器人技术需要掌握一系列跨学科的知识和技能，涵盖机械设计、电子工程、计算机科学等多个领域。

avatar DAMO开发者矩阵