文章目录

前言

本篇主要以二叉树的认识，构建，遍历为主。

一、树的认识

1.定义

  树由节点（node）和边（edge）组成，形成一个层级结构。每棵树有一个根节点（root），而其他节点通过边与根节点相连。

2. 树的基本特性

  节点（Node）： 树的基本组成单位，包含值和指向子节点的链接。
  边（Edge）： 连接节点的线，表示它们之间的关系。
  根节点（Root）： 树的顶层节点，没有父节点。
  叶子节点（Leaf Node）： 没有任何子节点的节点。
  内部节点（Internal Node）： 至少有一个子节点的节点。
  深度（Depth）： 一个节点到根节点的路径长度。
  高度（Height）： 从某一节点到其最远叶子节点的最长路径长度；树的高度是其根节点的高度。
  子树（Subtree）： 每个节点及其所有后代组成的树也是一棵树。
  满二叉树(Perfect Binary Tree)： 一个深度为k(>=-1)且有2^(k+1) - 1个结点的二叉树称为满二叉树。 (又称“完美二叉树”)。
  完全二叉树(Complete Binary Tree) ：完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充，其叶子结点都靠左对齐。

3.树的相关性质及计算

1.二叉树在第i层最多有2(i-1)个结点。当最后一层结点达到2(i-1) 时，该树为满二叉树。

第一层：1
第二层：2
第三层：4
……
第i层：2(i-1)

2.深度为k的二叉树最多有2k -1个结点。

因为第k层结点最多为2k-1 个
所以根据等差数列前k项之和为：(1-qn )/(1-q) = (1-2n )/(1-2) = 2k-1

3.对任意一棵二叉树T，如果度数为0的结点个数为n0，度数为2的结点个数为n1，度数为2 的结点个数为n2，则n0=n2+1。

证明如下：
  令该树的总结点数为 n
  n=n0+n1+n2
  n=1+ n1 +n2 * 2
  联立以上等式：n0+n1+n2=1+n1+n2*2
得证：n0=n2+1

4.具有n个结点的完全二叉树的深度为：depth=⌊log2(n)⌋+1

证明如下：
将二叉树分为两部分，最后一行看做一部分（part2），以上的看做一部分（part1）。
⌊log2(n)⌋计算的为part1的深度，再加上取下界舍去的一层
所以得证

5.性质5 如果将一棵有 n个结点的完全二叉树的结点按层序(自顶向下， 同一层自左向右)连续编号1，2， …，n， 并简称编号为 i 的结点为结点i ( 1 ≤ i ≤ n ),则有以下关系成立：
(1) 若 i = 1 ,则结点i 是二叉树的根,无双亲； 若 i > 1 ,则i的双亲为结点 ⌊i/2⌋ 。

证明如下：
已知该结点的层从左往右数，该结点为第k1个，编号为n1，深度depth1=⌊log2(n1)⌋+1
n1=2depth1-1 -1+k1

如果存在孩子n2.
因为一个结点有两个孩子，所以父类同层的前面节点（k-1）会产生(k-1)*2个 结点，最后加上自己?(左孩子1，右孩子2)
k2=(k1-1)*2+?,
由于是孩子，所以深度为父亲结点深度+1
depth2=depth1 + 1

n2=2depth2-1 -1+k2
 =2depth1+1-1 -1+(k1-1)*2+?
 =2depth1 +2 * k1-3+?
 =2 * 2depth1-1 +2 * k1-3+?

 由于n1= ⌊n2/2⌋
所以得证

(2) 若 2i ≤ n ,则i的左孩子为 2i ， 否则无左孩子。

由(1)可知
n1=2depth1-1 +k1-1
因为是左孩子，所以?=1
所以n2=2 * 2depth1-1 +2 * k1-2
n2=2 * n1
所以得证

(3) 若 2i + 1 ≤ n 则 i 的右孩子为 2i+1 ,否则无右孩子。

由(2)可知：n2(左)=2*i
所以右孩子为 2i+1

二、树的遍历(前，中，后)

1.前序遍历（Pre-order Traversal）：

访问顺序：根节点 → 左子树 → 右子树
过程：先访问当前节点，然后递归遍历左子树，最后递归遍历右子树。

void preOrder(TreeNode* root) {  
    if (root) {  
        cout << root->value << " "; // 访问当前节点  
        preOrder(root->left);       // 遍历左子树  
        preOrder(root->right);      // 遍历右子树  
    }  
}

2.中序遍历（In-order Traversal）：

访问顺序：左子树 → 根节点 → 右子树
过程：先递归遍历左子树，然后访问当前节点，最后递归遍历右子树。

void inOrder(TreeNode* root) {  
    if (root) {  
        inOrder(root->left);       // 遍历左子树  
        cout << root->value << " "; // 访问当前节点  
        inOrder(root->right);      // 遍历右子树  
    }  
}

3.后序遍历（Post-order Traversal）：

