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

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

news 2024/9/27 9:40:05

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.cppBTNode* 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;
}

层次遍历

如果有孩子，就加入队列；然后自己退出队列。
画图说明：
遍历到A:将A的左右子节点B,C加入队列，然后A退出队列
在这里插入图片描述
遍历到B,把B的左子节点加入，然后B退出
在这里插入图片描述

在这里插入图片描述
这样我们B,C遍历完后正好到D,E,F这一层，而且顺序也符合要求，这就是层次遍历的基本方法。

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;//DLRcout << "DLR:";PreOrder(root);cout<<endl;//LDRcout << "LDR:";InOrder(root);cout << endl;//LRDcout << "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.mrgr.cn/news/37281.html

相关文章：

  • 【单元测试】任务3：JUnit assertThat断言
  • ppython 实现k nearest neighbours k最近邻分类算法
  • python 实现knn sklearn K近邻分类算法
  • LeetCode //C - 387. First Unique Character in a String
  • Spring Boot 进阶- Spring Boot日志框架介绍
  • ArcGIS与ArcGIS Pro去除在线地图服务名单
  • C++：笔试题
  • 深入理解C#中的装箱与拆箱操作及其性能影响
  • 力扣经典笔试题 最小K个数 小根堆 大根堆 快速排序 一题多解
  • 硬件设计很简单？合宙低功耗4G模组Air780E—开机启动及外围电路设计
  • 代码随想录算法训练营第四四天| 1143.最长公共子序列 1035.不相交的线 53. 最大子序和 392.判断子序列
  • 大学生科技竞赛系统小程序的设计
  • Day 2 词汇备战
  • MySQL_插入、更新和删除数据
  • 【Python报错已解决】TypeError: list indices must be integers or slices, not str
  • [网络]数据链路层-MAC帧与ARP协议
  • java日志门面之JCL和SLF4J
  • ICM20948 DMP代码详解（46）
  • 个人文章汇总(MyBatis)
  • 解决 Adobe 盗版弹窗