欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【数据结构·考研】树的孩子兄弟表示法

程序员文章站 2024-03-08 20:01:22
...

树的孩子兄弟表示法

也叫树的二叉树表示法。

树的左指针指向自己的第一个孩子,右指针指向与自己相邻的兄弟。

结构的最大优点是:它和二叉树的二叉链表表示完全一样。可利用二叉树的算法来实现对树的操作 。

【数据结构·考研】树的孩子兄弟表示法

左孩子右兄弟表示的树的高度 

因为二叉树表示法的根节点没有右孩子,所以树高就是左子树树高 + 1。

然后我们看下根节点第一个孩子的高度,由于第一个孩子的右子树和第一个孩子的高度是相同的,所以比较左子树 + 1的高度来和右子树来比较,如果 左子树 + 1 > 右子树,高度取左子树 + 1,否则取右子树。

//左孩子右兄弟表示的树的高度 
int Height(Tree& t){
	if(t == NULL) return 0;
	return Height(t->left) + 1 > Height(t->right) ? Height(t->left) + 1 : Height(t->right);
} 

左孩子右兄弟表示的树的叶子结点数

与求二叉树叶子结点的算法相似,仅需要把判断条件修改。

//左孩子右兄弟表示的树的叶子结点数 
int Count(Tree& t){
	if(t == NULL) return 0;
	if(t->left == NULL) return 1;
	return Count(t->left) + Count(t->right); 
}

树的总结点数

与求二叉树叶子结点的算法完全相同。

//总的结点数 
int CountSum(Tree& t){
	if(t == NULL) return 0;
	return CountSum(t->left) + CountSum(t->right) + 1;
}

树的先根遍历 

树的先根遍历,孩子是根,兄弟不是,多么精辟的话。先一边输出一边递归找孩子,等递归返回时再输出兄弟。

树的先根遍历的结果和二叉树的前序遍历的结果完全相同。

//树的先根遍历 
void preOrder(Tree& t){
	if(t == NULL) return;
	cout<<t->val<<" ";
	TreeNode* p = t->left;
	while(p != NULL){
		preOrder(p); //递归找“根” 
		p = p->right;
	}	
} 

树的后根遍历

在递归的边界处输出,先一直往下找“根”,找到最后走到孩子到了边界了,打印孩子之后再开始挖我的兄弟。

树的后根遍历的结果和二叉树的中序遍历的结果完全相同。

//树的后根遍历
void PostOrder(Tree& t){
	if(t == NULL) return;
	TreeNode* p = t->left;
	while(p != NULL){
		PostOrder(p); //递归找“根”
		p = p->right;
	}
	cout<<t->val<<" ";
} 

左孩子右兄弟表示的树的层次遍历

每找到一个孩子时,迭代的把它的兄弟全部找出来,对每个结点都这样处理。

最后的结果按行来打印。

//左孩子右兄弟表示的树的层次遍历 
void levelOrder(Tree& t){
	if(t == NULL) return;
	queue<TreeNode*> q;
	TreeNode* p;
	q.push(t);
	while(!q.empty()){
		int width = q.size();
		for(int i = 0;i < width;i ++){
			p = q.front();
			q.pop();
			cout<<p->val<<" ";
			p = p->left;
			while(p != NULL){
				q.push(p);
				p = p->right;
			}
		}
		cout<<endl;
	}
}

左孩子右兄弟表示的树的宽度

与二叉树非递归找宽度的原理完全相同,既然可以按层打印,就可以比较记录最大的宽度。

//左孩子右兄弟表示的树的宽度 
int Width(Tree& t){
	if(t == NULL) return 0;
	queue<TreeNode*> q;
	TreeNode* p;
	int max = 0;
	q.push(t);
	while(!q.empty()){
		int width = q.size();
		for(int i = 0;i < width;i ++){
			p = q.front();
			q.pop();
			p = p->left;
			while(p != NULL){
				q.push(p);
				p = p->right;
			}
		}
		max = max < width ? width : max; 
	}
	return max;
}

在以t为根的树中找结点p的双亲

循长子的兄弟链,递归在子树中搜索。

//在以t为根的树中找结点p的双亲
TreeNode* findParent(Tree& t,TreeNode* p){
	if(t == NULL || p ==NULL) return NULL;
	TreeNode* q = t->left;
	TreeNode* s;
	//循长子的兄弟链,递归在子树中搜索 
	while(q != NULL && q != p){
		if(s = findParent(p,q) != NULL) return s; //找到双亲,返回 
		q = q->right;
	}
	if(q != NULL && q == p) return t; //找到双亲 
	else return NULL; //未找到 
} 

树采用先序构造,大家可以自己画一下。

完整代码如下:

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

