【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历 x8 f) g8 g. s( F6 o0 t: { b1 K
% ^* i1 a4 `* T3 |' @[color=rgba(0, 0, 0, 0.749019607843137)]文章目录: U9 K5 T7 b- G& Q# v1 L: ^- Q j
[color=rgba(0, 0, 0, 0.749019607843137)]前言
f. e; e' A7 C9 Q3 K6 J7 x% c[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
0 e) Q% N, Z, G0 f: ?& P[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）0 ^8 C- B: N+ }0 r1 v. @, D% C5 M9 J
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历8 l% F) b5 h U% ]
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
- F( \' Z; C2 j9 J+ v[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
. T5 D( P) p- e' Q8 _8 F[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度" g1 W. S# q: D6 z$ n7 I( w, J
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
4 K( w6 j. m1 i8 z+ G2 c& w[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找# S. E+ `( j0 o$ Q
[color=rgba(0, 0, 0, 0.749019607843137)]前言
; I7 D7 s! T' G: p+ O1 d5 w: E: s[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。' L8 ?1 Y3 y# ?) D7 Q# B- d B
[color=rgba(0, 0, 0, 0.749019607843137)]
4 V! ?9 v8 S+ C% A8 F0 x \3 r* k& F+ P0 @4 g) X
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式0 k3 p- L7 g, Z: A4 O$ w9 J
[color=rgba(0, 0, 0, 0.749019607843137)]
1 k( P# l4 F; S% w& {! N5 h
; j! r. m. G$ S5 M4 R' h' C+ ?5 v[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：1 K% K' G* Y/ l6 m2 r
[color=rgba(0, 0, 0, 0.749019607843137)]
{6 }2 ^* U& P- m3 C9 A
5 @" @4 t! L5 N4 q" F[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树5 p. d2 D' `( w, t
[color=rgba(0, 0, 0, 0.749019607843137)]+ j6 W6 t8 m1 ^# o
8 |, ` ?* Z! b# _$ b, f[color=rgba(0, 0, 0, 0.749019607843137)]) U$ |' L2 d0 G1 f, @
+ a1 ~1 y9 w' _# e$ {5 c* |1 i
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树2 e1 y! g# S& D. n: S- x
[color=rgba(0, 0, 0, 0.749019607843137)]
$ U& A: {$ \8 B$ @% f o( Z4 M3 x/ K5 C& l3 Z
[color=rgba(0, 0, 0, 0.749019607843137)]& x: l- R5 O) p2 j
3 I7 O4 R4 @. T/ E- | w+ D
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
1 W$ y6 i- {# n3 H$ d" y, h6 }1 Q[color=rgba(0, 0, 0, 0.749019607843137)]5 ]* ^6 M- ?8 d. D* u
/ w) a( F: ~3 _
[color=rgba(0, 0, 0, 0.749019607843137)]
& D$ z1 d( O9 a6 _0 g+ Z: R( a
2 ?5 Q. Y; J" f8 p7 h[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
8 v7 Y0 _ v* p+ S [4 [[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之) @* b7 p! ]! Z1 @: T( }
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
$ D' h5 }: T' z7 S/ P0 I[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；; ^6 d, B4 W. e4 P5 g8 e
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；& H9 t, \) H2 A/ k2 b
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；; [2 G% ^1 h, j2 F5 J2 w
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；$ p: D* b$ V/ D" k' R
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；) D$ X' L1 w" }: @% ?# f- ?
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。$ ~4 M, c4 h) s5 c6 {
[color=rgba(0, 0, 0, 0.749019607843137)]8 l& i5 A1 {) @, d5 g5 j7 w2 h& }$ ~
4 t7 o0 g* X/ o. q+ B5 m4 _& X0 u6 l
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
& ^- _( g0 h9 i8 }[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
! o! v' f/ l5 ?) S2 A[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
/ ? G- m1 T; `3 g# Y! ~[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
) O$ i" ` v# w7 B/ @[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
. W8 n5 n S0 a. l[color=rgba(0, 0, 0, 0.749019607843137)]
" K0 o1 r+ l+ e9 E6 Z0 N* _5 Y$ M p& l( j" p7 |' ^
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;! s7 ~% H: X' ~: K9 }& y; k/ D5 V
[color=rgba(0, 0, 0, 0.749019607843137)]
' v% L( k( T4 I; `+ ^/ J
3 Z6 T M0 B1 z* I[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
3 c5 d0 C6 o: _& ~[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
6 V0 _: l3 ?2 K$ g, N[color=rgba(0, 0, 0, 0.749019607843137)]{ ]6 j* s, q! m+ M/ G' x3 y7 Z: Z' c7 y
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;
; r8 q$ w* q* }7 c[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
$ c" c b9 A' j" |5 J; }5 X) @[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
! s: m: o6 Z) b1 r# `& J$ Y; ^# }+ R[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;8 \$ K" g1 Z4 `
[color=rgba(0, 0, 0, 0.749019607843137)]2 i2 P' i0 u1 s( i; t4 [+ ]
3 I% u% b8 I8 ~4 Q# ]- a[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历( E P7 e S9 X, ?
[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
" @7 f- m/ x( B% O[color=rgba(0, 0, 0, 0.749019607843137)]{. o5 ?0 c0 ]& s) w% B
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
' r4 \3 t! I- F; J[color=rgba(0, 0, 0, 0.749019607843137)] {
) w9 Q* _1 o4 X4 D D' Y[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");7 G: ]' s- h. N. j5 v: U0 A
[color=rgba(0, 0, 0, 0.749019607843137)] return;* `' o/ @. f" C+ T' I) V0 j( G6 o
[color=rgba(0, 0, 0, 0.749019607843137)] }
& V' I: G* I1 g. r s& e, l' j[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);% m' J4 k% J, f
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
! ^* g9 ~' ]* M2 }5 T! q[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);3 W. G) I- h" c! z/ I# F% P
[color=rgba(0, 0, 0, 0.749019607843137)]}, h! Y0 g6 S6 u, K; s$ x' N- }% W6 I+ m
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
6 ^3 R3 B7 l! t3 A/ r: ][color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
, f, @; K6 z# M; O y[color=rgba(0, 0, 0, 0.749019607843137)]{" s1 L% c1 k6 O# h3 r1 J
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)% D, x) r0 M+ f% M! c' j7 G
[color=rgba(0, 0, 0, 0.749019607843137)] {1 Q) q. `9 I5 B1 k% k+ b; L( R
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");2 T1 Y N* Y% Z7 {- |. E: {. B
[color=rgba(0, 0, 0, 0.749019607843137)] return;! |* q8 p! ]7 ?% @. \
[color=rgba(0, 0, 0, 0.749019607843137)] }
: {+ K' U: S5 h+ C[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);- q) `: l0 T8 T
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
) j2 k Z' c+ k1 B) f3 y- ?% v[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);1 V0 s$ e Z+ e0 N8 f# v+ Y
[color=rgba(0, 0, 0, 0.749019607843137)]}
& V( q# Q9 f. G2 s; e, }( p[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
5 E/ W0 U7 P" X) Q9 }1 r) X) i5 |8 D0 K[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)! C8 k* h* j3 H4 D7 K3 @
[color=rgba(0, 0, 0, 0.749019607843137)]{
) @' d1 v' _7 p% y+ h/ B4 c/ f. H[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
9 t- Y; Q" A5 b4 i[color=rgba(0, 0, 0, 0.749019607843137)] {% ~8 m) m8 W( ?" Z' H' e( Q( [
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
; M. u" \2 f! F: i0 ^ M[color=rgba(0, 0, 0, 0.749019607843137)] return;5 ^" r; \0 m& {3 s3 U
[color=rgba(0, 0, 0, 0.749019607843137)] }
- N( r) B' y% I[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
5 v4 H/ R3 y& G& \7 W* }[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
M. I2 W! u5 M4 S) a[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
2 A$ {3 a. q' F; E& C* u0 z[color=rgba(0, 0, 0, 0.749019607843137)]}
+ g5 ^& K: t% F0 K3 ]* u- Z9 q$ Q[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构
/ L7 G) @. t) w5 q x9 X[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()
6 k3 h: K% `& Y; y" b4 U6 F[color=rgba(0, 0, 0, 0.749019607843137)]{" Z, ]7 r8 d: ~1 B0 u2 g, j8 b
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
+ Z6 ~; q3 ?' o3 q[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));4 {* E1 [* u/ d+ V8 _! U) J/ Q
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);! ^7 n' H# [* z; P( L
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
! [! B! e/ G/ t I5 m[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
! K6 A8 h8 k7 ^# v[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
7 M! _0 P- N8 o" ~2 |[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);4 i, y( [' h; h# l2 s' t+ \% s
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode)); f2 y/ ~2 I4 v
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
2 Y$ u- M% @1 a, R n# {9 N* K0 C[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));; H4 k8 V! [4 J2 n% T0 |! J
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
& X* Z, i5 m& X6 x$ c0 |[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
2 O% q1 F! |# i9 H[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);( a G" s4 J: H! q b- `
[color=rgba(0, 0, 0, 0.749019607843137)]
4 d1 ~! ~1 C8 O( l8 z2 `( S0 _6 [3 E3 k7 W0 G
[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;5 d9 J3 _3 N4 o! r+ D
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
7 V0 a2 B _+ ]" F[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;4 U- v' n. _* g$ F" Y L n/ t
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;, s' G2 R" E: f$ }5 D3 j0 {' h" |
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;: S: F8 r( g7 t) l
[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;. F+ h0 {9 ~+ N5 m2 `3 e
[color=rgba(0, 0, 0, 0.749019607843137)]
( m [7 j! a$ L
' r5 ?: B5 n0 ]8 Y[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;( g* w* e' Z0 A) q0 ]. H
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
2 N; \+ p' n! _) i9 m7 h[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;
9 h- Z' G6 x: i% E[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
+ R+ e" h+ X: W) a[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
3 ]. S$ H4 U% s# D' S8 w6 F3 N[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;+ Q w+ M ?; q0 d) e7 e, ]
[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;- O# O3 T2 n6 ?) n3 C. c
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;3 y# I) W7 ^8 _. _% o
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;: ^, r Y8 Q$ A1 {8 h/ ^* \
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
$ T: e; E* v) W' E6 M[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
% G4 U# l* Y1 m- Q[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
3 y2 S# q; V& r[color=rgba(0, 0, 0, 0.749019607843137)]* ]' f* l: M. b! Y8 i
' k4 O& D& S4 @- z[color=rgba(0, 0, 0, 0.749019607843137)] return n1;3 m3 Y/ {5 C t, l+ Q
[color=rgba(0, 0, 0, 0.749019607843137)]}7 z e: ^$ k6 j* @
[color=rgba(0, 0, 0, 0.749019607843137)]
& H! R! F1 y" T. | U# B8 f- {9 t+ W/ v+ R
[color=rgba(0, 0, 0, 0.749019607843137)]int main()* R! r, d2 d: K4 i( X/ z
[color=rgba(0, 0, 0, 0.749019607843137)]{3 L% ?5 z; ^9 J: {& P1 ] ^$ o
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构! n7 |" Z! s$ U. q" v" Z+ b
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();- @, b7 e, h5 |/ h& c9 l3 Z
[color=rgba(0, 0, 0, 0.749019607843137)], x) b+ h* a1 A3 z. C) X3 {
9 O- R5 P5 I+ P, L: w( `[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历0 G- _1 P5 \5 U" Y% M+ o
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");( ?/ N$ J) Z3 p/ {( s. I% f: Q
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
6 N* Y' \: y" i5 _5 ^[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
1 y9 d' t; Q7 F, {* l# j[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历; {3 }/ K6 | {, t* Y
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");+ I; [2 C7 I! ]/ K
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);+ c% ^8 A! d+ J6 R3 @6 a) E- K
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
" D( G( D- u1 G' Y: _+ C. X[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历+ ` T S0 F9 A# h. A1 U. A8 @6 u
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");. J3 f( C) d) a$ ]. l' r
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
1 b/ b+ L$ k, @* c[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");$ R- X* x; X4 z W2 B2 T; ~
[color=rgba(0, 0, 0, 0.749019607843137)]) b- J O! ?* v4 a ]5 D
0 T4 @2 {/ i: i- w[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
! ]' \' v7 h6 [( b[color=rgba(0, 0, 0, 0.749019607843137)]}
* O2 G y% [1 E8 O9 J5 x* T[color=rgba(0, 0, 0, 0.749019607843137)]1
1 z$ H6 i8 d: B[color=rgba(0, 0, 0, 0.749019607843137)]2
1 D X0 Z; ^) v1 V+ P[color=rgba(0, 0, 0, 0.749019607843137)]3# T6 S' Q7 t- m& C( T
[color=rgba(0, 0, 0, 0.749019607843137)]4+ Z' k* x! f8 I# P* @
[color=rgba(0, 0, 0, 0.749019607843137)]5
" q" Y+ P; l; y1 y/ s! d[color=rgba(0, 0, 0, 0.749019607843137)]6" L; c3 @+ x3 z* c$ _% j
[color=rgba(0, 0, 0, 0.749019607843137)]7" n% v. N i2 N4 W& u+ D* K
[color=rgba(0, 0, 0, 0.749019607843137)]81 I# P+ y t9 I; E5 W
[color=rgba(0, 0, 0, 0.749019607843137)]9) ?4 x$ m, y0 X y l, F7 y
[color=rgba(0, 0, 0, 0.749019607843137)]10, ~+ [7 t9 t' o4 g3 B8 Z
[color=rgba(0, 0, 0, 0.749019607843137)]11# e ~$ v5 O( ~
[color=rgba(0, 0, 0, 0.749019607843137)]12. F0 P& B: ~! d' `3 l+ B
[color=rgba(0, 0, 0, 0.749019607843137)]130 T8 |) c9 R; k, k: S* s2 `$ H4 g
[color=rgba(0, 0, 0, 0.749019607843137)]14 t! \( o& V1 i' L
[color=rgba(0, 0, 0, 0.749019607843137)]15" |' V4 h( j8 S
[color=rgba(0, 0, 0, 0.749019607843137)]169 U2 j2 B0 N6 r3 [& N) S; o9 b
[color=rgba(0, 0, 0, 0.749019607843137)]17
5 i. K. v0 t9 ^5 O- w[color=rgba(0, 0, 0, 0.749019607843137)]18, P/ \: m# q% l$ z
[color=rgba(0, 0, 0, 0.749019607843137)]19
9 ~9 g6 D# i4 J% X7 k, ^) |5 p+ F[color=rgba(0, 0, 0, 0.749019607843137)]203 w, f3 e' z( s
[color=rgba(0, 0, 0, 0.749019607843137)]214 s. E+ C0 O- Q H
[color=rgba(0, 0, 0, 0.749019607843137)]225 | W: e# o% `4 u/ y: E* j
[color=rgba(0, 0, 0, 0.749019607843137)]23
9 D7 t# ?6 B: ]: v. A, w" T5 y& N[color=rgba(0, 0, 0, 0.749019607843137)]24' x9 c* } p: S" s' m1 x
[color=rgba(0, 0, 0, 0.749019607843137)]25/ O3 w- V. F; l" J6 b5 J8 x" n
[color=rgba(0, 0, 0, 0.749019607843137)]26
% u' Y9 v& b5 E7 h" g- c, Q4 S$ ^[color=rgba(0, 0, 0, 0.749019607843137)]274 C. C7 C4 Q+ B0 b V; v0 s# k
[color=rgba(0, 0, 0, 0.749019607843137)]28' j2 h6 z6 ]) x0 H; C7 k C; c
[color=rgba(0, 0, 0, 0.749019607843137)]29! f( u; D4 J8 W/ ^
[color=rgba(0, 0, 0, 0.749019607843137)]30; b3 Z& x) E4 i% _
[color=rgba(0, 0, 0, 0.749019607843137)]31# ] g6 R, u' B c, Y. D7 m* g
[color=rgba(0, 0, 0, 0.749019607843137)]320 K4 x' A3 Y* J$ x
[color=rgba(0, 0, 0, 0.749019607843137)]33
# q( \4 p# j" a[color=rgba(0, 0, 0, 0.749019607843137)]34
* |; }- c/ \+ a, O[color=rgba(0, 0, 0, 0.749019607843137)]35
6 i& ?# T% e) ~[color=rgba(0, 0, 0, 0.749019607843137)]36
9 n. j& @2 j2 C/ j. |! K1 T[color=rgba(0, 0, 0, 0.749019607843137)]37
$ {' ^& ?9 a! P+ r6 X4 _/ A1 n[color=rgba(0, 0, 0, 0.749019607843137)]38
1 F' _7 n% m( K1 P8 N& {[color=rgba(0, 0, 0, 0.749019607843137)]39
2 x% y5 o- h+ v& t" H[color=rgba(0, 0, 0, 0.749019607843137)]40
2 ^+ q/ k" G% o/ p8 ?[color=rgba(0, 0, 0, 0.749019607843137)]41
/ g2 N( n$ j2 {2 O' x[color=rgba(0, 0, 0, 0.749019607843137)]425 w i$ Z' B9 o; Z2 C+ `
[color=rgba(0, 0, 0, 0.749019607843137)]43
& }$ e! U3 T H l1 V+ S9 c' T[color=rgba(0, 0, 0, 0.749019607843137)]447 i- N: P! g6 ^$ s4 W8 ]3 z
[color=rgba(0, 0, 0, 0.749019607843137)]45
; I6 L8 Y3 }+ @7 R" N! r[color=rgba(0, 0, 0, 0.749019607843137)]46# }6 ]: Q; c l0 [0 ]" K+ Q7 m
[color=rgba(0, 0, 0, 0.749019607843137)]47
$ l& d' c& ~4 h) r[color=rgba(0, 0, 0, 0.749019607843137)]48+ p- O4 S" p! {. _
[color=rgba(0, 0, 0, 0.749019607843137)]490 q9 D Q' N& b$ V- k9 ]
[color=rgba(0, 0, 0, 0.749019607843137)]505 V' x* k/ j* a, ]
[color=rgba(0, 0, 0, 0.749019607843137)]51. r% D; _$ z( [* U4 X
[color=rgba(0, 0, 0, 0.749019607843137)]52
- d9 V. t- N, g6 N& Z[color=rgba(0, 0, 0, 0.749019607843137)]53
/ a) ~; \1 v/ r8 h7 k[color=rgba(0, 0, 0, 0.749019607843137)]54- F7 t3 T5 k. L& v2 N
[color=rgba(0, 0, 0, 0.749019607843137)]550 c1 R8 Q" z: X& R1 J* e
[color=rgba(0, 0, 0, 0.749019607843137)]56$ @; K( j9 [8 I6 k( i3 w
[color=rgba(0, 0, 0, 0.749019607843137)]57
6 U7 O v" B5 h3 r4 _9 }[color=rgba(0, 0, 0, 0.749019607843137)]58
: {7 n$ \ Y5 E9 b[color=rgba(0, 0, 0, 0.749019607843137)]59
' L; Q9 N5 C- N( @[color=rgba(0, 0, 0, 0.749019607843137)]60( g8 |8 E2 F" U& M* _. c! I2 r
[color=rgba(0, 0, 0, 0.749019607843137)]617 s) ?* E" u% Y6 K# Y6 Y
[color=rgba(0, 0, 0, 0.749019607843137)]624 l+ J2 w/ c& t: v0 Y
[color=rgba(0, 0, 0, 0.749019607843137)]63! Y' w( F \. x- ?2 {
[color=rgba(0, 0, 0, 0.749019607843137)]64
: W0 S5 t! r5 P- t( a* h8 J[color=rgba(0, 0, 0, 0.749019607843137)]658 t* u! D8 v# Q; |, z& U+ i8 c7 v4 a$ D
[color=rgba(0, 0, 0, 0.749019607843137)]66
2 p: F0 l/ U" D4 U. P[color=rgba(0, 0, 0, 0.749019607843137)]67( D2 Z7 S5 {& K& \
[color=rgba(0, 0, 0, 0.749019607843137)]68
; l, V% a, |2 g) Q, `% Y# V1 e[color=rgba(0, 0, 0, 0.749019607843137)]697 r4 v: Y- n1 x; h' L
[color=rgba(0, 0, 0, 0.749019607843137)]70
6 [* z& w/ K3 Q. s; y% @[color=rgba(0, 0, 0, 0.749019607843137)]71
6 I* T b7 Y4 N& x. d" I9 ~& H' y[color=rgba(0, 0, 0, 0.749019607843137)]72
1 S1 {# `# I6 S) U+ a" K% e[color=rgba(0, 0, 0, 0.749019607843137)]736 k7 d, B8 }2 ?% _
[color=rgba(0, 0, 0, 0.749019607843137)]74
3 W& w7 u" u# C0 M0 P# |+ k) A[color=rgba(0, 0, 0, 0.749019607843137)]75
7 C: Q& q0 G* D+ ~[color=rgba(0, 0, 0, 0.749019607843137)]76" G9 l2 K7 p" |5 r+ P
[color=rgba(0, 0, 0, 0.749019607843137)]77* U# o: E1 G! T0 c4 ]9 {
[color=rgba(0, 0, 0, 0.749019607843137)]78
* u/ G/ @8 V) A/ U4 J[color=rgba(0, 0, 0, 0.749019607843137)]79. U6 B9 X' s$ _
[color=rgba(0, 0, 0, 0.749019607843137)]80! g! A9 h( q" f3 ?& m" l
[color=rgba(0, 0, 0, 0.749019607843137)]81& C! P0 w. \3 r) q2 Y& j1 ]2 Z7 J
[color=rgba(0, 0, 0, 0.749019607843137)]82
5 A, p" {0 R9 H[color=rgba(0, 0, 0, 0.749019607843137)]83; k% y5 `1 C5 O
[color=rgba(0, 0, 0, 0.749019607843137)]846 B1 U" h. g. i$ m' W" Y/ j9 |
[color=rgba(0, 0, 0, 0.749019607843137)]85% [- K2 h3 Y5 K7 r* i9 \
[color=rgba(0, 0, 0, 0.749019607843137)]86" g9 D) s: I# ?) u/ k* B( Y
[color=rgba(0, 0, 0, 0.749019607843137)]87
$ i5 X* |, q" I9 g8 Z8 P( z[color=rgba(0, 0, 0, 0.749019607843137)]88
' L9 \% c+ k: U* [/ z[color=rgba(0, 0, 0, 0.749019607843137)]89$ w- I7 Q. ~" l! o* R, c
[color=rgba(0, 0, 0, 0.749019607843137)]90
( ^$ m" M2 X' p, \8 \$ f[color=rgba(0, 0, 0, 0.749019607843137)]919 J# c& K* B+ t7 I4 v
[color=rgba(0, 0, 0, 0.749019607843137)]92
' |9 P( _- h7 h[color=rgba(0, 0, 0, 0.749019607843137)]93
7 j0 c, E' y0 H4 o: f& M[color=rgba(0, 0, 0, 0.749019607843137)]947 l) n" |# x, X+ `! l
[color=rgba(0, 0, 0, 0.749019607843137)]95
0 B9 {5 p, y8 M; s" M0 D" D( N[color=rgba(0, 0, 0, 0.749019607843137)]96% F6 @+ X8 K+ m0 w# D: j
[color=rgba(0, 0, 0, 0.749019607843137)]976 c1 A+ O+ l4 f& r
[color=rgba(0, 0, 0, 0.749019607843137)]98
3 C" U' ?* V: o/ y9 R[color=rgba(0, 0, 0, 0.749019607843137)]99/ e, t& {. S! g( O, p" I# Z
[color=rgba(0, 0, 0, 0.749019607843137)]100) {: I9 W7 Z4 @% Q, \
[color=rgba(0, 0, 0, 0.749019607843137)]101
4 R6 e: R2 c# W! w% t0 J! ]2 e+ B[color=rgba(0, 0, 0, 0.749019607843137)]102" I% T7 F. B. n4 b" a
[color=rgba(0, 0, 0, 0.749019607843137)]103
% b% S6 n2 M* w. M: d1 R/ @[color=rgba(0, 0, 0, 0.749019607843137)]104
: t' H( J' {- e! @% N) O5 i5 ^[color=rgba(0, 0, 0, 0.749019607843137)]1054 c% \$ Q8 q d7 K+ N6 ~& \
[color=rgba(0, 0, 0, 0.749019607843137)]106
9 c* W3 P$ `/ j8 u% ?[color=rgba(0, 0, 0, 0.749019607843137)]107
, }6 v& r# v# d& m[color=rgba(0, 0, 0, 0.749019607843137)]108
: W4 z# W& _* x[color=rgba(0, 0, 0, 0.749019607843137)]109' Z' A4 ], O* R4 o" K' z
[color=rgba(0, 0, 0, 0.749019607843137)]110& _6 @. \6 [1 ~+ z6 o
[color=rgba(0, 0, 0, 0.749019607843137)]111( y L: l8 ^4 N4 h1 x0 \
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果： j0 n, e& V2 O# b. P8 P5 E
[color=rgba(0, 0, 0, 0.749019607843137)]2 D' ~( @; R9 W" A$ c
# a& {- D5 T J0 _7 B7 S$ S0 M l
[color=rgba(0, 0, 0, 0.749019607843137)]
D& B( {: K6 |5 b- x$ M8 Z
8 P0 v: }7 k$ ~: H. s! L8 U[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小$ ^4 o$ F. @/ b. p' j
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)# \ w- @2 e3 w6 u$ p! A1 j& t- W: z: {4 ^
[color=rgba(0, 0, 0, 0.749019607843137)]+ D5 z& \1 D. x$ v4 B: q
4 [& r% {- ]" h& L4 a) S7 v5 a% {[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小# X/ Y+ E. } L* X
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量8 ~" f0 q2 o- u3 U
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;: Z( v* z/ D7 a1 h* ` |% X
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root) F0 {+ k. z! I/ T; f6 ?
[color=rgba(0, 0, 0, 0.749019607843137)]//{
; `0 }; R" N& H! b3 a# j {[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
2 S2 t, o: @& Z. a[color=rgba(0, 0, 0, 0.749019607843137)]// {- l0 j. j \7 X3 W
[color=rgba(0, 0, 0, 0.749019607843137)]// return;
6 r' o# M# J; n! I[color=rgba(0, 0, 0, 0.749019607843137)]// }$ B- A+ S; i) K( F8 k# Z
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;
* O* F& |( } V a* m, k+ S[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
& Y$ d9 d. F+ ?[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);& v7 W, N. f# p$ J; g
[color=rgba(0, 0, 0, 0.749019607843137)]//
" F: F' Q! q1 t2 o8 |% x[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量$ D' A9 s6 i& Z X" Z& e
[color=rgba(0, 0, 0, 0.749019607843137)]//}5 P' E! v* Z H% v% R
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之3 }4 H9 U+ d8 P8 X5 n5 d- P# n
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
Q( h) d1 l3 y' c; P. O2 W[color=rgba(0, 0, 0, 0.749019607843137)]{
i# \7 o$ w- J! O+ Z" p# I[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;# u1 B8 W0 S# q+ e" Q
[color=rgba(0, 0, 0, 0.749019607843137)]}6 @8 p. X: Y; q' F& x
[color=rgba(0, 0, 0, 0.749019607843137)]1
5 A' E2 [0 D0 ~* W" R[color=rgba(0, 0, 0, 0.749019607843137)]26 ]& o8 }* E3 [8 |
[color=rgba(0, 0, 0, 0.749019607843137)]3( n9 o$ s$ Z/ A
[color=rgba(0, 0, 0, 0.749019607843137)]4
" p% _- ]. U, e0 V8 W[color=rgba(0, 0, 0, 0.749019607843137)]5! A5 V: d" p# U8 R5 a {
[color=rgba(0, 0, 0, 0.749019607843137)]67 U4 \9 S+ r" Y/ k t
[color=rgba(0, 0, 0, 0.749019607843137)]7
E% s* B9 n& l! z3 C' R5 M1 _[color=rgba(0, 0, 0, 0.749019607843137)]8
; L7 a; W3 l' @4 d[color=rgba(0, 0, 0, 0.749019607843137)]9. r# y# G6 U" @. r
[color=rgba(0, 0, 0, 0.749019607843137)]10& p' f2 s7 W- v. j6 w+ f+ @! k
[color=rgba(0, 0, 0, 0.749019607843137)]118 e/ u1 t) M/ S( P# g6 E6 S
[color=rgba(0, 0, 0, 0.749019607843137)]12
6 n' U* K# m, Q: H8 m, t[color=rgba(0, 0, 0, 0.749019607843137)]13
5 d+ \# |3 ?5 D- I$ P. ?; {[color=rgba(0, 0, 0, 0.749019607843137)]14- X/ f' X: P6 u: n3 n8 D1 b
[color=rgba(0, 0, 0, 0.749019607843137)]15
- x: @+ N* B2 R) R. @' T[color=rgba(0, 0, 0, 0.749019607843137)]16( Q1 Z! T. h" z2 A% w Y
[color=rgba(0, 0, 0, 0.749019607843137)]17
4 S( r% E- E0 u[color=rgba(0, 0, 0, 0.749019607843137)]18: ~) Q5 O2 Q/ I
[color=rgba(0, 0, 0, 0.749019607843137)]19
% ~7 H) M/ j9 `7 F) A" J" @2 Q[color=rgba(0, 0, 0, 0.749019607843137)]208 {4 ` L( f$ L7 k" G
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数( J8 H$ H- T! a& X/ f
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数" T/ x* C8 q- n$ n
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
5 a2 A! w4 F- T5 t- X# y! y, d[color=rgba(0, 0, 0, 0.749019607843137)]{
- R0 X. g; |8 j/ U1 e7 A[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点9 D/ N4 [4 g0 G! E6 b' G* ]
[color=rgba(0, 0, 0, 0.749019607843137)] {
$ a% v; N' M r5 O[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
+ e- ?0 O% t5 h+ B2 g[color=rgba(0, 0, 0, 0.749019607843137)] }1 j0 d2 h" b/ _8 @ f
[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空+ w( w1 K7 G5 v5 E
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
. m( D9 Q8 N! e' R: d1 t! m[color=rgba(0, 0, 0, 0.749019607843137)] {
5 _3 k- r, ]7 g; N' |% q2 D$ j8 D[color=rgba(0, 0, 0, 0.749019607843137)] return 1;( `3 j2 ]9 l* @% M) n
[color=rgba(0, 0, 0, 0.749019607843137)] }6 \! J9 h! i4 z [7 u
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
7 }0 j. ?$ G3 b/ w[color=rgba(0, 0, 0, 0.749019607843137)]}$ @9 t0 X# \' G0 l7 ~; ]
[color=rgba(0, 0, 0, 0.749019607843137)]1
8 G9 p8 @9 [! u* w' P2 C- A; u[color=rgba(0, 0, 0, 0.749019607843137)]2
. ?) e$ U+ }; b2 A, K6 F) b, |[color=rgba(0, 0, 0, 0.749019607843137)]39 u1 I' r5 @8 r! l/ J+ G6 z
[color=rgba(0, 0, 0, 0.749019607843137)]4+ j, w* G: L' o) d" y( f$ Z3 ]
[color=rgba(0, 0, 0, 0.749019607843137)]54 L8 I6 j. N& i
[color=rgba(0, 0, 0, 0.749019607843137)]6% j# d) H( V% b2 N- X9 K$ W
[color=rgba(0, 0, 0, 0.749019607843137)]7
" {4 D! s8 _' x- K[color=rgba(0, 0, 0, 0.749019607843137)]86 K- w9 T( ?: A. k
[color=rgba(0, 0, 0, 0.749019607843137)]9
Y' g l/ G/ G. @3 m4 @[color=rgba(0, 0, 0, 0.749019607843137)]10; ]8 P$ K% G! m3 }, U
[color=rgba(0, 0, 0, 0.749019607843137)]11. E$ I& ?2 ?: U* _' f# E2 M& q
[color=rgba(0, 0, 0, 0.749019607843137)]127 T5 M- E( r* Z, ~" r) k
[color=rgba(0, 0, 0, 0.749019607843137)]13; q: i* r$ \; b* U. G, v5 P7 s
[color=rgba(0, 0, 0, 0.749019607843137)]14
2 b) | m" ^6 N. a' B: U+ Y[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
2 b, z% e, ^5 c) I! y[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
, _; v6 r- N ~4 D, z[color=rgba(0, 0, 0, 0.749019607843137)]{; p0 M! f* K6 i5 A1 u9 v
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0
0 Q. g6 [. x* A4 D# E[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)+ J8 F4 f+ Z0 Z) ~
[color=rgba(0, 0, 0, 0.749019607843137)] {
0 u$ ~0 j/ _ j4 {[color=rgba(0, 0, 0, 0.749019607843137)] return 0;% L- i$ V' d) N& o4 n! D- @
[color=rgba(0, 0, 0, 0.749019607843137)] }
$ y! B8 V. b5 D& ^( O1 d6 ][color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树
2 Q* \1 S: e9 ][color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度* T$ y' Q/ C: Z, ~
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
# o; d" e5 W+ w( z t[color=rgba(0, 0, 0, 0.749019607843137)]
* \* l' o* R$ y& k& T$ J9 [/ N% Y* q: k: q/ q5 G a
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
. K! w+ G5 L q9 `" [* q* |[color=rgba(0, 0, 0, 0.749019607843137)]}1 y+ ^5 S# h9 p3 V
[color=rgba(0, 0, 0, 0.749019607843137)]1" C. U' v; `$ A+ B* {
[color=rgba(0, 0, 0, 0.749019607843137)]2
& E3 s* C: h3 p: x, K/ ?$ C[color=rgba(0, 0, 0, 0.749019607843137)]3
" e/ ^8 `3 }# S9 Q: r[color=rgba(0, 0, 0, 0.749019607843137)]4
; A+ ]* b# p; D' N7 s9 t[color=rgba(0, 0, 0, 0.749019607843137)]5
, h7 _2 L6 c$ S2 b8 X[color=rgba(0, 0, 0, 0.749019607843137)]67 s% _ ~* R- m: a, a: J
[color=rgba(0, 0, 0, 0.749019607843137)]7
7 U1 V- v- h6 ?[color=rgba(0, 0, 0, 0.749019607843137)]8
6 C) U3 R6 `/ ]/ o[color=rgba(0, 0, 0, 0.749019607843137)]94 P7 d: c1 G: [$ P3 ?, C2 @1 @
[color=rgba(0, 0, 0, 0.749019607843137)]10
( j9 F8 q" O5 z4 k[color=rgba(0, 0, 0, 0.749019607843137)]118 _6 a }4 {, _' S- K# D3 w U- O
[color=rgba(0, 0, 0, 0.749019607843137)]12) s+ a) m6 k+ F; s8 D) F6 y& G
[color=rgba(0, 0, 0, 0.749019607843137)]13
, [8 L! H$ H) w; `3 A[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
( x- Y& d( c: ^[color=rgba(0, 0, 0, 0.749019607843137)]
5 _/ v% @$ v% A, i
: B# V1 j$ l/ ?; |! Q! T[color=rgba(0, 0, 0, 0.749019607843137)]
8 A9 _" n+ S, t$ t
0 R# ]& ~6 W/ ~- l& [6 o$ ^* G( D[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
9 _3 n* |) [0 M1 G+ X) F" o[color=rgba(0, 0, 0, 0.749019607843137)]; Z) T$ J2 s" x* w' U4 ^
) A8 s9 A1 S& ]; n8 T, v5 V
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数, C& X& V+ z3 R" \$ U
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)$ O% e; B3 }! t0 X i
[color=rgba(0, 0, 0, 0.749019607843137)]{: q9 U }: R0 @& I/ P7 h8 T
[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);- }+ |/ n4 S m' L; `, S( \7 o
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)5 n$ Q! W' T7 k: O& ?
[color=rgba(0, 0, 0, 0.749019607843137)] {$ ]) [4 X, d, k
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;) u/ Q/ n, g: j4 z3 D1 r
[color=rgba(0, 0, 0, 0.749019607843137)] }
4 R% ~+ M# ~9 |( f7 W[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)! E, L( l% O4 S
[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1); V0 h/ v* Q9 d8 a
[color=rgba(0, 0, 0, 0.749019607843137)] {
' x/ q# p. X/ r! V* m[color=rgba(0, 0, 0, 0.749019607843137)] return 1;6 t2 l% u* z. f' X* O5 k$ |
[color=rgba(0, 0, 0, 0.749019607843137)] }. R5 X4 J: `! w4 x" I0 [
[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层
. Z6 A9 j: f/ S7 B[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);. I3 C/ t) w1 M; {- S
[color=rgba(0, 0, 0, 0.749019607843137)]}
2 v6 I0 H; F! G[color=rgba(0, 0, 0, 0.749019607843137)]18 l5 K6 Q* w+ ?6 G# C
[color=rgba(0, 0, 0, 0.749019607843137)]2. X; v( |: X& d' y! Y
[color=rgba(0, 0, 0, 0.749019607843137)]33 `; j% v+ R3 r# y
[color=rgba(0, 0, 0, 0.749019607843137)]4
/ C( |! t$ M% i S/ G; s/ q# b[color=rgba(0, 0, 0, 0.749019607843137)]5
4 i- j- f9 O0 t4 Y4 @; e; R9 a[color=rgba(0, 0, 0, 0.749019607843137)]64 `# d+ B- a% `' v! B: {6 @3 t* @
[color=rgba(0, 0, 0, 0.749019607843137)]7
8 {" ~) r U! _. U[color=rgba(0, 0, 0, 0.749019607843137)]8
# P/ z) Q/ N' N[color=rgba(0, 0, 0, 0.749019607843137)]9
- L- K. F5 B @/ E$ S. t! K[color=rgba(0, 0, 0, 0.749019607843137)]10
( ]) n( U$ } G8 Z% Z( a0 i[color=rgba(0, 0, 0, 0.749019607843137)]11* \3 O4 g6 z. k3 E3 U v4 z2 d4 u" s
[color=rgba(0, 0, 0, 0.749019607843137)]12. G o1 j# O) `- ?/ @! ]' U& A5 w
[color=rgba(0, 0, 0, 0.749019607843137)]135 K# s7 R5 Z6 u' T; {, U4 t
[color=rgba(0, 0, 0, 0.749019607843137)]14
7 z8 B/ P0 X0 X! O[color=rgba(0, 0, 0, 0.749019607843137)]15
2 Z3 e5 Z4 Y: j: H' Z) r[color=rgba(0, 0, 0, 0.749019607843137)]16 R0 C2 s" F+ c# I5 u& j
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
. `9 F" k9 P7 n; \[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找2 [6 f0 R* l# E% }
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
# S0 O5 z, ?# b5 B V[color=rgba(0, 0, 0, 0.749019607843137)]{; d! c6 U# O5 V2 b
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
8 Q2 T* L* |. u5 s7 K, j/ N[color=rgba(0, 0, 0, 0.749019607843137)] {! h( U" f6 O/ \7 E
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;3 T6 w# i' R/ o9 d* D. s3 p0 ~8 u6 B& B
[color=rgba(0, 0, 0, 0.749019607843137)] }
/ l* G0 N6 a& a5 T[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)4 d$ ~" f) f) a
[color=rgba(0, 0, 0, 0.749019607843137)] {# Q) _) O5 [ k
[color=rgba(0, 0, 0, 0.749019607843137)] return root;1 r o% g7 I6 d3 g" l
[color=rgba(0, 0, 0, 0.749019607843137)] }
- B* l* Q2 s0 j& A' M[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
9 ~7 v1 D; d$ @( M& H; `! r[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);0 e& d: v2 h, ~: [
[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)7 z/ w# m7 e4 ?1 T* Z
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;0 P9 {9 Y' l- L5 C. N0 D& ]
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树/ c1 B; |9 Y9 Y% K0 ?
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);1 ?% Z3 W$ C% {* u0 g
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
% j/ j0 L# n9 [( ^' C) y[color=rgba(0, 0, 0, 0.749019607843137)] return rret;) ?1 |+ }7 k0 ` O& j! j& k" |
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
`4 ~+ y: D8 j+ L: h" {[color=rgba(0, 0, 0, 0.749019607843137)]}
# n6 ?6 ]4 w1 y, c6 [2 n[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
% Y( O8 i- [% R3 `- [[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
1 ]1 z- R% _( C; F5 b[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
6 y6 `# I. s3 I0 c
7 T+ K: W! j, b" b7 a. y4 H% R0 b7 z/ C6 U) X. c6 T& o7 G( j
[color=rgba(0, 0, 0, 0.75)]
6 V$ Q/ u" V- r) `9 K; n
2 I7 E8 d5 Q0 D0 S$ P% _
( h' n3 v! K0 \$ F, ]
+ W) d5 r! t+ f8 I0 M |
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
