当前位置： 首页 > article >正文

C++实现二叉树的创建删除，dfslfs,求叶子结点个数，求叶子结点个数，求树的高度

article 2024/12/25 2:26:08

C++实现二叉树的创建删除，dfs/lfs,求叶子结点个数，求树的高度

基本算法：

用链栈建立二叉树，通过递归实现深度优先的三种遍历，用队列实现广度优先层次遍历。借助递归思想求解叶子结点个数和树的深度。

tree.h定义基本的框架，包括结点的定义，创建树时用的栈，lfs遍历用到的队列等。

在教材上经常出现用数组实现栈，这里不妨用链表实现。

例子

A(B(D(,G)),C(E,F))
在这里插入图片描述

//tree.h
#pragma once
typedef char BTNodeDataType;
struct 	BTNode
{
	BTNodeDataType data;
	struct BTNode* lchild;
	struct BTNode* rchild;
	struct BTNode* parent;

};

struct TreeStackNode
{
	BTNode* treenode;
	TreeStackNode* next;
};

struct BTQueueNode
{
	BTNode* data;
	BTQueueNode* next;
};

struct BTQueue
{
	BTQueueNode* front;
	BTQueueNode* rear;
};

TreeStackNode* InitTreeStackNode();

//全局变量ts,便于多文件调用
extern TreeStackNode* ts = InitTreeStackNode();

void PushStack(TreeStackNode*& root,
	TreeStackNode*& decendent);

void DestroyStack(TreeStackNode*& s);
void PopStack(TreeStackNode*& root);

BTNode* InitBTNode();
void InsertBT(BTNode*& n, BTNodeDataType d, int i);
void DispBT(BTNode*& root);

string GetBTString(BTNode*& root);
BTQueueNode* InitBTQueueNode();

BTQueue* InitBTQueue();
void EnQueue(BTQueue*& queue, BTNode* data);
void DeQueue(BTQueue*& queue);
BTQueueNode* GetQueueFront(BTQueue*& queue);

void PreOrder(BTNode*& root);
void InOrder(BTNode*& root);
void PostOrder(BTNode*& root);

int CountLeaf(BTNode* root);
int GetHeight(BTNode* root);

定义组成元素为结点的队列

//BTNodeQueue.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
BTQueue* InitBTQueue()
{
	BTQueue* queue= (BTQueue*)malloc(sizeof(BTQueue*));
	queue->front = NULL;
	queue->rear = NULL;
	return queue;

}


void EnQueue(BTQueue*& queue,BTNode* data)
{
	BTQueueNode* newnode;
	newnode =
		(BTQueueNode*)malloc(sizeof(BTQueueNode*));
	newnode->data = data;
	newnode->next = NULL;
	
	if (queue->front == NULL && queue->rear == NULL)
	{
		queue->front = queue->rear = newnode;
	}
	else
	{
		queue->rear->next = newnode;
		queue->rear = queue->rear->next;
	}

}
void DeQueue(BTQueue*& queue)
{
	if (queue->front == NULL)
	{
		cout << "Queue is empty" << endl;
		return;
	}
	if (queue->front == queue->rear )
	{
		queue->front = queue->rear = NULL;
		return;
	}
	BTQueueNode* q = queue->front;
	queue->front = queue->front->next;
	q->data = NULL;
	free(q->data);
	q->next = NULL;
	free(q->next);
	q->next = NULL;
	q = NULL;

}

BTQueueNode* GetQueueFront(BTQueue*& queue)
{
	return queue->front;
}

插入结点过程：

先构建根结点，用left_value判断是否有左节点，如果有就退栈；(x,x)插入右节点前先退栈，之后新节点入栈，(,x)插入右节点，之后新节点入栈。k判断下一个要插入的是左节点还是右节点。

1是左，2是右。

画图理解：G的插入：插入G,然后G入栈、

在这里插入图片描述

C的插入，G,D,B依次退栈，然后C插入后入栈。