访问顺序：左子树 → 右子树 → 根节点
过程：先递归遍历左子树，然后递归遍历右子树，最后访问当前节点。

void postOrder(TreeNode* root) {  
    if (root) {  
        postOrder(root->left);     // 遍历左子树  
        postOrder(root->right);    // 遍历右子树  
        cout << root->value << " "; // 访问当前节点  
    }  
}

4.暴力秒解法（做题）


三、树的构建

存储方式

1.顺序存储（简单提及）

 顺序存储时，首先必须对树结构的结点进行某种方式 的线性化，使之成为一个线性序列，然后存储。完全 二叉树和满二叉树采用顺序存储结构比较合适，因为 根据二叉树中的结点序号可以唯一地反映出结点之间 的逻辑关系。
  顺序存储是指按照完全二叉树结点的编号顺序，用一 组连续的存储单元存放结点内容。在一棵完全二叉树 中，按照从根结点起、自上而下、从左至右的方式对 结点进行顺序编号，便可得到一个反映结点之间关系 的线性序列。这种存储结构可以反映完全二叉树结点 的层次和顺序，既简单又节省存储空间。

c语言代码如下（参考课本）：

#define maxsize 1024;
typedef char datatype;
typedef struct{
	datdtype data[maxsize];
	int last;
}sequenlist;

由于该方式是用数组存储，所以数组下标即为结点编号。如果存入结点为空，则可用其他字符表示（例如：@）。
父类语子类的关系则通过上面提到的关系计算其位置。

2.链式存储（重点讲解）

相比于顺序存储，二叉树一般采用链式存储结构来表示，因为链式存储有动态内存分配，灵活的结构，简化的插入和删除操作，支持多种数据类型等顺序存储所不具有的优点。

1.结点构造代码如下（示例）：

struct Birtree {  //结点的建立
    int data;  
    Birtree* left;  // 没有节点则为NULL  
    Birtree* right; // 没有节点则为NULL  
};

结点主要包括存储的数据及左右结点地址

2.树的构造代码如下（示例）：

void creatBiTree(Birtree* &T) {  // 先序遍历
    int n;  
    cout << "请输入当前结点的data的值,0代表当前节点为NULL:" ;  
    cin >> n;  
    if (n == 0) {  //n为0表示叶子结点，没有子类，所以设为NULL
        T = NULL;  
        return;  
    } else {  
        T = new Birtree;  
        T->data = n;  //根
        creatBiTree(T->left);//左  
        creatBiTree(T->right); //右
    }  
}

3.树的遍历代码如下（示例）：

// 先序遍历  
void preTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        cout << T->data << " ";  //根
        preTree(T->left);//左    
        preTree(T->right);  //右
    }  
}  

// 中序遍历  
void midTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        midTree(T->left);  //左   
        cout << T->data << " ";  //根
        midTree(T->right);  //右
    }  
}  

// 后序遍历  
void postTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        postTree(T->left);  //左
        postTree(T->right);  //右
        cout << T->data << " ";  //根
    }  
}

通过代码我们不难发现，三种遍历的代码几乎一样，唯一的不同就是三行代码的顺序

4.计算二叉树的深度代码如下（示例）：

int depthtree(Birtree* T){
    int m,n;
    if(T==NULL) return 0;
    else{
        m=depthtree(T->left);//统计最长左子树深度
        n=depthtree(T->right);//统计最长右子树深度
        if(m>n) return (m+1);//每次遍历计算深度，最后找出最大深度
        else return (n+1);
    }
}

5.计算二叉树的叶子结点总数代码如下（示例）：

int yezinumbertree(Birtree* T){
    if(T==NULL) return 0;
    if(T->left==NULL&&T->right==NULL){
        cout << "先序排列的叶子结点的值为：" << T->data << endl;
        return 1;
    } 
    else{
        return yezinumbertree(T->left)+yezinumbertree(T->right);
    }//对叶子结点返回的1进行累加，最后返回
}

5.计算二叉树的结点总数代码如下（示例）：

int nodenumbertree(Birtree* T){
    if(T==NULL) return 0;//判断树是否为空
    else{
        return nodenumbertree(T->left)+nodenumbertree(T->right)+1;
    }//对非空的树，每一次遍历加一
}

6.复制二叉树 代码如下（示例）：

void copyTree(Birtree* T, Birtree* &NewT) {  // 使用引用以操控指针  
    if (T == NULL) {  
        NewT = NULL;  
        return;  
    } else {  
        NewT = new Birtree;  //创建结点
        NewT->data = T->data;  //传值
        copyTree(T->left, NewT->left);  
        copyTree(T->right, NewT->right);  
    }  
}

7.总体代码展示

#include <bits/stdc++.h>  
using namespace std;  

struct Birtree {  
    int data;  
    Birtree* left;  // 没有节点则为NULL  
    Birtree* right; // 没有节点则为NULL  
};  

