C++学习记录-数据结构-求二叉树的高度

发表于2022-03-29|更新于2025-07-13|数据结构与算法

|浏览量:

C++学习记录-数据结构-求二叉树的高度

int findHeight(Node *p=root)
{
	if (p == NULL)
	{
		return -1;//如果高度规定从1开始计数，则返回0
	}
	else
	{
		return max(findHeight(p->left), findHeight(p->right)) + 1;
        //此处会算出当前节点的高度
	}
}//递归法实现求二叉树的高度

文章作者: 星辰微光

文章链接: http://example.com/2022/03/29/C++-%E5%AD%A6%E4%B9%A0%E8%AE%B0%E5%BD%95-%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-%E6%B1%82%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E9%AB%98%E5%BA%A6/

版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源星辰微光的博客！

C++数据结构

相关推荐

C++学习记录-数据结构-二叉搜索树删除节点

C++学习记录-数据结构-二叉搜索树删除节点从二叉搜索树中删除节点，有三种可能的情况：情况1：欲删除的节点是叶子节点：只需切断链接情况2：欲删除的节点有一个子节点，则令其父节点的指针指向子节点情况3：与删除的节点有两个子节点：另节点的值等于其右子树的最小值，再删除右子树的最小值代码示例：删除节点函数： 1234567891011121314151617181920212223242526272829303132333435363738394041424344Node* deletenode(Node* root,int value){ //第一步，找出节点 if (root == NULL) { return NULL; } else if (root->data > value) { root->left = deletenode(root->left, value); } //如果当前节点的值大于欲删除的值，左拐 else if (root->data <...

C++学习记录-数据结构-二叉树的插入和查找数字

C++学习记录-数据结构-二叉树的插入和查找数字迭代法实现插入 123456789101112131415161718192021222324252627282930313233343536373839404142434445void Insert(int num){ scanner = root;//首先保存一下根节点的地址 if (root == NULL)//如果根节点为空 { root = new Node; root->data = num;//new一个并赋值 scanner = root;//扫描指针重新定位到根节点 return; } else//如果根节点不为空 { while (true) { if (root->data >= num)//如果当前节点的数据大于等于欲插入的数据，则要左拐 { if (root->left != NULL) { root = root->left;...

C++学习记录-数据结构-二叉树的遍历

C++学习记录-数据结构-二叉树的遍历二叉树的层次遍历（宽度优先遍历）利用队列的特性 123456789101112131415161718192021222324252627282930void BFS(){ Node* arr[100]; //创建一个队列数组存储节点的地址，可以使用STL里的队列 arr[0] = root; int head = 0; int tail = 1; //存入根节点，定义头尾 while (head != tail)//当头部不等于尾部的时候，即队列不为空时 { cout << arr[head]->data << " "; if (arr[head]->left != NULL) { arr[tail] = arr[head]->left; tail++; }//左孩入队 if (arr[head]->right !=...

C++学习记录-数据结构-链表

C++学习记录-数据结构-链表当要按顺序储存一大组数据，且要随时往里面增减数据，此时数组就显得不方便，用链表则会快很多链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多代码实现： 1.创建链表结构体 12345struct data { int dat;//用于储存数据 data* next=NULL;//用于指向下一个数据}; 2.定义用于指示的变量 1234567int num = 0;//定义一个整形变量用于计算链表中数据的数量int dat;//用于录入数据struct data* head=NULL;//定义一个头指针指向链表的第一个数据struct data* point =...

C++学习记录-数据结构-链表的两种反转

链表的两种反转首先创建一个链表： 123456struct Node { int data; Node* next = NULL;};Node* head = NULL;//指向头部的指针 1.递归法反转链表 12345678910111213void reserve(Node *p){ if (p->next == NULL) { head = p; return; } reserve(p->next); p->next->next = p; p->next = NULL; return;}//链表的递归反转，开始时传入头指针head 2.迭代法反转链表 12345678910111213141516void reserveBydiedai(){ Node* prev = NULL; Node* now = head; Node* nex; while (now != NULL) { nex = now->next; now->next =...

C++学习记录-数据结构-队列与栈

C++学习记录-数据结构-队列与栈一、队列队列是一种先进先出的线性结构。在它的头部只允许进行出队（删除）操作，在它的尾部只允许进行入队（插入）操作，即“先进先出”。具体操作： 1.定义一个数组arr 2.定义一个int head=0，指向数组第一位 3.定义一个int tail=0，指向数组第一位（此时数组为空队列） 4.入队，arr[tail]=x；tail++ 5.出队，即head++ 当head=tail时，队列为空队列代码示例：解密QQ号给一串数字，先将第1个数删除，再将第2个数放到末尾，将第3个数删除，再将第4个数放到末尾…直到最后一个数，将最后一个数删除。最后把删除的数按顺序连在一起即为所求QQ号分析：删除即为出队操作，放到末尾即为出队后入队操作 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<iostream>using namespace std;char...

数据加载中