首页 > 其他分享 >二叉树小结

二叉树小结

时间:2024-02-21 20:44:19浏览次数:23  
标签:pR 遍历 struct int root 二叉树 小结

 

===============================================================================================

二叉树的定义方式:

1.顺序表:

typedef struct SqTree{
    char data[maxsize];
    bool isNULL;
}SqTree;

2.链表

struct node{
    int val;
    struct node *lchild,*rchild;
    // int Ltag,Rtag;      // tag=0,指向孩子,tag=1。指向线索。线索二叉树
};

3.或者使用这种方式定义:

int Tree[35][2];

int deal(int i0,int i1,int pR){            
    if(i0>i1){
        return -1;     
    }
    int i = pos[pre[pR]];
    int Llen = i-i0; 
    int root = pR;
    Tree[root][0] = deal(i0,i-1,pR+1);
    Tree[root][1] = deal(i+1,i1,pR+Llen+1);
    return root;         
}

4.也可以定义为结构体:

struct tnode{
    int nodeid,lidx,ridx,level;
};

===============================================================================================

 树 这种数据类型在顺序存储、链式存储下的体系:

 

===================================================================================================

其他:

1. 完全二叉树用数组表示时下标一定要从1开始!!!

2. BST的中序序列是递增的。

3. 二叉树先序遍历需要借助栈,栈的入栈顺序就是先序序列、出栈顺序就是中序序列。

4.树的层次遍历和图的bfs、树和图的dfs类似(MST)

5.并查集是树的应用

6.快速排序类似树的先序遍历、归并排序类似树的后序遍历

7.回溯算法、动态规划的基础在于树的遍历

 

标签:pR,遍历,struct,int,root,二叉树,小结
From: https://www.cnblogs.com/jinziguang/p/18026177

相关文章

  • 力扣递归之 236. 二叉树的最近公共祖先
    给定一个二叉树,找到该树中两个指定节点的最近公共祖先。百度百科中最近公共祖先的定义为:“对于有根树T的两个节点p、q,最近公共祖先表示为一个节点x,满足x是p、q的祖先且x的深度尽可能大(一个节点也可以是它自己的祖先)。” 示例1:输入:root=[3,5,1,6,2,0,8,null,n......
  • leedcode 二叉树的最小深度
    自己写的:#二叉树节点的定义classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightclassSolution:defminDepth(self,root:Optional[TreeNode])->int:#......
  • leedcode 平衡二叉树
    对称二叉树走不通  201/228 个通过的测试用例classSolution:defisBalanced(self,root:Optional[TreeNode])->bool:queue=[root]ifnotroot:returnTrueifnotroot.leftandnotroot.right:returnTr......
  • (20/60)二叉搜索树的最小绝对差、二叉搜索树中的众数、二叉树的最近公共祖先
    过外婆八十寿宴,补卡二叉搜索树的最小绝对差leetcode:530.二叉搜索树的最小绝对差双指针中序遍历法思路搜索树的最小绝对差一定出现在中序遍历的相邻两个元素之间。设置前后两个指针,每次对比“历史最小”与当前node->val-pre->val的值哪个更小,进行相应更新。复杂度分析......
  • 二叉树(2)
    目录538把二叉搜索树转换为累加树538把二叉搜索树转换为累加树和平常的遍历顺序不同这题根据题意是需要取比当前节点大的所有数值的和而在二叉搜索树中,节点的大小关系是左<中<右所以自然而然地我们就得到了如下的遍历顺序:右->中->左classSolution{public:intvalue......
  • 代码随想录算法训练营第二十天 | 236. 二叉树的最近公共祖先 , 501.二叉搜索树中的众
      530.二叉搜索树的最小绝对差 已解答简单 相关标签相关企业 给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值 。差值是一个正数,其数值等于两值之差的绝对值。 示例1:输入:root=[4,2,6,1,3]输出:1示......
  • (2024.2.5-2024.2.18)C语言学习小结
    这两周主要围绕《HeadfirstC》这本书展开C语言学习,同时尝试学习DES密码算法C程序。基本内容《HeadfirstC》学习的内容基本上就是进程与通信、网络、线程这块。以下是思维导图:实践练习除了书上的一些小练习之外,我也实践写了HFC的C语言实验室2的程序,一波三折,详见C代码......
  • 「力扣」104. 二叉树的最大深度
    「力扣」104.二叉树的最大深度题目描述给定一个二叉树root,返回其最大深度。二叉树的最大深度是指从根节点到最远叶子节点的最长路径上的节点数。示例1:输入:root=[3,9,20,null,null,15,7]输出:3示例2:输入:root=[1,null,2]输出:2提示:树中节点的数量在[0,10......
  • 代码随想录算法训练营第十九天 | 98.验证二叉搜索树, 700.二叉搜索树中的搜索,617.合并
     654.最大二叉树 已解答中等 相关标签相关企业 给定一个不重复的整数数组 nums 。 最大二叉树 可以用下面的算法从 nums 递归地构建:创建一个根节点,其值为 nums 中的最大值。递归地在最大值 左边 的 子数组前缀上 构建左子树......
  • 代码随想录算法训练营第十八天 | 112. 路径总和,113. 路径总和ii ,106.从中序与后序遍
     513.找树左下角的值 已解答中等 相关标签相关企业 给定一个二叉树的 根节点 root,请找出该二叉树的 最底层最左边 节点的值。假设二叉树中至少有一个节点。 示例1:输入:root=[2,1,3]输出:1示例2:输入:[1,2,3,4,null,5,6,n......