[C++知识库]【C++】树与二叉树

二叉树

• 二叉树：最多分两叉的有序树。

如上图所示。

常见操作

链表存储

存储结构

typedef struct node{
	int data;//数据 
	node *l,*r;//左右子树 
}node,*tree;

先序建树

node* build(){
	int k;
	cin>>k;//输入k 
	if(k==-1){//-1表示结点空 
		return NULL;
	}else{
		node *p=new node();//创建新节点 
		p->data=k;
		p->l=build();//递归创建左子树 
		p->r=build();//递归创建右子树 
		return p;//返回结点 
	}
}

tree root=new node();
root->l=build();
//输入1 2 -1 -1 3 -1 -1

• 经过上述语句调用后，树$root$结构如下图所示。

先序输出

void pre(node* p){
	if(!p) return;
	cout<<p->data<<' ';
	pre(p->l);
	pre(p->r);
}

中序输出

void in(node* p){
	if(!p) return;
	in(p->l);
	cout<<p->data<<' ';
	in(p->r);
}

后序输出

void last(node* p){
	if(!p) return;
	last(p->l);
	last(p->r);
	cout<<p->data<<' ';
}

层序输出

void level(node* p){
	queue<node*> q;//定义队列 
	if(p) q.push(p);//入队根节点 
	while(!q.empty()){
		cout<<q.front()->data<<' ';//输出队首结点 
		if(q.front()->l) q.push(q.front()->l);//入队队首结点左孩子结点 
		if(q.front()->r) q.push(q.front()->r);//入队队首结点右孩子结点 
		q.pop();//出队队首结点 
	}
}

静态链表

存储结构

int len=0;//已用结点数 
int tree[N+1];//i号结点的数据,下标从1开始
int child[N+1][2];//i号结点的左右子结点编号

先序建树

int build(int idx){//创建结点idx 
	int k;
	cin>>k;//输入k 
	if(k==-1){//-1表示结点空 
		len--;//回退一个结点 
		return 0;
	}else{
		tree[idx]=k;//创建新节点
		child[idx][0]=build(++len);
		child[idx][1]=build(++len);
		return idx;//返回结点 
	}
}

build(++len);
//输入1 2 -1 -1 3 -1 -1

• 经过上述语句调用后，树$root$结构如下图所示。

先序输出

void pre(int p){
	if(tree[p]==0) return;
	cout<<tree[p]<<' ';
	pre(child[p][0]);
	pre(child[p][1]);
}

中序输出

void in(int p){
	if(tree[p]==0) return;
	in(child[p][0]);
	cout<<tree[p]<<' ';
	in(child[p][1]);
}

后序输出

void last(int p){
	if(!p) return;
	last(child[p][0]);
	last(child[p][1]);
	cout<<tree[p]<<' ';
}

层序输出

void level(int p){
	queue<int> q;//定义队列 
	if(tree[p]) q.push(p);//入队根节点 
	while(!q.empty()){
		cout<<tree[q.front()]<<' ';
		if(child[q.front()][0]) q.push(child[q.front()][0]);//入队队首结点左孩子结点 
		if(child[q.front()][1]) q.push(child[q.front()][1]);//入队队首结点右孩子结点 
		q.pop();//出队队首结点 
	}
}

完全二叉树

• 若高度为$h$的二叉树的前$h?1$层为满二叉树且第$h$层左连续，则此树为一颗完全二叉树。如下图所示。

存储

• 完全二叉树可采用线性结构存储

• 当根结点编号为$1$时，$i$号结点的左孩子下标为$2i$，右孩子下表为$2i+1$，以$0$表示空结点

int tree[N+1]={0};//最大大小为N的完全二叉树

读取

void read(int n){
	for(int i=1;i<=n;i++){
		cin>>tree[i];//读入完全二叉树,由于0表示空结点,故不得输入0
	}
}

先序输出

void pre(int p){
	if(tree[p]!=0){
		cout<<tree[p]<<' ';
		pre(2*p);//递归左子树
		pre(2*p+1);//递归右子树
	}
}

单词树

• 用于统计单词数，$aa,abc,acd,bc$这几个字符串构建单词树如下图所示，每一条路径都是一个单词前缀。

存储结构

typedef struct node{
	char data;
	node* next[26];
}node,*tree;

建立单词树

void build(node* p,string s){//插入s到p树 
	if(!p){
		p=new node();
		setNextNull(p);
	}
	s[0]=tolower(s[0]);//转换第一个字符为小写方便计算
	if(p->next[s[0]-'a']==NULL){//记录第s[0]-'a'个数据为s[0] 
		p->next[s[0]-'a']=new node();
		setNextNull(p->next[s[0]-'0']);
		p->next[s[0]-'a']->data=s[0];
	}
	if(s.size()>1) build(p->next[s[0]-'a'],s.substr(1));//递归下一层 
}

先序输出

void pre(node *p){
	if(p){
		cout<<p->data<<' ';
		for(int i=0;i<26;i++){
			if(p->next[i]) pre(p->next[i]);
		}
	}
}

测试代码

#include <iostream>
using namespace std;
typedef struct node{
	char data;
	node* next[26];
}node,*tree;
void setNextNull(node *p){//初始化孩子节点为空
	if(p){
		for(int i=0;i<26;i++){
			p->next[i]=NULL; 
		}
	}
}
void build(node* p,string s){//插入s到p树 
	if(!p){
		p=new node();
		setNextNull(p);
	}
	s[0]=tolower(s[0]);//转换第一个字符为小写方便计算
	if(p->next[s[0]-'a']==NULL){//记录第s[0]-'a'个数据为s[0] 
		p->next[s[0]-'a']=new node();
		setNextNull(p->next[s[0]-'0']);
		p->next[s[0]-'a']->data=s[0];
	}
	if(s.size()>1) build(p->next[s[0]-'a'],s.substr(1));//递归下一层 
}
void pre(node *p){
	if(p){
		cout<<p->data<<' ';
		for(int i=0;i<26;i++){
			if(p->next[i]) pre(p->next[i]);
		}
	}
}
int main(){
	tree root=new node();
	setNextNull(root);
	int n;
	string s;
	cin>>n;
	while(n--) cin>>s,build(root,s);
	pre(root);
	return 0;
}
// 4 aa abc acd bc

版权声明

• 本文档归cout0所有，仅供学习使用，未经允许，不得转载。