//结点定义 
typedef struct node{
	char val;
	struct node* left; //左孩子 
	struct node* right; //右兄弟 
}TreeNode,*Tree;

//左孩子右兄弟表示的树的高度 
int Height(Tree& t){
	if(t == NULL) return 0;
	return Height(t->left) + 1 > Height(t->right) ? Height(t->left) + 1 : Height(t->right);
} 

//左孩子右兄弟表示的树的叶子结点数 
int Count(Tree& t){
	if(t == NULL) return 0;
	if(t->left == NULL) return 1;
	return Count(t->left) + Count(t->right); 
}

//总的结点数 
int CountSum(Tree& t){
	if(t == NULL) return 0;
	return CountSum(t->left) + CountSum(t->right) + 1;
}

//树的先根遍历 
void preOrder(Tree& t){
	if(t == NULL) return;
	cout<<t->val<<" ";
	TreeNode* p = t->left;
	while(p != NULL){
		preOrder(p); //递归找“根” 
		p = p->right;
	}	
} 

//树的后根遍历
void PostOrder(Tree& t){
	if(t == NULL) return;
	TreeNode* p = t->left;
	while(p != NULL){
		PostOrder(p); //递归找“根”
		p = p->right;
	}
	cout<<t->val<<" ";
} 

//二叉树的层次遍历 
void levelOrderTraverse(Tree& t){
	if(t == NULL) return;
	queue<TreeNode*> q;
	TreeNode* p;
	q.push(t);
	while(!q.empty()){
		int width = q.size();
		for(int i = 0;i < width;i ++){
			p = q.front();
			q.pop();
			cout<<p->val<<" ";
			if(p->left) q.push(p->left);
			if(p->right) q.push(p->right);
		}
		cout<<endl;
	}
}

//左孩子右兄弟表示的树的层次遍历 
void levelOrder(Tree& t){
	if(t == NULL) return;
	queue<TreeNode*> q;
	TreeNode* p;
	q.push(t);
	while(!q.empty()){
		int width = q.size();
		for(int i = 0;i < width;i ++){
			p = q.front();
			q.pop();
			cout<<p->val<<" ";
			p = p->left;
			while(p != NULL){
				q.push(p);
				p = p->right;
			}
		}
		cout<<endl;
	}
}

//左孩子右兄弟表示的树的宽度 
int Width(Tree& t){
	if(t == NULL) return 0;
	queue<TreeNode*> q;
	TreeNode* p;
	int max = 0;
	q.push(t);
	while(!q.empty()){
		int width = q.size();
		for(int i = 0;i < width;i ++){
			p = q.front();
			q.pop();
			p = p->left;
			while(p != NULL){
				q.push(p);
				p = p->right;
			}
		}
		max = max < width ? width : max; 
	}
	return max;
}

//先序遍历构造树 
void CreateTree(Tree& t){
	char x;
	cin>>x;
	if(x == '#') t = NULL; 
	else{
		t = new TreeNode; 
		t->val = x;  
		CreateTree(t->left); 
		CreateTree(t->right); 
	}
} 

//在以t为根的树中找结点p的双亲
TreeNode* findParent(Tree& t,TreeNode* p){
	if(t == NULL || p ==NULL) return NULL;
	TreeNode* q = t->left;
	TreeNode* s;
	//循长子的兄弟链,递归在子树中搜索 
	while(q != NULL && q != p){ 
		if((s = findParent(p,q)) != NULL) return s; //找到双亲,返回 
		q = q->right;
	}
	if(q != NULL && q == p) return t; //找到双亲 
	else return NULL; //未找到 
} 

int main(){
	Tree t;
	CreateTree(t);
	/*
	   a b d # # e # # #
	*/
	cout<<"用二叉树表示的树层次遍历:"<<endl;
	levelOrderTraverse(t);
	cout<<endl; 
	cout<<"左孩子右兄弟表示的树的层次遍历:"<<endl;
	levelOrder(t);
	cout<<endl; 
	cout<<"左孩子右兄弟表示的树的宽度:"<<endl;
	cout<<Width(t)<<endl; 
	cout<<"左孩子右兄弟表示的树的高度 :"<<endl;
	cout<<Height(t)<<endl; 
	cout<<"左孩子右兄弟表示的树的叶子结点数:"<<endl;
	cout<<Count(t)<<endl;
	cout<<"树的总结点数:"<<endl;
	cout<<CountSum(t)<<endl;
	cout<<"树的先根遍历:"<<endl;
	preOrder(t);
	cout<<endl; 
	cout<<"树的后根遍历:"<<endl;
	PostOrder(t);
	cout<<endl; 
}

运行结果:

【数据结构·考研】树的孩子兄弟表示法