QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 2501|回复: 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
    【数据结构】二叉树的遍历:前序,中序,后序的递归结构遍历9 l  h, ?) Q6 l; ^" A7 Z0 ?$ f4 b' K

    7 ], N/ ?) Q0 k8 r1 {: _. ^[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
    / n6 R9 I5 h& M- W& k% I[color=rgba(0, 0, 0, 0.749019607843137)]前言7 `- t7 p0 @: Q+ Y& q
    [color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
    + }4 W$ f# |; O  H, f- F[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数(代码实现). ]3 w6 f0 _5 e- H" q8 f2 @
    [color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
    / ]: E+ D7 o- t- J; D, l[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
    8 E: N$ j. e  k! J7 k7 j4 l[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
    3 I8 x1 C$ O# b7 f+ z[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度9 B: f! G7 U9 t7 P7 b5 b0 G) y
    [color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数3 A7 H2 V( f2 W: C
    [color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
    2 ]% h6 }4 J# z[color=rgba(0, 0, 0, 0.749019607843137)]前言
    % |* E$ h7 _  `2 d* e. Y[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前,我们需要先创建一棵二叉树,然后才能学习其相关的基本操作,由于现在我们对二叉树结构的掌握还在初阶部分,为了降低大家的学习成本,我们先手动快速创建一棵简单的二叉树,快速进入二叉树的操作学习,这个方法在我们调试程序代码的时候,也非常适用。等二叉树结构了解的差不多时,我们再继续研究二叉树真正的创建方式。4 m/ Y+ C/ R- ^
    [color=rgba(0, 0, 0, 0.749019607843137)]
    : f7 V2 |0 |, t2 g4 {: I" X

    # q3 S6 E6 V: m8 u/ I[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
    + k1 g$ n6 D2 \4 x2 l5 E[color=rgba(0, 0, 0, 0.749019607843137)]9 G5 i7 u5 S6 F/ G. |# T

    ) ~, f' u% l+ }/ T: s* ?8 a[color=rgba(0, 0, 0, 0.749019607843137)]按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历访问顺序:' s8 J$ m+ u3 d; r0 |$ A
    [color=rgba(0, 0, 0, 0.749019607843137)]
    : }7 t: O  U# p1 e2 U+ Y" `
    0 W/ _6 C& E  R: S
    [color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历(先序,先根):根——左子树——右子树
      o9 q$ I$ N" U' J: x[color=rgba(0, 0, 0, 0.749019607843137)]6 }2 ^% s; @3 L5 L) L0 f" D8 C
    + X, P1 b$ d& q1 c
    [color=rgba(0, 0, 0, 0.749019607843137)]8 s9 m7 Y; S4 V# Q9 X
    ) w( z# ~) A6 Z: a" y# ]
    [color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历(中根):左子树——根——右子树' R' }6 w. m( f. a6 J0 U4 v+ ^
    [color=rgba(0, 0, 0, 0.749019607843137)]
    8 q, O. d4 d9 X5 u9 g

    + y" [, q; u5 {6 _9 H* J1 B2 i. c4 P[color=rgba(0, 0, 0, 0.749019607843137)]
    : _5 c0 p+ {& W- p5 D* \1 v

    % e8 \, U$ B+ f) {$ S" A. I  ^[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历(后根):左子树——右子树——根
      v% K- U7 Q- l1 e[color=rgba(0, 0, 0, 0.749019607843137)]3 t. a  y$ s, w% g! @
    : i! A( W$ C2 N4 s# I
    [color=rgba(0, 0, 0, 0.749019607843137)]; Z$ ^2 W3 Z/ X3 [3 [2 |( T0 d2 h8 l
    , L' L" x$ W0 f" N: V( ]6 R% X3 E/ N( z
    [color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数(代码实现)
    & X6 Q$ B" y6 e7 I[color=rgba(0, 0, 0, 0.749019607843137)]思路:分而治之' k; }/ [9 O2 N1 q% h6 Q- m
    [color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树,并赋予数据;/ h( g. V; V$ H; r, @
    [color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式,分别实现前序/中序/后序遍历这棵二叉树;+ ^5 E9 C. f1 B( h/ t
    [color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小(利用递归);
    . i2 j4 W5 x6 G) ]  [[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数(利用递归);' a) x3 J2 C+ U, h: |
    [color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度(利用递归);$ p7 K. \  y# ]
    [color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数(利用递归);
    ; V: N$ Q. y. Q[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数(利用递归)。
    6 K  |: n* ~+ |9 F/ t[color=rgba(0, 0, 0, 0.749019607843137)]
    6 ]4 r% |# ]( Z$ o/ |; L# @$ t8 e
    * \  |) `; O2 s6 r
    [color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
    6 h: L0 S4 Q: d! _4 }[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1: @% v% ~$ C0 A  O; w: D
    [color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
    9 D6 R, F: N' `" {" E5 G, X[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>5 g9 l* @1 u$ A' N
    [color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
    % a, t1 |' p0 H4 U+ \( Q$ ?[color=rgba(0, 0, 0, 0.749019607843137)]! H9 P! h, c8 D$ N- y- J$ C9 ~/ m

    : m8 l5 d" d: K/ b) E1 _( h[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;* W# {& j, X: m  f+ R
    [color=rgba(0, 0, 0, 0.749019607843137)]
    5 A1 ]* d8 Q/ G% K! [% H1 E3 k" Q% H
      M2 `7 n  f+ a4 T# {" o2 l* [
    [color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
    8 J, R+ ~% y2 L- O; `9 g4 {2 }[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
    ! g5 ^/ \# O( ?: L[color=rgba(0, 0, 0, 0.749019607843137)]{
    " H6 U6 @0 f1 W9 j[color=rgba(0, 0, 0, 0.749019607843137)]        BTDataType data;: y; v7 G1 X. d: h/ ~
    [color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* left;
    % f! h  I5 }7 K; u# T[color=rgba(0, 0, 0, 0.749019607843137)]        struct BinaryTreeNode* right;" Z9 W; \- E# Z% V9 t
    [color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
    $ ]- a. @, |. i# o0 W. {( W[color=rgba(0, 0, 0, 0.749019607843137)]
    ) U/ p5 {8 b6 t3 ~0 b4 L+ {

    ! T/ H6 N9 l0 a3 [* l! n$ X$ s[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
      [. y: C0 K6 x) W: N/ @[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
    $ E; M9 o# c! H8 i8 v# I[color=rgba(0, 0, 0, 0.749019607843137)]{
    - `5 y( y, V5 j[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    4 n5 f7 o/ A8 o* V  U[color=rgba(0, 0, 0, 0.749019607843137)]        {; |. Z/ N* c# ^7 [9 c2 e) @5 b
    [color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");
    ( c) q7 K( C) f4 D# M( @[color=rgba(0, 0, 0, 0.749019607843137)]                return;8 ~6 K1 L' N  u' |# @5 `
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    0 p: v6 b; e& S6 z9 ?/ C[color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
    ; M3 c/ P  o# o, i9 |9 Q, ]# d[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->left);  V2 X3 R. h% s
    [color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root->right);& C$ K$ M! |, j: n$ c6 J
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    " [$ g: n1 r/ U[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历% y) {$ q. b, m1 N3 a5 J( k% y+ H
    [color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)* P  }! b! o  W
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    , R3 |4 N4 u+ s: Z6 \[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)+ C8 y1 D2 `9 Y7 _, `% n* ?
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    0 l& ?6 A) ]4 T! Y% |  T[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");( d; X( `$ x, J1 X. _9 s
    [color=rgba(0, 0, 0, 0.749019607843137)]                return;: b, ~4 c; V/ B
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    # x6 z7 L5 n6 ]# L4 c% h0 f; B1 y[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->left);0 v, \! ?1 E8 k& g: @0 |7 g9 H
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);, y1 O$ n. {8 }& M
    [color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root->right);
    1 w  o% P' b6 J( H[color=rgba(0, 0, 0, 0.749019607843137)]}8 l# W3 O. [8 C
    [color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
    3 e3 q. [+ Z9 ^7 Y# B[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)) a% }6 A( c' {5 X
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    $ a7 ], n$ O( ^+ d, h% d( }[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    ! J  @- [! I2 j3 M/ y[color=rgba(0, 0, 0, 0.749019607843137)]        {
    # P+ Y! @: w  A7 E7 i[color=rgba(0, 0, 0, 0.749019607843137)]                printf("NULL ");9 F  ~3 _2 ?% ^! i1 l+ j4 X7 D, B
    [color=rgba(0, 0, 0, 0.749019607843137)]                return;
    ( S4 b: }% c, w! Z; M7 w[color=rgba(0, 0, 0, 0.749019607843137)]        }
    1 B: g+ F$ W5 \! l; l2 N! G[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->left);0 t' E2 Z, }7 B& |& j" B1 h7 ^
    [color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root->right);$ c# D# m/ Q4 M! k+ j
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("%d ", root->data);
    ; F/ O) i0 p$ h( b; I[color=rgba(0, 0, 0, 0.749019607843137)]}
    6 Z# t$ T5 v: `+ a8 C+ T. i[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构2 Z3 z# _# d, }' Q/ R( y
    [color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()7 z0 R: P8 F+ G( n, B
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    ; p% X4 M2 l0 D6 I' a) ~4 X7 v[color=rgba(0, 0, 0, 0.749019607843137)]        //先动态开辟6个结点的空间8 l# D) N3 s9 ~6 H
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));+ ]% Q& w$ p# L/ }2 N
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n1);
    / ?9 `6 x) }( ~$ G) \2 j[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));$ p1 r; T! q( Q! {# f
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n2);
    / E! H& K, x0 o3 s* G' E7 \( K[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
    $ D- I8 ?" \3 p6 C; V+ ?+ Z[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n3);
    ! K8 P& h7 s* T; R' u5 k0 F[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));0 ^/ b$ z2 i* l# m1 X; @) H
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n4);
    7 w- e) r8 O6 e- u) b) {[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
    4 V" J% s! V. t+ [[color=rgba(0, 0, 0, 0.749019607843137)]        assert(n5);
    4 C# |; N: {% X/ ]( A% A5 |[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));& ^( S; L7 U- S  n
    [color=rgba(0, 0, 0, 0.749019607843137)]        assert(n6);7 M9 |& L7 n" L% ?% ?
    [color=rgba(0, 0, 0, 0.749019607843137)]# z& C' K& `* j7 t$ g5 q

    . w) D, Z* Q2 u+ \; @[color=rgba(0, 0, 0, 0.749019607843137)]        n1->data = 1;( U% d- N. p* X, J' I8 f
    [color=rgba(0, 0, 0, 0.749019607843137)]        n2->data = 2;
    " C/ J. J# d# b$ F# u& N[color=rgba(0, 0, 0, 0.749019607843137)]        n3->data = 3;" R; F, I$ h: f, P  Q
    [color=rgba(0, 0, 0, 0.749019607843137)]        n4->data = 4;
    : \2 o! i* V: r& y[color=rgba(0, 0, 0, 0.749019607843137)]        n5->data = 5;: K; E4 B3 p) r6 |0 ^; o! l
    [color=rgba(0, 0, 0, 0.749019607843137)]        n6->data = 6;
    0 t3 |1 h0 e, M[color=rgba(0, 0, 0, 0.749019607843137)]' J* `6 e1 Q# n3 T7 h$ F! M

    ( `; n3 U. _1 D9 W( G[color=rgba(0, 0, 0, 0.749019607843137)]        n1->left = n2;& L# L+ y" A' ~# [& a
    [color=rgba(0, 0, 0, 0.749019607843137)]        n1->right = n4;
    # D* U. u* t8 k' w, J8 F[color=rgba(0, 0, 0, 0.749019607843137)]        n2->left = n3;9 {+ h5 K# i2 X1 B' V) t! e9 b
    [color=rgba(0, 0, 0, 0.749019607843137)]        n2->right = NULL;
    , [% o3 W% w+ i. {, G[color=rgba(0, 0, 0, 0.749019607843137)]        n3->left = NULL;
    ; R% J9 J% L1 f. w[color=rgba(0, 0, 0, 0.749019607843137)]        n3->right = NULL;
    * _# |$ }) M2 R# Q# ?[color=rgba(0, 0, 0, 0.749019607843137)]        n4->left = n5;
    4 l  ]9 l5 r9 I/ |8 z7 _+ @[color=rgba(0, 0, 0, 0.749019607843137)]        n4->right = n6;' F5 X7 H, O! d" I* Q+ P0 ?
    [color=rgba(0, 0, 0, 0.749019607843137)]        n5->left = NULL;
    5 R' `# h3 C; W$ S# |6 a[color=rgba(0, 0, 0, 0.749019607843137)]        n5->right = NULL;1 F1 V- M2 z7 p3 T, ^0 X
    [color=rgba(0, 0, 0, 0.749019607843137)]        n6->left = NULL;
    , A5 V5 Z* C* I' X2 Y4 C[color=rgba(0, 0, 0, 0.749019607843137)]        n6->right = NULL;
    2 ?2 K& r! X$ R( H[color=rgba(0, 0, 0, 0.749019607843137)]
    ' z: `: r1 P4 z" V

    ' a; y/ I! y$ D# W7 ]. O[color=rgba(0, 0, 0, 0.749019607843137)]        return n1;
    # @$ r' S4 d3 \5 {[color=rgba(0, 0, 0, 0.749019607843137)]}& [! Q: m3 q5 N; \
    [color=rgba(0, 0, 0, 0.749019607843137)]
    8 _& J, @: D  z" T2 I. d% Z

    % @0 [8 ~( c4 L' N# b# u+ P: x; g[color=rgba(0, 0, 0, 0.749019607843137)]int main()
    6 p; D2 ~: Y9 Z! V[color=rgba(0, 0, 0, 0.749019607843137)]{% f$ l  V# B3 M' E% c( ~
    [color=rgba(0, 0, 0, 0.749019607843137)]        //先创建一个简单的二叉树结构
    0 A! V+ X, Y* v2 g9 g8 C- }[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* root = CreateTree();" F) \. H! y/ r) m/ j
    [color=rgba(0, 0, 0, 0.749019607843137)]
    / s, N% |" O" d2 q! ~' E

    0 s! o- b4 Q+ G( D[color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树前序遍历
    6 j- y: ~& ]8 }6 n3 J[color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树前序遍历:");
    $ h0 E( {5 m" A2 ?: S[color=rgba(0, 0, 0, 0.749019607843137)]        PreOrder(root);$ ^: H% u3 e3 T3 B6 K4 B# r  _
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");# _$ K- e- x$ ^6 O
    [color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树中序遍历" W3 c) R; B1 \
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树中序序遍历:");
    ) s; X) P. y" r6 {: l3 o1 T( {* |[color=rgba(0, 0, 0, 0.749019607843137)]        InOrder(root);
    9 b( Y% h1 z  M[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");, A& W& N3 X1 |
    [color=rgba(0, 0, 0, 0.749019607843137)]        //二叉树后序遍历* X$ a4 c( D" b7 p, B
    [color=rgba(0, 0, 0, 0.749019607843137)]        printf("二叉树后序遍历:");
    8 E) H3 ?% N+ q" q0 e( d[color=rgba(0, 0, 0, 0.749019607843137)]        PostOrder(root);
    * k( U% M: o. c7 p8 [5 J[color=rgba(0, 0, 0, 0.749019607843137)]        printf("\n");
    , \- K' C' S1 z0 T; e3 \: U  N! x[color=rgba(0, 0, 0, 0.749019607843137)]
    , }( T8 W8 L$ H2 u
    ' y2 e2 b/ k, x5 Y+ o. {# z& D5 S
    [color=rgba(0, 0, 0, 0.749019607843137)]        return 0;3 d0 w* d* A' p/ U. D0 E
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    6 X7 x8 _8 L- Q1 N1 _! ~* a: @$ z[color=rgba(0, 0, 0, 0.749019607843137)]1
    ! I# K, `: \0 t# k& @0 K6 @[color=rgba(0, 0, 0, 0.749019607843137)]2" L+ D- Y: X, N. Y0 k) [
    [color=rgba(0, 0, 0, 0.749019607843137)]3
    " h9 P) z5 S9 R) {$ S: G[color=rgba(0, 0, 0, 0.749019607843137)]4
    ' Y6 Y  \9 q$ p3 P  D- a8 [- f  |+ `[color=rgba(0, 0, 0, 0.749019607843137)]5+ l$ _; I6 Y$ I" ~% B5 p3 ~; W& C7 {
    [color=rgba(0, 0, 0, 0.749019607843137)]6
    ' f) C$ Y- O8 k- w6 ^[color=rgba(0, 0, 0, 0.749019607843137)]7
    : g8 k0 K& w& k( d6 n3 m[color=rgba(0, 0, 0, 0.749019607843137)]8
    $ }6 o# C( G" ^[color=rgba(0, 0, 0, 0.749019607843137)]9
    ) h- x: G6 y, Q! H+ k[color=rgba(0, 0, 0, 0.749019607843137)]10
    5 Y$ X' |0 \" B" [! q3 Q[color=rgba(0, 0, 0, 0.749019607843137)]11
    4 [; g4 K* ^/ j6 O; o+ C1 G[color=rgba(0, 0, 0, 0.749019607843137)]12
    7 c! b7 M  m7 J) K$ D1 \[color=rgba(0, 0, 0, 0.749019607843137)]13
    , n) T. E9 x6 ~/ ^$ A[color=rgba(0, 0, 0, 0.749019607843137)]14
    " ?3 ^" ]1 r6 g( q8 D1 I: l( x[color=rgba(0, 0, 0, 0.749019607843137)]155 p6 `8 y) }3 o. ~
    [color=rgba(0, 0, 0, 0.749019607843137)]16& U) l. P0 t( i/ i# z1 ]2 k2 V
    [color=rgba(0, 0, 0, 0.749019607843137)]175 X; ~" w8 f- c0 m+ H9 c# i
    [color=rgba(0, 0, 0, 0.749019607843137)]18' q9 ~0 I' j3 B: k. t2 @
    [color=rgba(0, 0, 0, 0.749019607843137)]19
    . v+ O% ]  q. ^/ ?, y[color=rgba(0, 0, 0, 0.749019607843137)]20
    / j, g3 k1 V  L/ N[color=rgba(0, 0, 0, 0.749019607843137)]21
    4 {" n8 Z! \1 B: F[color=rgba(0, 0, 0, 0.749019607843137)]222 S/ O5 x( a6 X& o4 N  ?- Z
    [color=rgba(0, 0, 0, 0.749019607843137)]23
    , q1 B/ ^1 O( I9 e% i0 h8 z[color=rgba(0, 0, 0, 0.749019607843137)]24
    6 H. h7 U- Z+ G[color=rgba(0, 0, 0, 0.749019607843137)]25
    # C  j! q  S; i$ i- }[color=rgba(0, 0, 0, 0.749019607843137)]26
    $ O. t/ F4 l! n8 b0 K[color=rgba(0, 0, 0, 0.749019607843137)]27
    2 Y) Z3 X' g; M5 b5 }[color=rgba(0, 0, 0, 0.749019607843137)]284 z+ {, Q" K  p6 ~# T
    [color=rgba(0, 0, 0, 0.749019607843137)]29
    9 t7 a. i& X: Y" X/ ?& A9 O[color=rgba(0, 0, 0, 0.749019607843137)]30
    ' b& f3 A9 F9 @) G) ^[color=rgba(0, 0, 0, 0.749019607843137)]31
    . o" c$ h0 z3 u" Y& ^  v[color=rgba(0, 0, 0, 0.749019607843137)]327 H9 A  `) Z( X, F
    [color=rgba(0, 0, 0, 0.749019607843137)]332 ?5 f- N4 L( y0 v$ _, ~
    [color=rgba(0, 0, 0, 0.749019607843137)]341 J" r8 H: {5 m, A: W7 a' v
    [color=rgba(0, 0, 0, 0.749019607843137)]351 r) z9 ?; l9 t; Q
    [color=rgba(0, 0, 0, 0.749019607843137)]36  K% ^5 q% t. _( w  ]  P$ g
    [color=rgba(0, 0, 0, 0.749019607843137)]37
    # N. _& C4 C1 V7 E7 u! b[color=rgba(0, 0, 0, 0.749019607843137)]38
    - K; u9 O7 Q. h" Q) P$ L4 C; |# ^) R1 W[color=rgba(0, 0, 0, 0.749019607843137)]39
    3 H: l* d; r& V  ^$ k[color=rgba(0, 0, 0, 0.749019607843137)]40* I" y9 k; v6 y2 {' Z& t7 t
    [color=rgba(0, 0, 0, 0.749019607843137)]41' i4 J4 }' c9 I: k
    [color=rgba(0, 0, 0, 0.749019607843137)]426 s+ ], q0 N$ b3 V5 K6 L/ @- o
    [color=rgba(0, 0, 0, 0.749019607843137)]438 G( l: V; U" Y. F) h* O( y8 U" Z
    [color=rgba(0, 0, 0, 0.749019607843137)]44
    , G- ]( _. u, y" ~% d[color=rgba(0, 0, 0, 0.749019607843137)]45
    4 C9 \8 q" Z( L3 L% ~/ j[color=rgba(0, 0, 0, 0.749019607843137)]46
    ' ?* v% E1 s+ u) h9 ?" ][color=rgba(0, 0, 0, 0.749019607843137)]47. m1 h6 K0 R" e% l& W  Z% [' R
    [color=rgba(0, 0, 0, 0.749019607843137)]48
    " R0 K- C; _3 S) q$ M  W0 _[color=rgba(0, 0, 0, 0.749019607843137)]49, W. w9 O/ l' ?$ i) E
    [color=rgba(0, 0, 0, 0.749019607843137)]50
    * b8 l: F' g# G  z3 T" g( C+ w/ y[color=rgba(0, 0, 0, 0.749019607843137)]51
    % I2 ^! v& K; v: S2 q) C  |/ B[color=rgba(0, 0, 0, 0.749019607843137)]52
    0 O4 |/ R9 ^# |( m) [/ c[color=rgba(0, 0, 0, 0.749019607843137)]53
    $ p" z# _' x* x/ ~0 b' ?9 }[color=rgba(0, 0, 0, 0.749019607843137)]54
    , i8 A& ~1 n3 D' V% N! l[color=rgba(0, 0, 0, 0.749019607843137)]555 K# a% O: Y* ~$ k) Y
    [color=rgba(0, 0, 0, 0.749019607843137)]56
    % \, x/ [. I  W  f) ?; N[color=rgba(0, 0, 0, 0.749019607843137)]57/ D! g- }3 n* V; N& F* Z
    [color=rgba(0, 0, 0, 0.749019607843137)]583 M. \& F& r" y4 p4 r
    [color=rgba(0, 0, 0, 0.749019607843137)]59$ O7 S- h  e. Y8 e3 Z+ O+ Z" a6 G/ s
    [color=rgba(0, 0, 0, 0.749019607843137)]60% T$ t( t- V0 C1 w. c8 ~# \7 d& b% z
    [color=rgba(0, 0, 0, 0.749019607843137)]614 P8 p: F! E# M1 f2 c
    [color=rgba(0, 0, 0, 0.749019607843137)]62
    + m. z* t8 w6 H, n( m. \[color=rgba(0, 0, 0, 0.749019607843137)]63
    , B) e* S: G# I, \7 V[color=rgba(0, 0, 0, 0.749019607843137)]642 k- n8 Z& s' o; h0 V
    [color=rgba(0, 0, 0, 0.749019607843137)]65/ H* n' n% t/ m2 [+ |( Y, y
    [color=rgba(0, 0, 0, 0.749019607843137)]66
    2 E7 r1 F$ ^# J# [[color=rgba(0, 0, 0, 0.749019607843137)]67
    # d3 U& L; V  e- m" C6 i4 Y[color=rgba(0, 0, 0, 0.749019607843137)]68
    3 T! n% A4 g; n( j# `: m[color=rgba(0, 0, 0, 0.749019607843137)]697 \9 r4 `& d! f) t  U( p, @+ T
    [color=rgba(0, 0, 0, 0.749019607843137)]70
    & E: y4 R$ i: p; u- `, w4 t[color=rgba(0, 0, 0, 0.749019607843137)]712 b: ]4 p, V0 A# `
    [color=rgba(0, 0, 0, 0.749019607843137)]72
    " k& u. K/ o) g2 i[color=rgba(0, 0, 0, 0.749019607843137)]73
    5 r- c0 s& A' n. X4 B[color=rgba(0, 0, 0, 0.749019607843137)]74
    ! s2 n0 E, f7 y" }; H5 j) x[color=rgba(0, 0, 0, 0.749019607843137)]75- b1 e' @0 [! U' C
    [color=rgba(0, 0, 0, 0.749019607843137)]76
    7 U1 @7 `6 T. s% V# \! ^[color=rgba(0, 0, 0, 0.749019607843137)]77/ w  T3 e; H) q) H0 g2 V. T
    [color=rgba(0, 0, 0, 0.749019607843137)]78( a+ }, \: p1 z& `/ v( u
    [color=rgba(0, 0, 0, 0.749019607843137)]790 R" F& e3 [/ L# u& l2 P* e
    [color=rgba(0, 0, 0, 0.749019607843137)]80+ f, d. ^! L/ g9 Y' V% E
    [color=rgba(0, 0, 0, 0.749019607843137)]814 z7 o& j1 x" w) c; y
    [color=rgba(0, 0, 0, 0.749019607843137)]82
    5 K9 @& d, J: C/ t8 C2 I[color=rgba(0, 0, 0, 0.749019607843137)]839 f/ v$ Z5 @" ?' u
    [color=rgba(0, 0, 0, 0.749019607843137)]84
    " o8 {+ d9 G" f" Z* X[color=rgba(0, 0, 0, 0.749019607843137)]85
    - C7 C" s- ^- \# a" r: R[color=rgba(0, 0, 0, 0.749019607843137)]86  \6 v" Q9 X0 U: O$ C. c8 }3 u
    [color=rgba(0, 0, 0, 0.749019607843137)]87
    6 ^: \' k* \6 F! T[color=rgba(0, 0, 0, 0.749019607843137)]884 J7 V! m  ^! Q) }
    [color=rgba(0, 0, 0, 0.749019607843137)]895 r! t* W& J; A- Q7 N' j+ ?
    [color=rgba(0, 0, 0, 0.749019607843137)]900 j* Y! F' e: T# `! F) Z
    [color=rgba(0, 0, 0, 0.749019607843137)]91
    ' c  s; |( p+ j) @6 c. ?[color=rgba(0, 0, 0, 0.749019607843137)]92
    * F# T6 |) l& D; e[color=rgba(0, 0, 0, 0.749019607843137)]93
      Y' T! R! D2 }! A6 ~  v" u[color=rgba(0, 0, 0, 0.749019607843137)]94
    0 z& `3 h0 P) N7 Q' S4 O# m[color=rgba(0, 0, 0, 0.749019607843137)]959 q! |5 L5 I5 i4 E5 ?3 q
    [color=rgba(0, 0, 0, 0.749019607843137)]96
    ; v, q: Y& I& _1 h: ?[color=rgba(0, 0, 0, 0.749019607843137)]97# o  Q+ E/ U3 p2 c0 i  B- C5 X
    [color=rgba(0, 0, 0, 0.749019607843137)]98
    8 e( ]' b% ]! j[color=rgba(0, 0, 0, 0.749019607843137)]99& F1 [; A" p2 h  o+ @8 i' t9 @
    [color=rgba(0, 0, 0, 0.749019607843137)]100
    / K, S' l5 v/ Y9 t. z[color=rgba(0, 0, 0, 0.749019607843137)]101$ R; h! c  n( ?$ \$ H* m) V& h# ^
    [color=rgba(0, 0, 0, 0.749019607843137)]102
    & P' |) z( C5 |  d2 I3 j' @# u9 C[color=rgba(0, 0, 0, 0.749019607843137)]103. M! k7 N( _9 R& [9 P1 Q
    [color=rgba(0, 0, 0, 0.749019607843137)]104
    - C6 H" a" y- {. [7 \! S2 t/ K[color=rgba(0, 0, 0, 0.749019607843137)]1057 r- ]+ I9 b( n' T- V5 I7 _
    [color=rgba(0, 0, 0, 0.749019607843137)]106
      F" Z7 {6 \. c0 I[color=rgba(0, 0, 0, 0.749019607843137)]107
    $ `' x2 {; V- I1 J( t0 V6 L( T[color=rgba(0, 0, 0, 0.749019607843137)]108' r; ^6 u6 @1 h& h% N5 q  Q- z: H
    [color=rgba(0, 0, 0, 0.749019607843137)]109' |  t7 l5 f5 L. N+ k
    [color=rgba(0, 0, 0, 0.749019607843137)]1108 x& |) }0 Y2 c, g; a% ~# Y  D
    [color=rgba(0, 0, 0, 0.749019607843137)]1110 _; X0 }& c# |
    [color=rgba(0, 0, 0, 0.749019607843137)]测试结果:
    . R! k2 a* m% T8 y$ K[color=rgba(0, 0, 0, 0.749019607843137)]
    - ?8 w, G/ }2 ]5 v' d" F; F* V  P+ b

    $ I. v4 z* Z6 I' y7 K[color=rgba(0, 0, 0, 0.749019607843137)]
    ; G" m7 Q, L9 j  \3 v2 C

    9 B! F  {* w$ {5 g& f% o[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
    6 ~/ C/ o! V* C[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)7 G7 L( \% I3 M  t/ D
    [color=rgba(0, 0, 0, 0.749019607843137)]4 D" }' H4 ]1 S9 d) D, ~& `
    / C4 Z% S6 D2 ?& y4 J8 ~
    [color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
      d6 ?8 G$ Z# b6 h[color=rgba(0, 0, 0, 0.749019607843137)]//法一:全局变量
    4 h4 l+ ~" i4 w$ q4 C[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
    - w/ c6 x; e( L[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
    1 K, Q6 |+ Y* j& d3 J9 t2 J[color=rgba(0, 0, 0, 0.749019607843137)]//{
    1 q, L& |. q# L5 r. u[color=rgba(0, 0, 0, 0.749019607843137)]//        if (root == NULL)8 c6 p2 D9 ~  z& c1 |! g- E
    [color=rgba(0, 0, 0, 0.749019607843137)]//        {% K1 P  C2 ~! N
    [color=rgba(0, 0, 0, 0.749019607843137)]//                return;
    . w# I. @. X9 G+ Q9 s- Z[color=rgba(0, 0, 0, 0.749019607843137)]//        }4 d3 b% }! \5 f, g+ X5 j# ~3 X
    [color=rgba(0, 0, 0, 0.749019607843137)]//        count++;8 J( @9 C+ U5 c* h
    [color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->left);4 |% L3 n0 Q" l3 d$ ^
    [color=rgba(0, 0, 0, 0.749019607843137)]//        TreeSize(root->right);1 b) w% y! V" v7 r5 e' y
    [color=rgba(0, 0, 0, 0.749019607843137)]//+ g4 q  u6 D9 v& E0 Y
    [color=rgba(0, 0, 0, 0.749019607843137)]//        return;//函数栈帧层层返回,最后回到根节点1,结束了1的右子树函数,什么都不返回,因为count是全局变量
    , v. U) p% V. X( v2 a[color=rgba(0, 0, 0, 0.749019607843137)]//}. V0 S8 L9 Y% a2 L
    [color=rgba(0, 0, 0, 0.749019607843137)]//法二:子问题思路:分而治之
    ; `4 g4 q6 u! p1 k! O[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)7 w3 y3 g  z0 V- P
    [color=rgba(0, 0, 0, 0.749019607843137)]{; l  {0 P0 j/ L
    [color=rgba(0, 0, 0, 0.749019607843137)]        return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
    9 V, D" Q  Q- ]3 o: _- e, ?[color=rgba(0, 0, 0, 0.749019607843137)]}
    $ [$ K3 [5 u( D[color=rgba(0, 0, 0, 0.749019607843137)]1% B! n7 A' b8 D! t
    [color=rgba(0, 0, 0, 0.749019607843137)]22 i/ c. b' }" S( V2 E( C. P- [
    [color=rgba(0, 0, 0, 0.749019607843137)]3! T% t  d6 g& F* y! g/ S$ K
    [color=rgba(0, 0, 0, 0.749019607843137)]4+ X5 A: g5 A6 t! C; j
    [color=rgba(0, 0, 0, 0.749019607843137)]5
    % a" w6 n$ I6 d; j! s/ f[color=rgba(0, 0, 0, 0.749019607843137)]6& K) w- M  l; O9 Z
    [color=rgba(0, 0, 0, 0.749019607843137)]7
    % J! H3 l5 s+ f4 s5 i8 N8 B[color=rgba(0, 0, 0, 0.749019607843137)]88 ]  k9 E4 r1 {9 r( M+ p
    [color=rgba(0, 0, 0, 0.749019607843137)]9
    0 Y4 f& c" K' t. s/ u" B[color=rgba(0, 0, 0, 0.749019607843137)]107 [& R6 B' r+ Q5 ?! i6 p8 K8 B- y
    [color=rgba(0, 0, 0, 0.749019607843137)]11
    + j! G" ~7 v  b6 A- Q- v[color=rgba(0, 0, 0, 0.749019607843137)]12
    # y" P8 T# d' c" Q5 p[color=rgba(0, 0, 0, 0.749019607843137)]13% J$ Q' k' y3 ]1 M: [3 o2 t
    [color=rgba(0, 0, 0, 0.749019607843137)]14
    7 i9 g4 r( m5 W, V9 u5 C, p[color=rgba(0, 0, 0, 0.749019607843137)]152 X! G9 i* W# _* s; h, b. [
    [color=rgba(0, 0, 0, 0.749019607843137)]16
    ! F; B( d2 a8 W/ a: R& H1 m  l[color=rgba(0, 0, 0, 0.749019607843137)]17/ A; U. t5 R* ~3 ^& w% r9 p
    [color=rgba(0, 0, 0, 0.749019607843137)]18
    ) ]) M1 x2 F7 T; x$ w; \7 G[color=rgba(0, 0, 0, 0.749019607843137)]19
    & z% A0 {  o+ R[color=rgba(0, 0, 0, 0.749019607843137)]20
    3 b( a, H" f1 ~. h[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数- Z5 a9 t0 S( L# \" [4 p% S
    [color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数  E$ y, B* N$ l1 q2 `" J/ {
    [color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
    * A3 l* n3 D. [# z# e1 }0 Y[color=rgba(0, 0, 0, 0.749019607843137)]{# S- \2 H& u: E6 W5 G' w. R4 P
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)//首先得考虑空树的情况,0个叶子结点  X) e" R/ a3 e: _( R* V" j+ t4 s
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    0 [5 ?- ^/ S& I8 a0 o[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;$ |3 D$ s; N/ P
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
    6 A& f" M- m6 G' z[color=rgba(0, 0, 0, 0.749019607843137)]        //叶子结点的特征就是左右子树为空
    , A* A8 u. w: }! l7 o[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->left == NULL && root->right == NULL)
    " R4 _" L, a5 @- Q5 }% w[color=rgba(0, 0, 0, 0.749019607843137)]        {; `3 m9 n) B  m; K3 w( u7 l
    [color=rgba(0, 0, 0, 0.749019607843137)]                return 1;( Y9 x% K' J/ Z& Q
    [color=rgba(0, 0, 0, 0.749019607843137)]        }1 C( H: A* s6 h: B+ Q  a+ Z; j
    [color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLeafSize(root->left) + TreeLeafSize(root->right);
    0 {$ i& }; p' O[color=rgba(0, 0, 0, 0.749019607843137)]}" ~; `# c9 [+ k8 U1 D0 t1 D5 [4 n  a
    [color=rgba(0, 0, 0, 0.749019607843137)]1# \5 Y4 D) v9 g$ O: L
    [color=rgba(0, 0, 0, 0.749019607843137)]23 \; `0 C6 |: E( j4 r
    [color=rgba(0, 0, 0, 0.749019607843137)]37 b  n- Z1 s5 j0 G: [! p0 i% \+ v
    [color=rgba(0, 0, 0, 0.749019607843137)]4) z- C  C; k3 {7 H3 \. L4 V5 D
    [color=rgba(0, 0, 0, 0.749019607843137)]5
    & s  N( u+ @# U* ?0 r5 R[color=rgba(0, 0, 0, 0.749019607843137)]6, b' [, Y; ^  T% a% T. V& b
    [color=rgba(0, 0, 0, 0.749019607843137)]7; [- O9 N* {+ Q6 R4 {6 K6 _. }
    [color=rgba(0, 0, 0, 0.749019607843137)]8) x$ y6 o1 l* I
    [color=rgba(0, 0, 0, 0.749019607843137)]9
    8 _% e4 t; ^' g. G: P. I[color=rgba(0, 0, 0, 0.749019607843137)]10
      ]9 `! P3 A: c* J6 G+ a[color=rgba(0, 0, 0, 0.749019607843137)]118 H* s4 d+ O# ^# M# }4 H; n
    [color=rgba(0, 0, 0, 0.749019607843137)]12
    8 ~4 `; V( F8 k0 `9 t4 N4 G: m[color=rgba(0, 0, 0, 0.749019607843137)]13
    : {3 g2 _$ p2 V- L8 O) S' c+ O: s[color=rgba(0, 0, 0, 0.749019607843137)]14
    ) {! w' U9 e  l/ ]$ g' n6 x- o- `[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度; o7 ]3 q$ z( o; `/ @
    [color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
    + l1 p2 T% m5 X- l6 O/ t2 _[color=rgba(0, 0, 0, 0.749019607843137)]{2 J5 L0 R. c6 d
    [color=rgba(0, 0, 0, 0.749019607843137)]        //空树高度为0, p6 }, A  O2 B: s
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)- y5 F! _9 A) o7 a2 }. R
    [color=rgba(0, 0, 0, 0.749019607843137)]        {+ M7 A, q' \+ H" V/ p8 g2 i
    [color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
    $ K+ C: ^. l% T[color=rgba(0, 0, 0, 0.749019607843137)]        }/ I- M2 f! a0 |
    [color=rgba(0, 0, 0, 0.749019607843137)]        //树的高度是较高的那棵子树! A& s* |/ D0 L0 T1 ?
    [color=rgba(0, 0, 0, 0.749019607843137)]        int lh = TreeHeight(root->left);//左子树的高度
    0 {  `6 q: v! a! _% q" m[color=rgba(0, 0, 0, 0.749019607843137)]        int rh = TreeHeight(root->right);//右子树的高度1 ]! N9 ~  T/ h9 Q" j
    [color=rgba(0, 0, 0, 0.749019607843137)]4 l" C6 w. `# T3 ]! x6 A
    ) r3 s- h9 j9 D* j4 }0 n
    [color=rgba(0, 0, 0, 0.749019607843137)]        return lh > rh ? lh + 1 : rh + 1;" X. w% ?: |) N# `
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    8 ?: Z( V; B( n4 L[color=rgba(0, 0, 0, 0.749019607843137)]10 I. G5 i5 e3 h
    [color=rgba(0, 0, 0, 0.749019607843137)]2
    + I$ C* ?9 A' }: I, }! a+ H4 X[color=rgba(0, 0, 0, 0.749019607843137)]3
    3 @& w: _/ ^2 f3 O9 S1 R( p, Y[color=rgba(0, 0, 0, 0.749019607843137)]42 [4 N/ k+ Z) @
    [color=rgba(0, 0, 0, 0.749019607843137)]5) Y" w$ i% u5 o
    [color=rgba(0, 0, 0, 0.749019607843137)]6! ]  ~! y5 Q3 G# F8 I6 x+ J
    [color=rgba(0, 0, 0, 0.749019607843137)]7
    : m' C* X4 ?' u# D, V0 V% J[color=rgba(0, 0, 0, 0.749019607843137)]8
    # v( X. O! ~% w) G$ p  i[color=rgba(0, 0, 0, 0.749019607843137)]90 A/ `8 q, H8 s( ^) S! z% H/ H/ z
    [color=rgba(0, 0, 0, 0.749019607843137)]10
    ) n/ d4 _7 m; D3 c/ o7 h- f* l% Z[color=rgba(0, 0, 0, 0.749019607843137)]11+ P, G! i5 x2 W( W" F( [' V
    [color=rgba(0, 0, 0, 0.749019607843137)]122 V/ q! b4 C2 o' {# u
    [color=rgba(0, 0, 0, 0.749019607843137)]13
    1 ]/ k' @6 F/ t1 X[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
    7 j7 {% r1 s' \9 R& e% P  u[color=rgba(0, 0, 0, 0.749019607843137)]
    & A" U- h$ p6 g; m; h! f) `

    - L* X" i( W! ~[color=rgba(0, 0, 0, 0.749019607843137)]
    3 s# y/ O4 Q- e8 I7 Q, ^( e
    0 m% I6 w& O  j8 B; x3 J* `
    [color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数,转换成求子树第K-1层的结点个数。举个栗子:如果我们要求这棵二叉树第3层的结点个数(为3),就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
    ( D" u4 M) P( v  N) F  {- e[color=rgba(0, 0, 0, 0.749019607843137)]) y9 g9 S% ^1 U! W
    # O3 o, ~! r5 O' \# T9 a7 W
    [color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
    : S; k% ~- x" }% A7 c$ d[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)5 F- ~) A$ G' \2 M+ w: v+ G) o
    [color=rgba(0, 0, 0, 0.749019607843137)]{
    ' T8 T) A$ i+ c4 S( g[color=rgba(0, 0, 0, 0.749019607843137)]        assert(K > 0);
    & P4 E  k) E6 Q; i8 a6 w- X[color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)& A0 x6 H5 H3 w; C/ o1 t: X
    [color=rgba(0, 0, 0, 0.749019607843137)]        {
    0 w6 E3 b: T2 ?9 y: D[color=rgba(0, 0, 0, 0.749019607843137)]                return 0;
    4 t7 q1 m/ h; w) e7 L[color=rgba(0, 0, 0, 0.749019607843137)]        }* V' ~, z$ ]  Q, m4 I
    [color=rgba(0, 0, 0, 0.749019607843137)]        //如果是第一层(递归出口)
    7 s6 Q: B1 _3 b- J; J[color=rgba(0, 0, 0, 0.749019607843137)]        if (K == 1)
    - C  ~* [3 O6 L( a* a5 p6 l[color=rgba(0, 0, 0, 0.749019607843137)]        {
    $ p: U6 y7 w7 S[color=rgba(0, 0, 0, 0.749019607843137)]                return 1;- q. z, \4 T/ L9 P
    [color=rgba(0, 0, 0, 0.749019607843137)]        }& ]" K3 Z7 I% i- h; V( m! F$ u
    [color=rgba(0, 0, 0, 0.749019607843137)]        //转换成子树的第K-1层9 d- P" A7 y1 b: A) H1 A
    [color=rgba(0, 0, 0, 0.749019607843137)]        return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
    1 Y7 {* g$ B1 ]8 |1 q3 O! d6 b[color=rgba(0, 0, 0, 0.749019607843137)]}
    6 }- c, J' A0 J& r- n: N2 y- D[color=rgba(0, 0, 0, 0.749019607843137)]1, |4 }( A/ c0 l5 l5 b8 n7 j9 w
    [color=rgba(0, 0, 0, 0.749019607843137)]27 q7 s4 B4 f$ Z4 B
    [color=rgba(0, 0, 0, 0.749019607843137)]3, `3 l* }2 {5 M+ ?
    [color=rgba(0, 0, 0, 0.749019607843137)]4
    % O2 O9 a4 G& h) T& f0 z, X[color=rgba(0, 0, 0, 0.749019607843137)]58 o% X- r1 r, M: Y" S! T# {
    [color=rgba(0, 0, 0, 0.749019607843137)]6
    " D4 v, P/ i! ]3 `( ~2 S! j' E  F[color=rgba(0, 0, 0, 0.749019607843137)]7
    : x4 m/ h. Y# E) Z+ g) w* r; P9 B[color=rgba(0, 0, 0, 0.749019607843137)]8' e6 J3 A% Y8 `" x7 D9 f
    [color=rgba(0, 0, 0, 0.749019607843137)]9! W" I# l9 F7 x& ~; F2 c: h; Z
    [color=rgba(0, 0, 0, 0.749019607843137)]10
    9 X+ V$ D8 z% S6 T6 {- d* u6 e+ e[color=rgba(0, 0, 0, 0.749019607843137)]116 g' {% q  I( U- q( p% {% r3 N
    [color=rgba(0, 0, 0, 0.749019607843137)]12
    2 Y" ~- ]; @: X[color=rgba(0, 0, 0, 0.749019607843137)]13& @5 ?; N7 @! U- p' p' p
    [color=rgba(0, 0, 0, 0.749019607843137)]14+ l! C0 S, \- d, d
    [color=rgba(0, 0, 0, 0.749019607843137)]15
    " ]. x9 z) r# Y. v3 w3 ?# Q[color=rgba(0, 0, 0, 0.749019607843137)]16
    . k1 Z, a+ r8 q3 `, O' T. a[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找& n/ M" z7 W) M( r1 H8 p. z
    [color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
    0 {: j# y6 ~6 g4 m% H, m[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
    - L5 ^6 y4 S( N2 @9 v[color=rgba(0, 0, 0, 0.749019607843137)]{5 n  v# S. V  ]6 w! k
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (root == NULL)
    9 D2 e  `/ Z% m6 g: n/ C[color=rgba(0, 0, 0, 0.749019607843137)]        {
    ! q3 t+ J2 y$ w3 d" L[color=rgba(0, 0, 0, 0.749019607843137)]                return NULL;) D! M( Y7 Y+ h" W; T
    [color=rgba(0, 0, 0, 0.749019607843137)]        }
      E0 X) G. V& L0 v  F[color=rgba(0, 0, 0, 0.749019607843137)]        if (root->data == data)9 v" Y% B/ E+ t
    [color=rgba(0, 0, 0, 0.749019607843137)]        {; `4 r% g' u* r8 D9 f3 d' e5 q
    [color=rgba(0, 0, 0, 0.749019607843137)]                return root;" S8 _4 |5 |. _1 v+ Y/ W
    [color=rgba(0, 0, 0, 0.749019607843137)]        }4 m- d) }$ S  S/ ^5 J3 `/ r- T5 W
    [color=rgba(0, 0, 0, 0.749019607843137)]        //先查找左子树
    , K4 X4 _1 Q1 g$ Q. [[color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* lret = TreeFind(root->left, data);3 ~* j! `9 m/ G/ E- f) i) y( v
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (lret)
    3 \" G! `; F0 C  Z* D$ e[color=rgba(0, 0, 0, 0.749019607843137)]                return lret;$ f# W+ ?) D. e
    [color=rgba(0, 0, 0, 0.749019607843137)]        //再查找右子树* y* H6 k; i( k# Z; ~
    [color=rgba(0, 0, 0, 0.749019607843137)]        BTNode* rret = TreeFind(root->right, data);" g3 l0 {( E, k" z4 ?
    [color=rgba(0, 0, 0, 0.749019607843137)]        if (rret)
    * A: c! \4 k5 x3 ~$ `[color=rgba(0, 0, 0, 0.749019607843137)]                return rret;
    " e% U( r; r4 ~/ {# ^6 l7 h" `[color=rgba(0, 0, 0, 0.749019607843137)]        return NULL;9 e2 |2 _) ?/ Z* \9 }  _
    [color=rgba(0, 0, 0, 0.749019607843137)]}
    4 V$ h4 T+ `, s" j' @' w$ Z[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
    9 s& o/ k. {2 q: ]$ G* H  e5 M  {[color=rgba(0, 0, 0, 0.749019607843137)]版权声明:本文为CSDN博主「SouLinya」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
    " f/ _% q% Y( Q& z4 {& ~: ^- U7 x[color=rgba(0, 0, 0, 0.749019607843137)]原文链接:https://blog.csdn.net/weixin_63449996/article/details/1268412125 \4 ?! p& `  x9 Z4 m

    # s1 o0 k) W" x  E* H" ~# O5 U% E! l
    [color=rgba(0, 0, 0, 0.75)]/ S/ v( I& Z' a6 \

    + b4 P7 h. ]( Z, M
    9 C5 k9 ?  j. n; g" b
    6 C& a5 ?" W* E, C# \4 z
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

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

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

    蒙公网安备 15010502000194号

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

    GMT+8, 2026-8-6 10:52 , Processed in 0.525254 second(s), 51 queries .

    回顶部