在这里插入图片描述

E,F插入：插入E,然后E入栈,遇到逗号，E退栈，插入F,然后F入栈

在这里插入图片描述

	//main.cpp
	BTNode* root = InitBTNode();
	
    //树的根节点root从ts_next开始
	TreeStackNode* n = InitTreeStackNode();
	ts->next = n;
	ts->next->treenode = root;
	string s = "A(B(D(,G)),C(E,F))";
	char* c = &s[0]; int k = 1; 
	//用left_value判断是否有左节点，如果有就退栈
	//(_,_)插入右节点先退栈，(,_)插入右节点不退栈
	bool left_value=false;
	for (int i = 0; i < s.length(); i++)
	{
		if (*c == '(')
		{
			left_value = false;
			k = 1;
		}
		else if (*c == ')')
		{
			PopStack(ts);
		}
		else if (*c == ',')
		{
			if (left_value)
			{
				PopStack(ts);	
			}
			k = 2;
		}
		else
		{
			InsertBT(ts->next->treenode, *c, k);
			left_value = true;
		}
		c++;
	}

链栈对应的push，pop操作

void PushStack(TreeStackNode*& root,TreeStackNode*& decendent)
{
	//头插法进栈,带头结点
	if (root->next == NULL)
	{
		root->next = decendent;
	}
	else
	{
		TreeStackNode* q = root->next;
		root->next = decendent;
		decendent->next = q;
	}
}

void PopStack(TreeStackNode*& root)
{
	//退栈
	if (root->next == NULL)
	{
		cout << "Stack is Empty" << endl;
		return ;
	}
	else if (root->next->next == NULL)
	{

		TreeStackNode* p = root->next;
		root->next = NULL;
		//这里不能随便free掉，毕竟结点已经加进去二叉树了
        //free(p);
		//p = NULL;
	
	}
	else
	{
		TreeStackNode* p = root->next;
		TreeStackNode* q = p->next;
		root->next = q;
        //free(p);
		//p = NULL;

	}
}

在二叉树中插入结点的过程，k判断下一个要插入的是左节点还是右节点。1是左，2是右。

//tree.cpp
void InsertBT(BTNode*& n, BTNodeDataType d, int i)
{
	TreeStackNode* newstacknode =
		InitTreeStackNode();
	if (n->data == NULL)
	{
		n->data = d;
		newstacknode->treenode = n;
	}
	else
	{
		BTNode* new_node = InitBTNode();
		new_node->data = d;
		//new_node->parent = n;
		switch (i)
		{
		case 1:
			n->lchild = new_node;
			break;
		case 2:
			n->rchild = new_node;
			break;
		}
		newstacknode->treenode = new_node;
	}
	//新插入的结点进栈
	
	PushStack(ts,newstacknode);

}

从一个结点获得二叉树的字符串表示,

利用递归的思想，如果有孩子，先加左括号，然后如果有左节点，递归到左节点；如果有右节点，加逗号，递归到右节点，加括号：

void DispBT(BTNode*& root)
{
    if(root==nullptr) return;
	cout << root->data;
	if (root->lchild != NULL || root->rchild != NULL)
	{
		cout << "(";
		if (root->lchild != NULL)
			DispBT(root->lchild);
		if (root->rchild != NULL)
		{
			cout << ",";
			DispBT(root->rchild);
		}
		cout << ")";

	}
	
}

string GetBTString(BTNode*& root)
{
	static string s= "";
	
	s+= root->data;
	if (root->lchild != NULL || root->rchild != NULL)
	{
		s += "(";
		if (root->lchild != NULL)
			GetBTString(root->lchild);
		if (root->rchild != NULL)
		{
			s += ",";
			GetBTString(root->rchild);
		}
		s += ")";

	}
	return s;
}

层次遍历

如果有孩子，就加入队列；然后自己退出队列。

