构造二叉树及其基本操作（操作全）

二叉树的基本操作如下

构造一棵二叉树

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

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