快捷通道

QQ登录

只需要一步，快速开始

  注册地址  找回密码

数学建模社区-数学中国

留学>>
返回列表 发新帖
查看: 2466|回复: 0
打印 上一主题 下一主题

【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历

[复制链接]
字体大小: 正常 放大
杨利霞        

5273

主题

82

听众

17万

积分

  • TA的每日心情
    开心
    2021-8-11 17:59

    • 签到天数: 17 天

    [LV.4]偶尔看看III

    网络挑战赛参赛者

    网络挑战赛参赛者

    自我介绍
    本人女，毕业于内蒙古科技大学，担任文职专业，毕业专业英语。

    群组: 2018美赛大象算法课程

    群组: 2018美赛护航培训课程

    群组: 2019年 数学中国站长建

    群组: 2019年数据分析师课程

    群组: 2018年大象老师国赛优
    跳转到指定楼层
    1#
    发表于 2022-9-15 11:55 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
    + _( y8 g7 x/ g  s
    ( K- m$ e9 Z' F1 K1 T[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
    0 D6 _: h/ k* i) E[color=rgba(0, 0, 0, 0.749019607843137)]前言
    , N% R  c$ n# U* `- \0 u[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
    / x5 \- {6 e, V9 `  ^[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）/ \0 {6 V# @1 A$ L$ a
    [color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历: t& l% S( L& x' t/ j
    [color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小& n( r, q9 ?' U' _0 {4 a! |+ y) h
    [color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
    % g% Y6 V8 I  y: W[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
    ( e3 g) ^2 O8 W$ G! G[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
    ! }6 u% B3 H2 t) I[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找' s- u6 S0 ^; l7 C; d% y
    [color=rgba(0, 0, 0, 0.749019607843137)]前言
    2 L# U0 r5 Q& y- N6 H[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。; @: ^2 V6 J4 o9 u2 D
    [color=rgba(0, 0, 0, 0.749019607843137)]
    5 p' \0 k- ?1 V7 ^    & H  g% U: D; ^5 t% G1 j# U
    [color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
    8 D6 v& ]8 J4 r5 q- @* Z[color=rgba(0, 0, 0, 0.749019607843137)]0 q) `. E8 |7 w; w
    ' _$ @0 O1 \0 D- P6 l3 S8 R
    [color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：5 v' w* \" _* r: Q
    [color=rgba(0, 0, 0, 0.749019607843137)]; z8 r* j1 S" T5 m  j, x% B0 v
    0 l3 y' e. C( M
    [color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树4 k' h8 u5 R% h+ s4 O+ u4 T
    [color=rgba(0, 0, 0, 0.749019607843137)]9 ~' s$ E' |. r: k
    . }& K) y7 ]3 q) X$ X4 X
    [color=rgba(0, 0, 0, 0.749019607843137)]
    3 D8 l2 K$ V9 f( t, J  q4 v# `
    ' ^* G2 q& r+ }  A[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树+ m6 F2 b8 y/ y2 v4 c
    [color=rgba(0, 0, 0, 0.749019607843137)]
    1 Z9 m& B& h& e% Q1 f2 B    / U8 Q% v% Y1 A3 L* |4 j
    [color=rgba(0, 0, 0, 0.749019607843137)]. i6 j  I" m2 O5 C2 c/ `

    - X' G) z" u  Y[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
      v0 g" x+ z; t0 {[color=rgba(0, 0, 0, 0.749019607843137)]# I5 [; z$ Z' s8 y' v) S$ K
    1 s  d7 q9 d9 d: F# O0 s
    [color=rgba(0, 0, 0, 0.749019607843137)]  O/ m0 M! r% T1 o
    $ [6 ~7 q! w3 X& c
    [color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）( n" }6 |+ J. N
    [color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
    $ t& f: g! x. F. l! ^3 C[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
    2 i. R% V* ~& V5 r! y[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；; {# J, Y& r2 X" s6 R  R$ C; ~! d
    [color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
    : V# @; z6 q& n3 [6 F[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；. Y- L2 u7 o) j+ s; ?& M: w# Z! ~
    [color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
    8 O, D" E) K4 E3 y: S1 E4 X[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；4 `; k4 Y2 }, w, q
    [color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
    7 F; H& k7 d. _5 R6 K; x. A. ]' d[color=rgba(0, 0, 0, 0.749019607843137)]
    9 _5 y/ m. {* b% \. M
    ! R  u4 K6 v, Y, [3 b% V. S[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历" \' Q! x7 Q4 {+ Q5 P0 v
    [color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 15 y0 Y5 D% u  ?/ G
    [color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>) J$ c% z" A3 Z
    [color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>+ U' I% A" K, K4 @: q
    [color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>" z  y, [4 Y" w2 c; X
    [color=rgba(0, 0, 0, 0.749019607843137)]/ }3 A$ H: K. D

    ( m$ ~; q+ v5 W; R[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
    $ ~5 ]* @% ?' c; N" A* c; Q( Y4 C: Y; N[color=rgba(0, 0, 0, 0.749019607843137)]$ u% ?) ^* _* {  y4 U
    ; \1 [' G" Z: O# h( x% |4 i
    [color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
    , i8 K9 R- }9 m8 j! S[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode& u+ ?/ G/ f# }+ S& ~% e8 F
    [color=rgba(0, 0, 0, 0.749019607843137)]{' z& M4 b) [1 I  H8 }% L9 N  c. R
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTDataType data;
    $ x2 U( C/ r* c% m0 q. F! x9 k[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* left;4 N" R+ B  k9 a% v8 U: B
    [color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* right;" G6 o3 U) Q; W8 ~
    [color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
    3 o( D' z( `1 r" _. `[color=rgba(0, 0, 0, 0.749019607843137)]
      N8 _* o2 w3 H0 \  ?
    / m" ~  d  v+ r5 }9 t+ o[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
    9 W% p1 J+ x$ k6 e3 ]* b[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)1 l+ E' c5 y; @. m
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    ) u, U. V) a; @[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)0 k  x) b, W4 w
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    8 o6 V+ I5 @/ O6 {, ^9 U2 q) F9 ^& `[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");6 V7 }# S% S- e+ H+ X1 e. J9 O
    [color=rgba(0, 0, 0, 0.749019607843137)]                return;+ S- P8 ]; V4 z7 |+ u
    [color=rgba(0, 0, 0, 0.749019607843137)]        }; _- O6 q" m" V" M5 g0 T* T8 f
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
    2 F  b$ i- Y  T9 Y4 i) p5 c[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->left);7 `, l5 ?% o- b/ X; P2 \9 ]+ R
    [color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->right);; A. l- K. R! g* n3 o/ F9 W4 r: ^$ u% H
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    3 O/ e  q' r6 \[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
    - B! N+ H7 K3 z5 k8 N. i[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
    % o6 M* ^4 o4 j  C- R$ o[color=rgba(0, 0, 0, 0.749019607843137)]{
    * y1 j9 H! K" w4 i[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)/ J2 m. n9 d* d  e) i2 H. I
    [color=rgba(0, 0, 0, 0.749019607843137)]        {: }* W+ B. E/ r% d/ J( e3 Z
    [color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");" P+ R% F' O& e( M# t# C+ E& _
    [color=rgba(0, 0, 0, 0.749019607843137)]                return;
    7 {. `4 W+ H* a& g$ s; M[color=rgba(0, 0, 0, 0.749019607843137)]        }
    ' s) _2 c4 C! Z9 s2 g- J2 @( X[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->left);" }3 f  Y! l' u8 G
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
    # ^% @* S& c- B5 ~[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->right);) _) M# H7 P9 z; m
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    - L. P8 s7 Z* b3 @/ E4 \[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历% M4 ^$ B' a( ^2 `2 H( N
    [color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)& D+ C* M3 |5 L7 \5 h  T7 f
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    9 E# A8 g+ J; x% n; W1 V[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    * Z" }; ^* H8 U' x7 r) f6 _[color=rgba(0, 0, 0, 0.749019607843137)]        {
    2 K8 `+ h; l# e4 W! `[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");2 @" m  y3 W3 D5 U9 k; n
    [color=rgba(0, 0, 0, 0.749019607843137)]                return;
    % {/ y0 ?) N+ E[color=rgba(0, 0, 0, 0.749019607843137)]        }" ]9 U' l# V2 E+ \0 W- y9 F2 [
    [color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->left);" g( U" `* P& x, g- g+ J2 y" I
    [color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->right);+ G' ?* v7 `! A/ k7 v% ?% }7 G8 Y
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
    : K7 {, t- N& G% U/ y' S[color=rgba(0, 0, 0, 0.749019607843137)]}
    / J/ B/ j& r$ a: n9 b7 y[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构; x( }3 w+ f0 B( `, z  J
    [color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
    " a$ r+ b" r) P9 ?1 h[color=rgba(0, 0, 0, 0.749019607843137)]{
    6 H! g  K0 z( p[color=rgba(0, 0, 0, 0.749019607843137)]        //先动态开辟6个结点的空间
    + p. N! q. |  R" H' K$ s4 o6 o( c6 r[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
    . a! ~+ Z$ j) ~2 _[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n1);) k9 v; l! w* d) U) j5 T
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));' j& Y) N4 t# l+ Y! Q* c+ r
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n2);) `" ?/ m6 E( M* m9 K
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));. E) X3 }2 K5 n: m( u6 y, K0 j$ |
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n3);8 h& z8 ~7 C! x& s' m% P
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
    " b# [/ ?- g; w/ S- ]3 y[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n4);
    ) [6 E- _7 P& m( M4 E8 g[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
      j9 R  H; v% ?; j& ~7 F5 ?; Y( {[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n5);
    ) W$ N& h" V2 I; ^[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));" S( D1 u0 M3 x5 A* g  f! D6 l
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n6);
    0 O9 D! J  o; v- z- e5 p3 [[color=rgba(0, 0, 0, 0.749019607843137)]4 c' i: ]2 `& R6 b

    : p) E( T: c/ A% H1 H# c+ @& m[color=rgba(0, 0, 0, 0.749019607843137)]        n1->data = 1;; ~/ A" ]0 I) o! S
    [color=rgba(0, 0, 0, 0.749019607843137)]        n2->data = 2;+ Q# v2 I+ ^7 B, j6 N
    [color=rgba(0, 0, 0, 0.749019607843137)]        n3->data = 3;6 R' g6 a1 i- ^+ Q5 i7 F; l0 [
    [color=rgba(0, 0, 0, 0.749019607843137)]        n4->data = 4;9 `$ G' g% S' A) s, @" h
    [color=rgba(0, 0, 0, 0.749019607843137)]        n5->data = 5;
      M7 T/ w; }3 h[color=rgba(0, 0, 0, 0.749019607843137)]        n6->data = 6;5 m2 x4 n7 m' j8 K
    [color=rgba(0, 0, 0, 0.749019607843137)]
    9 A& a  ?: \5 f. v7 r    ! @# E) i7 A' P, G
    [color=rgba(0, 0, 0, 0.749019607843137)]        n1->left = n2;3 _2 I5 N1 B' {! U( d4 |  H
    [color=rgba(0, 0, 0, 0.749019607843137)]        n1->right = n4;& L8 Y3 _" d/ J7 S6 ^7 g
    [color=rgba(0, 0, 0, 0.749019607843137)]        n2->left = n3;
    " ?. h* y" \& l% y/ C/ ]1 N[color=rgba(0, 0, 0, 0.749019607843137)]        n2->right = NULL;
    # N3 e4 n, \3 w& K3 |) b[color=rgba(0, 0, 0, 0.749019607843137)]        n3->left = NULL;
    ' i! W! N9 g# B3 G6 V% g[color=rgba(0, 0, 0, 0.749019607843137)]        n3->right = NULL;
    ; y( p9 S3 z+ Z* `[color=rgba(0, 0, 0, 0.749019607843137)]        n4->left = n5;
    3 p  w: O! q  X6 g4 g[color=rgba(0, 0, 0, 0.749019607843137)]        n4->right = n6;
    0 s* b) ?1 {0 U1 \: z[color=rgba(0, 0, 0, 0.749019607843137)]        n5->left = NULL;
    : F" C& [7 \0 J: H* `+ W[color=rgba(0, 0, 0, 0.749019607843137)]        n5->right = NULL;4 J' p+ w+ d! H& T+ I3 O: m" x' K
    [color=rgba(0, 0, 0, 0.749019607843137)]        n6->left = NULL;! U0 c/ X% T5 O5 I4 w6 D/ m/ b. i
    [color=rgba(0, 0, 0, 0.749019607843137)]        n6->right = NULL;, T+ H& S- [  c0 K
    [color=rgba(0, 0, 0, 0.749019607843137)]
    2 \6 s0 @/ @( L4 i! X
    ; B' h' e( P, i- P2 z[color=rgba(0, 0, 0, 0.749019607843137)]        return n1;
    7 ?" r! t& j- p' R$ w8 r/ s[color=rgba(0, 0, 0, 0.749019607843137)]}" w4 ~) c: q; _3 `
    [color=rgba(0, 0, 0, 0.749019607843137)]4 }% a! ~2 M" L, V' I) ^- J
    3 X9 P  |0 d9 B* G9 u
    [color=rgba(0, 0, 0, 0.749019607843137)]int main()/ ~! C. Q5 o7 D
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    . o% N1 a. H" E5 b' O) n[color=rgba(0, 0, 0, 0.749019607843137)]        //先创建一个简单的二叉树结构9 s3 c6 a  }% z
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* root = CreateTree();: f' F* |" A: W; ~/ q
    [color=rgba(0, 0, 0, 0.749019607843137)]
    ! j- ]/ a1 J+ ]$ h1 ?7 {% z4 D
    1 O0 B$ e) d3 B[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树前序遍历5 [. r* u- H, j/ D  o, a! o
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树前序遍历:");. r4 r6 T- n! x9 Z  t8 y7 f: n
    [color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root);
      @9 t; e+ |2 V% w[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
    # e/ R4 x, V4 G[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树中序遍历9 e/ s  b- A+ j
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树中序序遍历:");; _* r% i0 P) I
    [color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root);
    4 o; z0 `$ T' F% Q' u9 E: v[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
    1 P( _- r; T7 q% n  N  ^[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树后序遍历
    4 e- ~' R( `4 x[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树后序遍历:");1 u/ v3 `/ s# _# M
    [color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root);
    ) E3 `* x' l2 v[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
    3 G; I( M0 M) i$ v; {! z0 |[color=rgba(0, 0, 0, 0.749019607843137)]0 J/ I! ^0 J6 |$ b  o
    ! L3 A% v9 T0 {; {/ ?3 ?8 X
    [color=rgba(0, 0, 0, 0.749019607843137)]        return 0;( U( U7 D$ `, u- m
    [color=rgba(0, 0, 0, 0.749019607843137)]}! B; y1 {6 L2 q$ S6 ~* k4 l
    [color=rgba(0, 0, 0, 0.749019607843137)]1
    7 ]. C/ E. }" Z# _( ]' _! i[color=rgba(0, 0, 0, 0.749019607843137)]2
      F1 x+ @1 D- l7 F2 N( G[color=rgba(0, 0, 0, 0.749019607843137)]31 U2 m% w9 p' f) W$ O1 M$ c
    [color=rgba(0, 0, 0, 0.749019607843137)]4( K, ~4 R! r3 ]9 k. ]
    [color=rgba(0, 0, 0, 0.749019607843137)]5
    1 M% s2 |8 h7 q4 z$ }' Q& F/ @- w[color=rgba(0, 0, 0, 0.749019607843137)]6
      w0 k% o7 x: M' Z. N[color=rgba(0, 0, 0, 0.749019607843137)]7
    8 F3 b- f: l# e6 ^[color=rgba(0, 0, 0, 0.749019607843137)]8
    2 `+ l6 {, M. _# w[color=rgba(0, 0, 0, 0.749019607843137)]9
    4 h2 O- M+ ?: c[color=rgba(0, 0, 0, 0.749019607843137)]10
    . ]: M9 ^4 k" r: b$ Y% M+ d[color=rgba(0, 0, 0, 0.749019607843137)]11
      W7 U# E/ H9 T/ @0 I[color=rgba(0, 0, 0, 0.749019607843137)]12/ u) m! R) Z" [8 S; j  C1 K
    [color=rgba(0, 0, 0, 0.749019607843137)]139 q  B5 y5 b9 L+ k5 J$ k
    [color=rgba(0, 0, 0, 0.749019607843137)]14
    " x3 Q2 A1 j* B5 x- @% x/ q; w* R8 `[color=rgba(0, 0, 0, 0.749019607843137)]15
    4 W( i! n6 h: }3 ]# m0 I8 X. `' y[color=rgba(0, 0, 0, 0.749019607843137)]16: [: ~9 n2 A5 u5 K7 `9 C$ g
    [color=rgba(0, 0, 0, 0.749019607843137)]17
    3 P2 C- x6 M2 A  H9 s# Q7 n  q8 Y1 |[color=rgba(0, 0, 0, 0.749019607843137)]18) V7 D1 g8 x: m- c3 t' S
    [color=rgba(0, 0, 0, 0.749019607843137)]19# q- ]( h) |$ r# _
    [color=rgba(0, 0, 0, 0.749019607843137)]20
    , e: B' h" m5 b. F) F6 x. _[color=rgba(0, 0, 0, 0.749019607843137)]21# n# W+ g( _5 A3 H3 d# z) B
    [color=rgba(0, 0, 0, 0.749019607843137)]22- `+ m3 g0 w7 c  ~9 V' x
    [color=rgba(0, 0, 0, 0.749019607843137)]23# Z. n' U7 C  k5 o& @* }( w
    [color=rgba(0, 0, 0, 0.749019607843137)]24/ U% o; u$ ~7 [! U: M. _
    [color=rgba(0, 0, 0, 0.749019607843137)]25
    " u, H9 S  z) p7 ?# s2 c+ E[color=rgba(0, 0, 0, 0.749019607843137)]26
    4 }0 A- x" `! f- a* I- M[color=rgba(0, 0, 0, 0.749019607843137)]27+ l2 q' q+ H$ B
    [color=rgba(0, 0, 0, 0.749019607843137)]28& h9 ^( X0 |! v8 l
    [color=rgba(0, 0, 0, 0.749019607843137)]29
    / f! \1 x5 d2 d* _[color=rgba(0, 0, 0, 0.749019607843137)]30
    ( b/ J. g/ M% x* w& F# N% _[color=rgba(0, 0, 0, 0.749019607843137)]31! k( g6 L' t1 \7 ^" d, q8 [
    [color=rgba(0, 0, 0, 0.749019607843137)]32
    1 g# h6 m6 U4 H' Y9 d6 q8 T[color=rgba(0, 0, 0, 0.749019607843137)]330 }5 b5 C! F7 V4 J
    [color=rgba(0, 0, 0, 0.749019607843137)]340 R2 k9 k# Q  d
    [color=rgba(0, 0, 0, 0.749019607843137)]35
    / y, y; G0 [! Z( d% o0 h[color=rgba(0, 0, 0, 0.749019607843137)]36
    / q) z( m2 A* A8 k0 I[color=rgba(0, 0, 0, 0.749019607843137)]37, _" N2 d3 }" }% s- Z$ z4 k$ y
    [color=rgba(0, 0, 0, 0.749019607843137)]38+ K. e1 `- Y. L2 s8 T, u
    [color=rgba(0, 0, 0, 0.749019607843137)]39/ X' t9 Z0 [& ]9 I1 w
    [color=rgba(0, 0, 0, 0.749019607843137)]40
    - b5 }* u3 h. a, L4 B[color=rgba(0, 0, 0, 0.749019607843137)]41
    ) d  o. ^" T6 `: _[color=rgba(0, 0, 0, 0.749019607843137)]42. Q+ j/ ^) @+ Y% v* N$ V4 Q9 x  \
    [color=rgba(0, 0, 0, 0.749019607843137)]43
    ( N% H% l% x6 N0 F[color=rgba(0, 0, 0, 0.749019607843137)]44
    0 S* h+ v0 p! s  {7 Z/ l[color=rgba(0, 0, 0, 0.749019607843137)]45: y5 X# _2 w8 u6 N! ^
    [color=rgba(0, 0, 0, 0.749019607843137)]468 W4 j8 F( O1 \# L; |3 ?3 |
    [color=rgba(0, 0, 0, 0.749019607843137)]47
      h0 c6 ^) @) g, f7 V% q/ h( e[color=rgba(0, 0, 0, 0.749019607843137)]48- k! P/ O* r. k4 T1 \* x1 G% b
    [color=rgba(0, 0, 0, 0.749019607843137)]49
    7 v& u; |! U$ c' u1 w[color=rgba(0, 0, 0, 0.749019607843137)]50
    $ ~) @" S: h3 X4 ~[color=rgba(0, 0, 0, 0.749019607843137)]515 V0 g$ v5 S6 {  T
    [color=rgba(0, 0, 0, 0.749019607843137)]52: L$ d  N' @5 ?8 F
    [color=rgba(0, 0, 0, 0.749019607843137)]53
    * |& L/ ?) g$ T$ N3 o3 U[color=rgba(0, 0, 0, 0.749019607843137)]54& y" J/ P1 I, [3 ?/ C
    [color=rgba(0, 0, 0, 0.749019607843137)]55
    2 S5 Y5 L- y: @2 }[color=rgba(0, 0, 0, 0.749019607843137)]569 v* G& ]  [7 Q7 f% v" t
    [color=rgba(0, 0, 0, 0.749019607843137)]57/ w! I3 s, H7 v4 {
    [color=rgba(0, 0, 0, 0.749019607843137)]58' T- W# B* H% H9 v/ F3 R! Z" X
    [color=rgba(0, 0, 0, 0.749019607843137)]59
    9 q1 U. u) s% F5 s& G1 ^. r/ ?[color=rgba(0, 0, 0, 0.749019607843137)]607 O3 I: b  P- ~- ]
    [color=rgba(0, 0, 0, 0.749019607843137)]61& l! h: E! q8 G& X, ^$ T
    [color=rgba(0, 0, 0, 0.749019607843137)]62: P9 I( Y. L: ]  V
    [color=rgba(0, 0, 0, 0.749019607843137)]63
    , y# q/ Z; M) o& D& q* v% E- b[color=rgba(0, 0, 0, 0.749019607843137)]646 `" f) N8 k, h
    [color=rgba(0, 0, 0, 0.749019607843137)]657 F5 J" b9 J! @6 |8 F6 X( I* v
    [color=rgba(0, 0, 0, 0.749019607843137)]66. X& ?6 I" ~/ S
    [color=rgba(0, 0, 0, 0.749019607843137)]67
    3 a/ w$ M) Y3 Y8 k- h. s4 k[color=rgba(0, 0, 0, 0.749019607843137)]68) p6 t4 K1 t2 |6 d. G( p
    [color=rgba(0, 0, 0, 0.749019607843137)]696 i0 S6 G, ?* ?" `0 p0 s$ t# T% r
    [color=rgba(0, 0, 0, 0.749019607843137)]70
    2 ^2 G% X+ T- _[color=rgba(0, 0, 0, 0.749019607843137)]715 ^% K5 Z3 ?1 S0 U' Q+ e
    [color=rgba(0, 0, 0, 0.749019607843137)]72
    - o4 O6 H6 |; |4 P' \[color=rgba(0, 0, 0, 0.749019607843137)]73
    4 q9 N( B3 m* @, C" j- H[color=rgba(0, 0, 0, 0.749019607843137)]74
    - k* H) E4 X3 v# C( H; C& {# d[color=rgba(0, 0, 0, 0.749019607843137)]75
    7 ^+ G5 j! }1 z1 L, X, E& g2 s9 ~[color=rgba(0, 0, 0, 0.749019607843137)]76. A) X1 q5 y3 O, T2 h+ C# _
    [color=rgba(0, 0, 0, 0.749019607843137)]77
    + E, Y( A, g% ^, K$ Z/ y[color=rgba(0, 0, 0, 0.749019607843137)]78
    4 W8 L+ Z" @5 S! {3 A+ a[color=rgba(0, 0, 0, 0.749019607843137)]79
    4 ^' p' p, m5 `[color=rgba(0, 0, 0, 0.749019607843137)]80
    9 G" s; m- C! D6 r[color=rgba(0, 0, 0, 0.749019607843137)]81
    - Q1 q9 Y0 V; P3 J- {[color=rgba(0, 0, 0, 0.749019607843137)]826 g7 N# R% k" D% y( e
    [color=rgba(0, 0, 0, 0.749019607843137)]83
    " a5 Y: `! k' b) z; N[color=rgba(0, 0, 0, 0.749019607843137)]84/ N& l' Z$ K# }7 C8 U9 E
    [color=rgba(0, 0, 0, 0.749019607843137)]85
    " f/ R1 ]: y. {1 {$ d+ ], A' s[color=rgba(0, 0, 0, 0.749019607843137)]86
    % j3 d' c$ e% u, s- ]+ ?+ S[color=rgba(0, 0, 0, 0.749019607843137)]87
    , Q. Y+ q' _5 D& N8 e: l5 f[color=rgba(0, 0, 0, 0.749019607843137)]88; s6 t0 s4 ?, S; m* [% I: z( s& n
    [color=rgba(0, 0, 0, 0.749019607843137)]89
    7 h' ]5 v) w( E9 X0 R[color=rgba(0, 0, 0, 0.749019607843137)]90
    5 m: g/ @( z& X% w[color=rgba(0, 0, 0, 0.749019607843137)]91
    6 \, a7 |% N& _/ V9 v1 Z3 e. r3 ^[color=rgba(0, 0, 0, 0.749019607843137)]92
    2 G9 S) }" X& Z( u  F2 i- {0 @[color=rgba(0, 0, 0, 0.749019607843137)]939 r+ h* L. i; V9 Q  D5 x
    [color=rgba(0, 0, 0, 0.749019607843137)]94
    0 E6 ^* _8 @. P8 @8 Q[color=rgba(0, 0, 0, 0.749019607843137)]95: b0 R" L) l! }4 O% d0 U
    [color=rgba(0, 0, 0, 0.749019607843137)]969 Y: K, G" B4 m8 o
    [color=rgba(0, 0, 0, 0.749019607843137)]97
    2 h% Y0 v0 ]- G3 O8 D6 E[color=rgba(0, 0, 0, 0.749019607843137)]98$ c$ m% s: e; G% t* k; Y* F
    [color=rgba(0, 0, 0, 0.749019607843137)]99$ |. w, f% Y) S) K1 v
    [color=rgba(0, 0, 0, 0.749019607843137)]100# q: u- u# H6 C9 `* {
    [color=rgba(0, 0, 0, 0.749019607843137)]101
    ! {6 q6 A* M" g# Q6 z[color=rgba(0, 0, 0, 0.749019607843137)]102
    " F8 |6 {" V3 x3 s! K) n% y, t% o[color=rgba(0, 0, 0, 0.749019607843137)]103( ^  n1 ^0 E- z6 A2 ^: d. J1 A
    [color=rgba(0, 0, 0, 0.749019607843137)]104$ D$ H* x0 x& Z0 n
    [color=rgba(0, 0, 0, 0.749019607843137)]105# m% T, t# q* |, U, c% [
    [color=rgba(0, 0, 0, 0.749019607843137)]106
    2 J, u+ M* y/ H3 j8 I' u- ?0 a: |& Z[color=rgba(0, 0, 0, 0.749019607843137)]107
    # K6 T9 V' q6 |0 e8 w[color=rgba(0, 0, 0, 0.749019607843137)]1088 i* ?1 E) @6 G3 c; L: i
    [color=rgba(0, 0, 0, 0.749019607843137)]109
    ) \/ P+ j: ~8 {: l[color=rgba(0, 0, 0, 0.749019607843137)]110
    $ Y4 e/ G$ W1 m0 T2 T. S( D# t[color=rgba(0, 0, 0, 0.749019607843137)]111) O+ p7 w) O7 F/ Q# N8 n
    [color=rgba(0, 0, 0, 0.749019607843137)]测试结果：& v0 w$ d/ [# S+ E/ m$ m* \
    [color=rgba(0, 0, 0, 0.749019607843137)]) o% S% _4 r4 A: E" A

    9 @. ^- R# x  P/ T[color=rgba(0, 0, 0, 0.749019607843137)]9 ~- e* q8 v- S

    : k( ?6 k3 g* k2 i5 d$ u[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小6 h2 l" P/ K& c" i4 g4 E
    [color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)4 w# y0 C8 c2 {% w6 A$ V8 S$ q
    [color=rgba(0, 0, 0, 0.749019607843137)]
    9 R: K0 c7 L- ^; X. H    * k3 F0 e- W" k- N9 E5 w3 c
    [color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
    * h; X3 T1 ~6 |8 ?) S1 S4 K$ S[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
    . V4 B) G7 j+ M: A& }4 F+ {8 ~[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
    0 R, u5 c4 Z+ I$ h* D/ r' m[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
    7 d  Y  F- W4 {0 B$ I4 @4 ^) @[color=rgba(0, 0, 0, 0.749019607843137)]//{
    1 x4 U3 W9 A* C[color=rgba(0, 0, 0, 0.749019607843137)]//        if (root == NULL)) f- I: _1 Z5 N0 J& [
    [color=rgba(0, 0, 0, 0.749019607843137)]//        {
    2 _, p+ s. }$ c, K[color=rgba(0, 0, 0, 0.749019607843137)]//                return;
    , n& ?1 Y- m! T7 v: ~4 W[color=rgba(0, 0, 0, 0.749019607843137)]//        }/ F5 g5 C4 M: a/ S2 X& U
    [color=rgba(0, 0, 0, 0.749019607843137)]//        count++;; C) D. e& w" q
    [color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->left);, A) W- w, D( w0 `# [
    [color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->right);
    5 x: }4 W2 d* e. X[color=rgba(0, 0, 0, 0.749019607843137)]//
    0 }* @9 l% W- }' i[color=rgba(0, 0, 0, 0.749019607843137)]//        return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量& U; m4 ~4 G- z% }+ q; r5 C
    [color=rgba(0, 0, 0, 0.749019607843137)]//}
    7 h! a: Y$ `3 z" @[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
    4 m; W$ x' |( d2 j9 ]7 F[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)* f2 h0 S- I5 W' l# t$ m6 B
    [color=rgba(0, 0, 0, 0.749019607843137)]{1 F; I& w6 U' U1 k/ g" A5 t* S; i
    [color=rgba(0, 0, 0, 0.749019607843137)]        return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;- N" K5 V% j/ o& W! |; t7 Y
    [color=rgba(0, 0, 0, 0.749019607843137)]}- A8 i% f; S  L! H
    [color=rgba(0, 0, 0, 0.749019607843137)]1
    & G' b& R& Z4 M! |[color=rgba(0, 0, 0, 0.749019607843137)]27 S9 z4 R& h! w0 Q  R9 F
    [color=rgba(0, 0, 0, 0.749019607843137)]3
    % k. N+ o  N( @( R[color=rgba(0, 0, 0, 0.749019607843137)]4, h: ]4 S+ [1 |3 _  Q, A+ V0 m+ y
    [color=rgba(0, 0, 0, 0.749019607843137)]5( j% f- @+ x% C4 V$ f
    [color=rgba(0, 0, 0, 0.749019607843137)]6
    6 q1 |7 Z" ]! [% r" e+ D. `0 ?2 C[color=rgba(0, 0, 0, 0.749019607843137)]7# Z  c; Z. J7 [0 B( G
    [color=rgba(0, 0, 0, 0.749019607843137)]8
    # z, A. y. t. ]! f, K- @* K[color=rgba(0, 0, 0, 0.749019607843137)]9
    8 L- b) w2 @5 a/ H6 ~  n1 v[color=rgba(0, 0, 0, 0.749019607843137)]10
    * U  [$ N6 i  ]; |[color=rgba(0, 0, 0, 0.749019607843137)]11
    , [' j6 E" E) z, @0 I! {[color=rgba(0, 0, 0, 0.749019607843137)]12
    7 Y( ?  R$ v* k[color=rgba(0, 0, 0, 0.749019607843137)]13# K; e% q* x' ]5 C8 L0 v8 W) R
    [color=rgba(0, 0, 0, 0.749019607843137)]14
    ; H1 g7 I: I, j: t: a! T& Y! H[color=rgba(0, 0, 0, 0.749019607843137)]15
    8 n5 W+ s$ |/ `[color=rgba(0, 0, 0, 0.749019607843137)]16
    & e& l$ ~$ ~& b2 v& ]4 K[color=rgba(0, 0, 0, 0.749019607843137)]17
    ) F$ N: D7 _2 A. X[color=rgba(0, 0, 0, 0.749019607843137)]18. }8 l% r' Q& C  t- n' y
    [color=rgba(0, 0, 0, 0.749019607843137)]19' Y+ [( D5 B" t+ R
    [color=rgba(0, 0, 0, 0.749019607843137)]20* J; {5 V4 E  w+ S1 l
    [color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数0 e- [0 g1 W: \2 J4 u
    [color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数- o4 s0 Q7 g; |4 E8 Y9 G. x
    [color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
    & n$ E2 A5 j& B! q/ U5 U0 s4 O[color=rgba(0, 0, 0, 0.749019607843137)]{; O( H( G7 ^! |' ]8 G5 B6 H$ U4 `
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)//首先得考虑空树的情况,0个叶子结点7 p) h& ~& A4 r+ l  I0 M
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    , e# u/ v+ u% _' |2 O[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;1 X- Z+ @  q/ c% L
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    - _; M8 k* B$ r% g[color=rgba(0, 0, 0, 0.749019607843137)]        //叶子结点的特征就是左右子树为空
    . X) B% g( a. j& M6 O' F% {' m[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->left == NULL && root->right == NULL)
    ) I  B! L1 I! U* F; ^/ x- _! h[color=rgba(0, 0, 0, 0.749019607843137)]        {
    - S$ g  H( ^9 Y" N4 h) D+ @1 \# F: T[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;
    ( w% v- N- B* Y9 v: S& @[color=rgba(0, 0, 0, 0.749019607843137)]        }: `% [# G8 F- ]$ k
    [color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLeafSize(root->left) + TreeLeafSize(root->right);: k5 V* P& Y9 A5 H( x
    [color=rgba(0, 0, 0, 0.749019607843137)]}+ p/ D' Y# O+ k0 o  F4 K8 S- g8 o
    [color=rgba(0, 0, 0, 0.749019607843137)]1
    ( y' F4 ]8 c4 o" w) \8 C[color=rgba(0, 0, 0, 0.749019607843137)]2  I9 c6 D. `$ C1 l: S. K6 w
    [color=rgba(0, 0, 0, 0.749019607843137)]3
    : I$ r. v3 ?/ z5 w0 C, s" S, v[color=rgba(0, 0, 0, 0.749019607843137)]4
    / Q, n( e' Z6 G; Q" }3 X" ~- B[color=rgba(0, 0, 0, 0.749019607843137)]5
    6 o% W# y' q! W0 H$ x! f[color=rgba(0, 0, 0, 0.749019607843137)]6
    3 x' {1 w. K+ v( b# T[color=rgba(0, 0, 0, 0.749019607843137)]7
      P/ v! T; H* X9 [6 _[color=rgba(0, 0, 0, 0.749019607843137)]8
    + P" q( r" B6 o" Y[color=rgba(0, 0, 0, 0.749019607843137)]9/ r5 K1 S. E# h) s0 \7 r8 L& H
    [color=rgba(0, 0, 0, 0.749019607843137)]10
    . l, F& k) |2 w/ \5 o[color=rgba(0, 0, 0, 0.749019607843137)]11
    3 f3 N7 I% }& b) q, ?/ {[color=rgba(0, 0, 0, 0.749019607843137)]123 }  [) H* l9 T# v) L
    [color=rgba(0, 0, 0, 0.749019607843137)]13
    3 H' S% ^, Y. p3 E) W% g[color=rgba(0, 0, 0, 0.749019607843137)]14/ u* i" f4 _  U& M
    [color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
    + E- v  N3 `5 r3 C[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root), l- B+ g9 D% Y5 x& I9 D9 B
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    7 }- T, a# h, a% S9 X0 U) R[color=rgba(0, 0, 0, 0.749019607843137)]        //空树高度为0
    . ?' K6 L) a  `# ^! ?* Z7 z, X[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL). H; r) H( }- n; d
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    ! r. E2 ]% y- W( ^6 X9 P  h[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
    " @5 o* J8 {+ t3 k[color=rgba(0, 0, 0, 0.749019607843137)]        }% ^+ h# c4 W- Q) i- c' o4 c! k2 N, e
    [color=rgba(0, 0, 0, 0.749019607843137)]        //树的高度是较高的那棵子树
    & ?5 Y. C/ o7 ?; M; N/ w7 ]9 z$ L[color=rgba(0, 0, 0, 0.749019607843137)]        int lh = TreeHeight(root->left);//左子树的高度5 e1 C8 i( F& K; V+ a. K
    [color=rgba(0, 0, 0, 0.749019607843137)]        int rh = TreeHeight(root->right);//右子树的高度0 G* c" l' o' {$ O. F1 }0 M, H
    [color=rgba(0, 0, 0, 0.749019607843137)]
    ) K# \& \. V+ k8 p" e3 R6 H+ j    # y8 K  T; E$ R+ L! f
    [color=rgba(0, 0, 0, 0.749019607843137)]        return lh > rh ? lh + 1 : rh + 1;7 o4 n  P7 _, c. z4 J0 W
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    , C: Y7 Z% s5 |( b0 X[color=rgba(0, 0, 0, 0.749019607843137)]1
    " [& s* a3 D3 n6 `" C1 T8 x[color=rgba(0, 0, 0, 0.749019607843137)]2
    / o( V3 A1 A& q' e$ k6 ^) U[color=rgba(0, 0, 0, 0.749019607843137)]3
    6 W  {! A3 A; U! X[color=rgba(0, 0, 0, 0.749019607843137)]44 |2 ~% n/ Z2 o# K3 F/ P$ M# x
    [color=rgba(0, 0, 0, 0.749019607843137)]5
    # u; Y0 a; H# G  [* i[color=rgba(0, 0, 0, 0.749019607843137)]62 e4 d5 a7 W% @5 T
    [color=rgba(0, 0, 0, 0.749019607843137)]76 c: p6 q: n. L( Y3 C+ L
    [color=rgba(0, 0, 0, 0.749019607843137)]8! ~6 I. ?- r% W, ^" J
    [color=rgba(0, 0, 0, 0.749019607843137)]9
      v! j* y8 I5 k6 ~  [3 u2 Y: d+ b[color=rgba(0, 0, 0, 0.749019607843137)]10
    0 y8 s9 q8 d4 c1 r% f6 [- U( \# x[color=rgba(0, 0, 0, 0.749019607843137)]11: z  I2 i: Q% A9 L1 L6 e
    [color=rgba(0, 0, 0, 0.749019607843137)]126 L( i: Y4 t  c
    [color=rgba(0, 0, 0, 0.749019607843137)]13/ \7 h( a; X7 r( ]
    [color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数/ n" w" a$ h5 [$ z! }  I/ k$ C
    [color=rgba(0, 0, 0, 0.749019607843137)]! w/ Y" `2 E/ x  r
    - k9 E4 d" d9 a
    [color=rgba(0, 0, 0, 0.749019607843137)]
    $ ?: a: R* X1 z# B7 M/ A+ ]9 y
    7 C6 ?" J: w; o) y" d1 {- a[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
    # c4 C! {0 p- y4 o[color=rgba(0, 0, 0, 0.749019607843137)]
    ' L& |4 z: l; P* c    8 F7 z% l2 a9 \) k7 L# Q( }
    [color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
    9 P- Q! {# z/ h# K0 N[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)& n$ ?0 p. u9 d! z
    [color=rgba(0, 0, 0, 0.749019607843137)]{+ I3 X1 M6 n6 O7 W1 P7 [6 e: d
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(K > 0);
    + M" F2 O( l) O$ |7 j' \! g. A[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    $ i( N6 i1 j) E+ B- L- E[color=rgba(0, 0, 0, 0.749019607843137)]        {- W3 }- W' m* d4 K% m% Z. O
    [color=rgba(0, 0, 0, 0.749019607843137)]                return 0;, J: W  _8 f( O
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    7 S& w2 Z1 {! I; X# C[color=rgba(0, 0, 0, 0.749019607843137)]        //如果是第一层(递归出口): U3 q0 G2 i9 L6 I3 O" h3 v
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (K == 1)
    ( @: B' X+ J, p3 w% {[color=rgba(0, 0, 0, 0.749019607843137)]        {0 a& u0 |4 L9 g  u# e% F' f0 Q
    [color=rgba(0, 0, 0, 0.749019607843137)]                return 1;) e# o8 \; a- y+ f  s7 V2 N( }
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    2 A5 R( r; D0 W* N' E/ u[color=rgba(0, 0, 0, 0.749019607843137)]        //转换成子树的第K-1层, C# J$ q2 W+ X/ o% b$ s
    [color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);$ m  v6 v& l/ X9 g8 f
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    & h4 s; _( {; f! e- y[color=rgba(0, 0, 0, 0.749019607843137)]1
    8 C& J! Q% r" p- }' n7 {$ C[color=rgba(0, 0, 0, 0.749019607843137)]2
    : @% k$ L7 |2 g/ h. |2 [[color=rgba(0, 0, 0, 0.749019607843137)]3/ k" Q3 i) N  ^! `, E( ]
    [color=rgba(0, 0, 0, 0.749019607843137)]4
    & N! |0 T0 x& E* r8 U  i[color=rgba(0, 0, 0, 0.749019607843137)]58 u! `& t: i0 Y, q4 p5 ?0 O
    [color=rgba(0, 0, 0, 0.749019607843137)]6
    3 D+ i/ R% y( h  B5 G# D[color=rgba(0, 0, 0, 0.749019607843137)]7- ?/ n( R2 y& w. D3 E3 R8 x7 v) X
    [color=rgba(0, 0, 0, 0.749019607843137)]8
    0 V- b8 f. `) N. H9 ][color=rgba(0, 0, 0, 0.749019607843137)]99 N8 n- x1 q0 k* k) f) {. s6 t
    [color=rgba(0, 0, 0, 0.749019607843137)]10# ^  D9 a8 G- s; Z
    [color=rgba(0, 0, 0, 0.749019607843137)]118 k" B0 X, L" r+ N
    [color=rgba(0, 0, 0, 0.749019607843137)]12
    - e7 W0 s9 f( F[color=rgba(0, 0, 0, 0.749019607843137)]139 F5 O; H/ ~6 y
    [color=rgba(0, 0, 0, 0.749019607843137)]149 }3 [, ^' @2 Q
    [color=rgba(0, 0, 0, 0.749019607843137)]15% r: e9 w9 r# s- X% b% F
    [color=rgba(0, 0, 0, 0.749019607843137)]16
    0 O, @, z  p; p* u% N( h$ m[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
    & L/ u& c7 q) J+ O[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
      C" U  L$ s' m; \+ i$ V* h# D  s  \[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
    . k! i. i9 C5 m[color=rgba(0, 0, 0, 0.749019607843137)]{7 w+ k/ n: ~' y  m. M
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    & B" _/ B+ R6 V. i[color=rgba(0, 0, 0, 0.749019607843137)]        {
    : _% f! \; @6 L[color=rgba(0, 0, 0, 0.749019607843137)]                return NULL;$ t6 c7 u: W* A8 W
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    * |% m& _& i* h( m6 F[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->data == data)  R! a3 g  a, E' n  J7 U% u$ d& k
    [color=rgba(0, 0, 0, 0.749019607843137)]        {8 p$ u3 f" [" Q/ u+ G
    [color=rgba(0, 0, 0, 0.749019607843137)]                return root;$ p$ c( l" E! ]
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    * \" p( S+ D6 N7 W[color=rgba(0, 0, 0, 0.749019607843137)]        //先查找左子树: [" ^/ ^8 a7 q' O& e
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* lret = TreeFind(root->left, data);
    * H+ [8 g3 C6 f[color=rgba(0, 0, 0, 0.749019607843137)]        if (lret)4 s2 @& H$ V+ ^! U
    [color=rgba(0, 0, 0, 0.749019607843137)]                return lret;, I9 D7 y& E8 p
    [color=rgba(0, 0, 0, 0.749019607843137)]        //再查找右子树" ?; ]( T, I9 c8 A6 j9 f
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* rret = TreeFind(root->right, data);
    * s" y1 A2 _6 ]+ g& R1 j0 h1 e[color=rgba(0, 0, 0, 0.749019607843137)]        if (rret)5 r8 m4 [% d5 a1 M. z- O
    [color=rgba(0, 0, 0, 0.749019607843137)]                return rret;
    1 Z" e: Y9 R% H( j8 y; N7 X& \[color=rgba(0, 0, 0, 0.749019607843137)]        return NULL;
    ) o2 r  M8 ^8 A9 B7 w[color=rgba(0, 0, 0, 0.749019607843137)]}$ _/ \/ q6 u' `+ \7 h+ f
    [color=rgba(0, 0, 0, 0.749019607843137)]————————————————
    ; d! v% m8 p5 ?[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。; O( R: J4 ^0 y) g* C
    [color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212$ W  z5 ^& n; ^  v) J! k* w

    - |) P- _5 F! m  }9 v% k) E' j0 Q
    [color=rgba(0, 0, 0, 0.75)]; ~3 ^; p/ Y) B% k6 t
    + W6 e- U) w- f* K, Y* e' B
    ! O7 P6 V7 z! c- |
    ! x2 C5 q4 U& A7 m. H- _
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    回复

    使用道具 举报

    返回列表 发新帖
    高级模式
    B Color Image Link Quote Code Smilies
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩

    • 电话咨询

    • 04714969085

    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问：王兆丰

    GMT+8, 2026-4-21 21:54 , Processed in 0.482656 second(s), 51 queries .

    回顶部