cout << "层次遍历：";
	BTQueue* queue = InitBTQueue();
	BTNode* p = root;
	EnQueue(queue, p);
	while (queue->front != NULL)
	{
		cout << p->data;
		DeQueue(queue);
		if(p->lchild!=NULL)
			EnQueue(queue, p->lchild);
		if (p->rchild != NULL)
			EnQueue(queue, p->rchild);
		if (queue->front != NULL)
		{
			p = queue->front->data;
		}
	}
	cout << endl;

完整代码

//tree.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
#include<math.h>

BTNode* InitBTNode()
{
	BTNode* n = (BTNode*)malloc(sizeof(BTNode*));
	n->data = NULL;
	n->lchild = NULL;
	//n->parent = NULL;
	n->rchild = NULL;
	return n;

}

void InsertBT(BTNode*& n, BTNodeDataType d, int i)
{
	TreeStackNode* newstacknode =
		InitTreeStackNode();
	if (n->data == NULL)
	{
		n->data = d;
		newstacknode->treenode = n;
	}
	else
	{
		BTNode* new_node = InitBTNode();
		new_node->data = d;
		//new_node->parent = n;
		switch (i)
		{
		case 1:
			n->lchild = new_node;
			break;
		case 2:
			n->rchild = new_node;
			break;
		}
		newstacknode->treenode = new_node;
	}
	//新插入的结点进栈
	
	PushStack(ts,newstacknode);

}

void DispBT(BTNode*& root)
{
    if(root==nullptr) return;
	cout << root->data;
	if (root->lchild != NULL || root->rchild != NULL)
	{
		cout << "(";
		if (root->lchild != NULL)
			DispBT(root->lchild);
		if (root->rchild != NULL)
		{
			cout << ",";
			DispBT(root->rchild);
		}
		cout << ")";

	}
	
}

string GetBTString(BTNode*& root)
{
	static string s= "";
	
	s+= root->data;
	if (root->lchild != NULL || root->rchild != NULL)
	{
		s += "(";
		if (root->lchild != NULL)
			GetBTString(root->lchild);
		if (root->rchild != NULL)
		{
			s += ",";
			GetBTString(root->rchild);
		}
		s += ")";

	}
	return s;
}

void PreOrder(BTNode*& root)
{
	if (root == NULL)
	{
		return;
	}
	cout << root->data;
	PreOrder(root->lchild);
	PreOrder(root->rchild);

}

void InOrder(BTNode*& root)
{
	if (root == NULL)
	{
		return;
	}
	InOrder(root->lchild);
	cout << root->data;
	InOrder(root->rchild);

}
void PostOrder(BTNode*& root)
{
	if (root == NULL)
	{
		return;
	}
	PostOrder(root->lchild);
	PostOrder(root->rchild);
	cout << root->data;

}

int CountLeaf(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	if (root->lchild == NULL && root->lchild == NULL)
		return 1;

	return CountLeaf(root->lchild) + CountLeaf(root->rchild);
}

int GetHeight(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}
	return max(GetHeight(root->lchild), GetHeight(root->rchild)) + 1;
}


TreeStackNode* InitTreeStackNode()
{
	TreeStackNode* s;
	s=(TreeStackNode*)malloc(sizeof(TreeStackNode*));
	s->treenode = (BTNode*)malloc(sizeof(BTNode*));
	s->treenode = NULL;
	s->next = NULL;
	return s;
}

void PushStack(TreeStackNode*& root,TreeStackNode*& decendent)
{
	//头插法进栈,带头结点
	if (root->next == NULL)
	{
		root->next = decendent;
	}
	else
	{
		TreeStackNode* q = root->next;
		root->next = decendent;
		decendent->next = q;
	}
}

