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

构造二叉树及其基本操作(操作全)

程序员文章站 2022-06-16 08:27:27
二叉树的基本操作如下构造一棵二叉树运用递归,从二叉树的根结点出发,先构造左子树再构造右子树,当输入"#"表示为空,跳回上一层。BiNode* BiTree::Create(){BiNode* bt;datatype ch;cin >> ch;if (ch == '#')bt = NULL;else{bt = new BiNode;bt->data = ch;bt->lchild = Create();bt->rchild...

二叉树的基本操作如下

构造一棵二叉树

运用递归,从二叉树的根结点出发,先构造左子树再构造右子树,当输入"#"表示为空,跳回上一层。

BiNode* BiTree::Create()
{
	BiNode* bt;
	datatype ch;
	cin >> ch;
	if (ch == '#')bt = NULL;
	else
	{
		bt = new BiNode;
		bt->data = ch;
		bt->lchild = Create();
		bt->rchild = Create();
	}
	return bt;
}

二叉树的前中后序的递归遍历
其实就是输出根结点的位置为前中后。

void BiTree::PreOrder(BiNode* bt)
{
	if (bt == NULL)return;
	else
	{
		cout << bt->data << endl;
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}

void BiTree::InOrder(BiNode* bt)
{
	if (bt == NULL)return;
	else
	{
		InOrder(bt->lchild);
		cout << bt->data << endl;
		InOrder(bt->rchild);
	}
}

void BiTree::PostOrder(BiNode* bt)
{
	if (bt == NULL)return;else
	{
		PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		cout << bt->data << endl;
	}
}

二叉树的非递归前序遍历
首先我们需要一个栈,先将root入栈,然后出栈(此时出的就是root)输出,如果有右结点则入右结点,有左节点则入左节点,注意顺序,因为是前序遍历所以让右结点先入左结点后入,这样会保证左结点先出栈,循环直到栈空。

void BiTree::IterativePreorder()
{
	BiNode* stack[Max];
	int top = -1;
	if (root == NULL)return;
	stack[++top] = root;
	while (top!=-1)
	{
		BiNode* p = stack[top];
		cout << p->data << endl;
		top--;
		if (p->rchild != NULL)stack[++top] = p->rchild;
		if (p->lchild != NULL)stack[++top] = p->lchild;
	}
}

二叉树的层序遍历
需要用到一个队列,先将根结点入队。然后将队列中的队首元素(这时就是根结点)出队、输出,再把当前出队结点的左右子节点压入队列(如果左右结点不为空的话),循环直到队列为空。

在这里插入代码片void BiTree::LevelOrder()
{
	BiNode* Q[Max], * q = NULL;
	int front = -1, rear = -1;
	if (root == NULL) return;
	Q[++rear] = root;
	while (front != rear)
	{
		q = Q[++front];
		cout << q->data << endl;
		if (q->lchild != NULL)Q[++rear] = q->lchild;
		if (q->rchild != NULL)Q[++rear] = q->rchild;
	}
}

求二叉树的高度
DFS,先一直往左走直到尽头,再跳回往右,把所有路径遍历一遍比较得出最大的高度。

int h=0,ht=0;
void BiTree::get_high(BiNode* bt)
{
	ht++;
	if (bt == NULL)return;
	if (bt->lchild == NULL && bt->rchild == NULL)
	{
		h = max(h, ht);
		return;
	}
	get_high(bt->lchild);
	ht--;
	get_high(bt->rchild);
	ht--;
}

求二叉树度为0、度为1、度为2的结点的个数
DFS将二叉树遍历一遍,看其左右结点是否为空逐一记录各度的结点数。

int d1=0, d2=0, d0=0;
void BiTree::get_node(BiNode* bt)
{
	if (bt->lchild != NULL && bt->rchild != NULL)
	{
		d2++;
		get_node(bt->lchild);
		get_node(bt->rchild);
	}
	else if (bt->lchild!=NULL)
	{
		d1++;
		get_node(bt->lchild);
	}
	else if (bt->rchild != NULL)
	{
		d1++;
		get_node(bt->rchild);
	}
	else
	{
		d0++;
		return;
	}
}

总代码

#include<iostream>
#include<string>
#include<map>
#include<algorithm>
#include<memory.h>
#include<cmath>
#include<queue>
#define pii pair<int,int>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
typedef char datatype;
const int Max = 1e3 + 5;
int h=0,ht=0, d1=0, d2=0, d0=0;

struct BiNode
{
	datatype data;
	BiNode *lchild, *rchild;
};
BiNode* fa;
class BiTree
{
public:
	BiTree() { root = Create(); }
	void PreOrder() { PreOrder(root); }
	void InOrder() { InOrder(root); }
	void PostOrder() { PostOrder(root); }
	void LevelOrder();
	void IterativePreorder();
	void get_high() { h = 0;get_high(root); }
	void get_node() { d0 = d1 = d2 = 0;get_node(root); }
	void get_width();
private:
	BiNode* Create();
	void Release(BiNode* bt);
	void PreOrder(BiNode* bt);
	void InOrder(BiNode* bt);
	void PostOrder(BiNode* bt);
	void get_high(BiNode* bt);
	void get_node(BiNode* bt);
	BiNode* root;
};

void BiTree::IterativePreorder()
{
	BiNode* stack[Max];
	int top = -1;
	if (root == NULL)return;
	stack[++top] = root;
	while (top!=-1)
	{
		BiNode* p = stack[top];
		cout << p->data << endl;
		top--;
		if (p->rchild != NULL)stack[++top] = p->rchild;
		if (p->lchild != NULL)stack[++top] = p->lchild;
	}
}

void BiTree::get_node(BiNode* bt)
{
	if (bt->lchild != NULL && bt->rchild != NULL)
	{
		d2++;
		get_node(bt->lchild);
		get_node(bt->rchild);
	}
	else if (bt->lchild!=NULL)
	{
		d1++;
		get_node(bt->lchild);
	}
	else if (bt->rchild != NULL)
	{
		d1++;
		get_node(bt->rchild);
	}
	else
	{
		d0++;
		return;
	}
}

void BiTree::get_high(BiNode* bt)
{
	ht++;
	if (bt == NULL)return;
	if (bt->lchild == NULL && bt->rchild == NULL)
	{
		h = max(h, ht);
		return;
	}
	get_high(bt->lchild);
	ht--;
	get_high(bt->rchild);
	ht--;
}

void BiTree::PreOrder(BiNode* bt)
{
	if (bt == NULL)return;
	else
	{
		cout << bt->data << endl;
		PreOrder(bt->lchild);
		PreOrder(bt->rchild);
	}
}

void BiTree::InOrder(BiNode* bt)
{
	if (bt == NULL)return;
	else
	{
		InOrder(bt->lchild);
		cout << bt->data << endl;
		InOrder(bt->rchild);
	}
}

void BiTree::PostOrder(BiNode* bt)
{
	if (bt == NULL)return;
	else
	{
		PostOrder(bt->lchild);
		PostOrder(bt->rchild);
		cout << bt->data << endl;
	}
}

void BiTree::LevelOrder()
{
	BiNode* Q[Max], * q = NULL;
	int front = -1, rear = -1;
	if (root == NULL) return;
	Q[++rear] = root;
	while (front != rear)
	{
		q = Q[++front];
		cout << q->data << endl;
		if (q->lchild != NULL)Q[++rear] = q->lchild;
		if (q->rchild != NULL)Q[++rear] = q->rchild;
	}
}

BiNode* BiTree::Create()
{
	BiNode* bt;
	datatype ch;
	cin >> ch;
	if (ch == '#')bt = NULL;
	else
	{
		bt = new BiNode;
		bt->data = ch;
		bt->lchild = Create();
		bt->rchild = Create();
	}
	return bt;
}

码字不易给个赞吧QAQ

本文地址:https://blog.csdn.net/asbbv/article/details/109625531