// 先序构建二叉树  
void creatBiTree(Birtree* &T) {  // 使用引用以操控指针  
    int n;  
    cout << "请输入当前结点的data的值,0代表当前节点为NULL:" ;  
    cin >> n;  
    if (n == 0) {  
        T = NULL;  
        return;  
    } else {  
        T = new Birtree;  
        T->data = n;  
        creatBiTree(T->left);  
        creatBiTree(T->right);  
    }  
}  

// 先序遍历  
void preTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        cout << T->data << " ";  
        preTree(T->left);  
        preTree(T->right);  
    }  
}  

// 中序遍历  
void midTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        midTree(T->left);  
        cout << T->data << " ";  
        midTree(T->right);  
    }  
}  

// 后序遍历  
void postTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        postTree(T->left);  
        postTree(T->right);  
        cout << T->data << " ";  
    }  
}  

// 复制二叉树  
void copyTree(Birtree* T, Birtree* &NewT) {  // 使用引用以操控指针  
    if (T == NULL) {  
        NewT = NULL;  
        return;  
    } else {  
        NewT = new Birtree;  
        NewT->data = T->data;  
        copyTree(T->left, NewT->left);  
        copyTree(T->right, NewT->right);  
    }  
}  

//计算二叉树的深度
int depthtree(Birtree* T){
    int m,n;
    if(T==NULL) return 0;
    else{
        m=depthtree(T->left);
        n=depthtree(T->right);
        if(m>n) return (m+1);
        else return (n+1);
    }
}

//计算二叉树的结点总数
int nodenumbertree(Birtree* T){
    if(T==NULL) return 0;
    else{
        return nodenumbertree(T->left)+nodenumbertree(T->right)+1;
    }
}

//计算二叉树的叶子结点总数
int yezinumbertree(Birtree* T){
    if(T==NULL) return 0;
    if(T->left==NULL&&T->right==NULL){
        cout << "先序排列的叶子结点的值为：" << T->data << endl;
        return 1;
    } 
    else{
        return yezinumbertree(T->left)+yezinumbertree(T->right);
    }
}

// 释放二叉树内存  
void deleteTree(Birtree* T) {  
    if (T == NULL) {  
        return;  
    } else {  
        deleteTree(T->left);  
        deleteTree(T->right);  
        delete T;  
    }  
}  

int main() {  
    Birtree* T = NULL;  
    Birtree* newT = NULL;  
    creatBiTree(T);  

    cout << "先序遍历：";  
    preTree(T);  
    cout << endl;  

    cout << "中序遍历：";  
    midTree(T);  
    cout << endl;  

    cout << "后序遍历：";  
    postTree(T);  
    cout << endl;  

    copyTree(T, newT);  
    cout << "原树的先序遍历：";  
    preTree(T);   
    cout << endl;  
    
    cout << "复制树的先序遍历：";  
    preTree(newT);   
    cout << endl;   

    cout << "二叉树的深度：";  
    cout << depthtree (T);  
    cout << endl; 

    cout << "二叉树的总结点数：";  
    cout << nodenumbertree (T);  
    cout << endl;

    // cout << "二叉树的叶子结点总数：";  
    cout << yezinumbertree (T);  
    cout << endl;

    // 释放内存  
    deleteTree(T);  
    deleteTree(newT);  
    
    return 0;  
}
//举例;1 3 5 0 0 8 0 0 2 0 0

四、通过遍历方式反推树的结构（做题无脑秒解）

1.已知先序遍历与中序遍历，求树的形状。


## 2.已知后序遍历与中序遍历，求树的形状。

3.二叉树的前序和后序可推什么结果？


五、平衡二叉树调整(做题秒解)

1.基本特征

二叉树: 平衡二叉树是二叉树的一种，每个节点最多有两个子节点（左子节点和右子节点）。
平衡条件: 平衡二叉树要求每个节点的左右子树的高度差（平衡因子）不超过 1。这意味着：
左子树的高度与右子树的高度之差的绝对值≤1。即，平衡因子的值为 -1、0 或 1。
自动调整: 在进行插入和删除操作后，平衡二叉树能够自动调整自身的结构，保持高度平衡。这通常是通过旋转操作来实现。

2.主要优点

快速查找、插入和删除: 由于保持了平衡，操作的时间复杂度为
O(logn)，使得其在处理动态数据集时表现良好。
动态集合的表现: 适用于动态数据集合，如需要频繁插入和删除元素的场景。

3.视频讲解

# 数据结构 # c++ # c语言 # 算法 # visualstudio # visual studio code
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

大数据毕业设计选题推荐-基于大数据的农作物产量数据分析与可视化系统-Hadoop-Spark-数据可视化-BigData

avatar 魔乐社区
cover

大模型推理适配实战：手把手带你完成vLLM Ascend迁移实操

avatar 魔乐社区
cover

基于python大数据的汽车数据分析系统设计与实现

avatar 魔乐社区