void PopStack(TreeStackNode*& root)
{
	//退栈
	if (root->next == NULL)
	{
		cout << "Stack is Empty" << endl;
		return ;
	}
	else if (root->next->next == NULL)
	{

		TreeStackNode* p = root->next;
		root->next = NULL;
        free(p);
		p = NULL;
	
	}
	else
	{
		TreeStackNode* p = root->next;
		TreeStackNode* q = p->next;
		root->next = q;
        free(p);
		p = NULL;

	}
}


//main.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
void test1()
{
	BTNode* root = InitBTNode();
	
    //树的根节点root从ts_next开始
	TreeStackNode* n = InitTreeStackNode();
	ts->next = n;
	ts->next->treenode = root;
	string s = "A(B(D(,G)),C(E,F))";
	char* c = &s[0]; int k = 1; 
	//用left_value判断是否有左节点，如果有就退栈
	//(_,_)插入右节点先退栈，(,_)插入右节点不退栈
	bool left_value=false;
	for (int i = 0; i < s.length(); i++)
	{
		if (*c == '(')
		{
			left_value = false;
			k = 1;
		}
		else if (*c == ')')
		{
			PopStack(ts);
		}
		else if (*c == ',')
		{
			if (left_value)
			{
				PopStack(ts);	
			}
			k = 2;
		}
		else
		{
			InsertBT(ts->next->treenode, *c, k);
			left_value = true;
		}
		c++;
	}
	string  BTString = GetBTString(root);
	cout << BTString << endl;
	
	cout << "层次遍历：";
	BTQueue* queue = InitBTQueue();
	BTNode* p = root;
	EnQueue(queue, p);
	while (queue->front != NULL)
	{
		cout << p->data;
		DeQueue(queue);
		if(p->lchild!=NULL)
			EnQueue(queue, p->lchild);
		if (p->rchild != NULL)
			EnQueue(queue, p->rchild);
		if (queue->front != NULL)
		{
			p = queue->front->data;
		}
	}
	cout << endl;

	//DLR
	cout << "DLR:";
	PreOrder(root);
	cout<<endl;

	//LDR
	cout << "LDR:";

	InOrder(root);
	cout << endl;
	//LRD
	cout << "LRD:";

	PostOrder(root);
	cout << endl;

	int Count =CountLeaf(root);
	cout << "叶子结点有" << Count << "个" << endl;

	int height = GetHeight(root);
	cout << "树的高度是：" << height << endl;
}

int main()
{
	test1();
	return 0;
}

结果展示

在这里插入图片描述


http://www.kler.cn/a/321350.html

相关文章：

  • Java - 日志体系_Apache Commons Logging（JCL）日志接口库
  • kotlin中泛型中in和out的区别
  • 使用FakeSMTP创建本地SMTP服务器接收邮件具体实现。
  • 人脸生成3d模型 Era3D
  • 浅析InnoDB引擎架构（已完结）
  • 前端使用 Konva 实现可视化设计器（20）- 性能优化、UI 美化
  • D19【python接口自动化学习】-python基础之内置数据类型
  • 矿石运输船数据集、散货船数据集、普通货船数据集、集装箱船数据集、渔船数据集以及客船数据集
  • Web3Auth 如何工作？
  • 相机、镜头参数详解以及相关计算公式
  • 【OceanBase 诊断调优】—— GC问题根因分析
  • centos7 启动mongodb时报错ERROR: child process failed, exited with error number 1
  • electron使用npm install出现下载失败的问题
  • 【HTML】img标签和超链接标签
  • Apache Iceberg 概述
  • ansible playbook多个play多个task
  • ChatGPT高级语音助手正式上线！OpenAI：50多种语言、9种声线可选
  • 磨具生产制造9人共用一台工作站
  • elasticsearch的Ingest Attachment插件的使用总结
  • 数据结构之链表（1），单链表
  • 微服务MongoDB解析部署使用全流程
  • C嘎嘎入门篇：类和对象（1）
  • excel单元格增加可选下拉列表
  • 玩转指针(3)
  • JVM 垃圾回收算法细节
  • 第13讲 实践：设计SLAM系统