【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历! Y$ E6 i8 R0 f, |% }
- {! d" e, B# I/ ^$ `[color=rgba(0, 0, 0, 0.749019607843137)]文章目录4 |7 _6 D3 ~5 e- [7 L6 }9 I1 i
[color=rgba(0, 0, 0, 0.749019607843137)]前言! h3 ^. M ?: B& U, k
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
1 W% c! A0 ]) a: j6 d[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
( x: T5 ]6 P" N4 M1 Q! C) ~+ u[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
- I" T4 _* F; j- o- h& Y# K% i9 q[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小 W8 ?- |2 d: N; E% ?6 J
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
/ e' Z8 P+ @3 b/ b! h[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
+ \0 r- f/ i' H/ P+ H[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数8 ^& m: t D: `8 J
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
$ b6 x, }/ k1 A1 ~, V$ Q$ {; U[color=rgba(0, 0, 0, 0.749019607843137)]前言4 s" G+ g7 j2 D
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。& G/ `- O# L- O; t9 k
[color=rgba(0, 0, 0, 0.749019607843137)]
" {- h% z. N0 O r @
: n& r4 @1 x4 L: V7 E2 i; h[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
4 I/ T3 P2 ^3 w' l! j[color=rgba(0, 0, 0, 0.749019607843137)], B4 V" ^3 b) v1 c( U
4 n2 r& G, b( p1 F D: N% e% @1 J[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：
+ w( o& T* P4 y. y. Q; R z6 A. j[color=rgba(0, 0, 0, 0.749019607843137)]% ?+ z+ M( J' _3 }3 y
7 ]+ V4 t! F7 F5 {5 K[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树
# m" c$ I# j: P5 O0 ?[color=rgba(0, 0, 0, 0.749019607843137)]
) `: R0 M/ X/ Z9 Y* P- D
$ ?/ h/ ^) @4 n[color=rgba(0, 0, 0, 0.749019607843137)]
; @0 [7 h3 w6 o# G4 u, f0 g
9 k: C( X3 ^/ S8 W" V[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树/ U- o. H! {; ]
[color=rgba(0, 0, 0, 0.749019607843137)]; b# S: T6 s; z
; W$ s1 Y$ j& ~& S[color=rgba(0, 0, 0, 0.749019607843137)]
7 i# C0 x* Y6 S$ b3 X. O+ \+ x9 K$ X6 w+ }
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
: [3 \8 N p; N/ N$ y) H[color=rgba(0, 0, 0, 0.749019607843137)]
5 Y' O' E4 R& {* Y$ `& H8 F) f' Z/ k- W! v# ?4 ~) K) \
[color=rgba(0, 0, 0, 0.749019607843137)]4 ~2 i- w4 E0 p) y+ l% u+ _
0 R& b6 l3 h* s+ l
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
6 d' |0 ?0 B4 |+ p% p! k[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之
: W! M9 j$ A+ l0 C; p3 ^9 U4 E[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；
+ }/ e! j& L+ @, M7 F: c- f[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
' k- n6 `" S# {: Q[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；% t* ~. L0 _" G
[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；
: C! \2 e6 d u/ ?8 T; v7 Q4 c[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；" w+ H% u$ p+ a( p8 |4 Z7 K
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
/ @; w- S/ J* @/ F2 \( y& ?[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
, |& f( b+ }$ I. c+ e/ \6 }) v[color=rgba(0, 0, 0, 0.749019607843137)]" Q% P% d: p$ F$ D% |/ G; Q
8 L" x9 ~# W% m5 i' G# k/ N
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
; @$ T: h7 i( v! g1 Y[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1/ E# l) N3 C$ w3 k2 ~
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
# R3 O' S) A" O5 B& Y! z[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>" Y- P! f/ B& R7 S2 T9 m+ k; U l" H% x
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
. d: B/ h) O2 p3 ?[color=rgba(0, 0, 0, 0.749019607843137)]
% \# {! N# W4 q8 r+ D3 M/ C* b- H; v* c5 |
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;
4 N7 e4 \" P [& k* a) @[color=rgba(0, 0, 0, 0.749019607843137)]* ~! }- W# T; S0 Q/ Q
( U: H9 n: G9 q- c$ `# d8 t4 s
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体9 t: A6 t0 E+ @" w3 e- |
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode/ l* n8 e$ O: M/ [3 o' [
[color=rgba(0, 0, 0, 0.749019607843137)]{8 z% D( f% o5 I7 Q
[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;6 @2 L( ^5 O# D. y3 A
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;# ^) ~5 {. J: S, |$ v- ~6 K
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
# E, n& s* A+ f. i4 T[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;' W. O5 \: { m. L4 h
[color=rgba(0, 0, 0, 0.749019607843137)]
0 @+ y3 u% t: |! N, b/ ?, C/ _! S" C! y2 j
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
2 Z# k+ N* {/ _: g: i; l[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
" n! \ T% v5 @9 N[color=rgba(0, 0, 0, 0.749019607843137)]{
( g1 o" T5 i: B0 n[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
$ l4 z, s0 l, O4 v, Z: X[color=rgba(0, 0, 0, 0.749019607843137)] {
% ^1 }2 z, i& Q0 [& m* {9 Q7 G[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");: `& s$ `2 J. Z4 W" u
[color=rgba(0, 0, 0, 0.749019607843137)] return;
& d, |# Z9 p( Z[color=rgba(0, 0, 0, 0.749019607843137)] }! @! o6 q, C0 N }; k- Y. ^8 Y
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
/ k t8 o6 J9 X8 P, [9 L[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
. A0 ?/ g, z8 O[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);
# J* _1 T2 f: a) Q) A0 @[color=rgba(0, 0, 0, 0.749019607843137)]}
. M: y( V/ X( I) K6 ~[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
, }. j: b4 U7 w- m( ]0 v[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
$ n% r& Z R7 @5 ^[color=rgba(0, 0, 0, 0.749019607843137)]{) w6 r3 o7 p% E4 z+ J! q+ x
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
S/ M) s1 h! y8 C" ]' a3 O[color=rgba(0, 0, 0, 0.749019607843137)] {) I0 t& `' U- c+ C4 j
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");: p2 e) v5 z6 \ R- p* C# V0 Y
[color=rgba(0, 0, 0, 0.749019607843137)] return;* R) d5 N9 X4 A j' V4 p; A9 i' g
[color=rgba(0, 0, 0, 0.749019607843137)] } I I3 g# I4 K) O3 Q/ X
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
+ b. v) ^ J. u u) w[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);8 j% p- S" A$ q+ A, [2 i8 X; ~# c
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);! l2 i3 R# P0 z7 R. _9 Q. R4 M
[color=rgba(0, 0, 0, 0.749019607843137)]}
1 Y) I+ o6 f& z% {' f8 l) l7 y[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历- d% |7 ]9 e6 m( n8 Z) a! s
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)
, l6 U' A6 V& ]+ B+ L[color=rgba(0, 0, 0, 0.749019607843137)]{
! z! S- l n, V4 d# R! [$ E[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)5 {5 D! @* h1 X* e
[color=rgba(0, 0, 0, 0.749019607843137)] {
o* M! j2 S! @( o; _% N9 s[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");& S( ~1 T- D5 R$ X
[color=rgba(0, 0, 0, 0.749019607843137)] return;
7 e+ R" n0 g' X q: Z% ~$ Y! M/ ?5 `[color=rgba(0, 0, 0, 0.749019607843137)] }
. i4 Z8 g) K) b$ ~8 o[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
- O7 b& Z/ n* }. c# s[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
$ k8 H9 ~" ?! t. }# ]+ D[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);3 r: H9 L8 }) X5 ^' M4 h
[color=rgba(0, 0, 0, 0.749019607843137)]}/ m8 \3 e8 X, f' h- T
[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构8 l% E4 `" y& D0 X. P0 o
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()1 g: J7 ]# h9 {9 T
[color=rgba(0, 0, 0, 0.749019607843137)]{0 y* f, r$ |' p& B* u
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
1 m5 X5 Z. b6 ?+ f4 S% F- |4 G; ~, d[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
; b; c% [! C+ U5 r7 l/ `7 c[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
$ D x+ A7 k K! U[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));1 `4 R+ E6 M; J F
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
% g' V) L0 C T$ n1 j; \[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
5 p: f U" I- w( E# T! z, r[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);7 i+ \, E8 P" N0 J
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));7 g$ V& Y' b# k0 z$ f' X' I4 X
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);9 ^3 G7 x: D% U, ]
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
0 M# S& c5 X$ M& w9 G- _[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);8 u# A0 h o0 h8 X6 K& m
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));5 s- _; o; ~9 M" I
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);) a) F) |7 @- i; v2 \
[color=rgba(0, 0, 0, 0.749019607843137)]& Y4 | K+ j9 o& y: W/ `5 q
& E: e6 f8 W1 H[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;: O) u. K: V, M- _) o
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;3 T/ T$ D5 o4 b- {" O
[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;. ~$ T$ _9 j5 x9 U% O2 B2 |' e) O
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;0 O- C/ m; \2 H
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
' h# [) X2 L3 J o( B( E# X[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
% S( }, t9 V; L4 V6 E[color=rgba(0, 0, 0, 0.749019607843137)]
3 r; Q: p/ G) p2 K" \' Z1 R
u8 P: Q, z+ V8 O+ h3 o8 G9 U[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
$ Y' y" {, K. ]! e[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;, o2 n+ h% g) m' d' P8 q
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;7 _0 I+ u# ^0 G1 b
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
! c7 ~: c& ]8 B8 k% [[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
! v: M( F8 [& @4 o[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;7 Z( I7 h% |% r
[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;2 M8 Y. H4 v; O7 G' r
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;4 N% O1 Y9 ]* z9 N: l8 p
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;8 z, Z: p6 S/ T5 h3 W& O- D- f% X
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;* F: d8 S! g) ]* h, s0 C6 B& q
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;! n, ~7 c7 j3 Z* W
[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
7 u# V4 w+ v3 ?0 k[color=rgba(0, 0, 0, 0.749019607843137)]
) E, _( a# y: n8 T1 j6 \: F: `, h) V- x* i
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;& d6 O* `1 R3 u8 B L5 W& n
[color=rgba(0, 0, 0, 0.749019607843137)]}3 q7 _1 T$ D! e
[color=rgba(0, 0, 0, 0.749019607843137)], B: h W. O- c6 L' P( W
! S: n6 i$ e) C- a9 r8 q& ~6 H+ q
[color=rgba(0, 0, 0, 0.749019607843137)]int main()8 i/ _* X: Z5 T H& t( r! i9 ^# s
[color=rgba(0, 0, 0, 0.749019607843137)]{1 f( j \2 E( T6 Z- @' ]4 z
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构) |& `) ^6 y, H3 M8 M6 a" [
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();
( Y! K& h, t! I1 I2 r; g* Z[color=rgba(0, 0, 0, 0.749019607843137)]
8 [% i% i$ B! E0 H7 S
# P1 u! w: Y+ U[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历
& N, g: @( r. P4 E7 O. r( @# x# I[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");+ R( ^, u* n7 G2 Q& O
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
, B+ K; i8 `% H1 D3 s' a" V[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");$ o3 H8 e. r6 h' T( T4 V! d$ m( m
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历' n) ^8 A8 D+ H& c. w. f8 \6 B
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
6 U/ b% _" k5 a6 j/ X+ G[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);% D2 X$ w* a+ G& r
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");# l& V6 p# j/ a i7 H5 i( m
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历( j g: l5 a+ w& L4 D
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
! q8 G9 ^% A, S/ e! \4 \3 }[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
- y' V- e: e+ D) q" a[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
( ~5 e+ g1 ^+ d" ^) m& z1 V[color=rgba(0, 0, 0, 0.749019607843137)]
5 g) H* ]; {. [0 O4 H6 k9 g. S9 j
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
. q/ i7 c8 n9 m( ~+ f/ ~+ n[color=rgba(0, 0, 0, 0.749019607843137)]}
! @! e5 b8 H. A9 B, _9 J0 T2 c" x[color=rgba(0, 0, 0, 0.749019607843137)]1
/ h# {3 Z) H, Z[color=rgba(0, 0, 0, 0.749019607843137)]23 r7 g& S9 s! r9 G- S! w* ]- a6 B
[color=rgba(0, 0, 0, 0.749019607843137)]3
: g3 q1 t4 o6 i# Q; {[color=rgba(0, 0, 0, 0.749019607843137)]49 l% P- G8 _1 X' T
[color=rgba(0, 0, 0, 0.749019607843137)]5
$ l8 P: h8 y& f8 s u' e9 C[color=rgba(0, 0, 0, 0.749019607843137)]6
+ J8 o' H7 b4 P4 |$ s[color=rgba(0, 0, 0, 0.749019607843137)]7
, M9 p0 y% s; i7 m J$ ][color=rgba(0, 0, 0, 0.749019607843137)]8/ K4 A- X/ C# Y& S$ g
[color=rgba(0, 0, 0, 0.749019607843137)]9
: f6 ]2 x: h o8 y3 N[color=rgba(0, 0, 0, 0.749019607843137)]10+ {0 ~3 Z* V7 b/ O
[color=rgba(0, 0, 0, 0.749019607843137)]11
7 ~+ Z+ ]0 G$ ^" w[color=rgba(0, 0, 0, 0.749019607843137)]12
9 J3 ^4 B& f0 V: {/ ]: _3 t% A) R[color=rgba(0, 0, 0, 0.749019607843137)]13" `! {+ `0 m8 m4 `
[color=rgba(0, 0, 0, 0.749019607843137)]14
- Q- v! L3 V7 F' s# r; t2 J[color=rgba(0, 0, 0, 0.749019607843137)]15
5 j& ~, q+ @* ?; D* X[color=rgba(0, 0, 0, 0.749019607843137)]16
f2 Y% ~, p Y T4 p+ }" L[color=rgba(0, 0, 0, 0.749019607843137)]17' l. A/ l0 d6 r5 Y
[color=rgba(0, 0, 0, 0.749019607843137)]18
" P* ^* W, H2 D: H[color=rgba(0, 0, 0, 0.749019607843137)]19
9 ]" Z4 z% y3 S) E+ Z# I1 @ k[color=rgba(0, 0, 0, 0.749019607843137)]20
4 s( {( N, o" H) ^[color=rgba(0, 0, 0, 0.749019607843137)]21
4 y: m6 L1 k/ _; I[color=rgba(0, 0, 0, 0.749019607843137)]228 N' \ |( O; T- C. |, _
[color=rgba(0, 0, 0, 0.749019607843137)]23
1 c5 A- G, B" S: h- Y0 ^% V) J' L[color=rgba(0, 0, 0, 0.749019607843137)]24# ^4 X/ t4 E, Z* t* s' ?5 {% C
[color=rgba(0, 0, 0, 0.749019607843137)]25
) z- J( ~/ j" i) p( b( B. w* y: E4 y[color=rgba(0, 0, 0, 0.749019607843137)]26
2 I. J6 O- d5 n( L[color=rgba(0, 0, 0, 0.749019607843137)]27
" ^/ r2 [; t/ z9 ^9 h0 ~' q[color=rgba(0, 0, 0, 0.749019607843137)]28- M6 Q" J4 G: n, @! R, x5 w+ H
[color=rgba(0, 0, 0, 0.749019607843137)]29
( h6 p0 I$ f& W+ |7 @' G; C" p[color=rgba(0, 0, 0, 0.749019607843137)]306 E! R/ H; h4 V2 E$ N' R
[color=rgba(0, 0, 0, 0.749019607843137)]31: E# e# o$ g; [! o
[color=rgba(0, 0, 0, 0.749019607843137)]32
+ N' F! s1 @& _8 w[color=rgba(0, 0, 0, 0.749019607843137)]33" S% t t0 s9 I
[color=rgba(0, 0, 0, 0.749019607843137)]346 r$ E2 w6 F$ Z- A7 H& U0 n) w
[color=rgba(0, 0, 0, 0.749019607843137)]35
9 A% V- b' s, R, l[color=rgba(0, 0, 0, 0.749019607843137)]36: Z( k! [3 L: o& D0 w
[color=rgba(0, 0, 0, 0.749019607843137)]37
/ `- f% X" A# [- M0 Z[color=rgba(0, 0, 0, 0.749019607843137)]38
# I& [2 L$ L+ `[color=rgba(0, 0, 0, 0.749019607843137)]39
9 \# G5 r+ s2 p7 m7 ~( Q3 V[color=rgba(0, 0, 0, 0.749019607843137)]40
6 U7 f2 u) ?6 n- o1 x: Z- o1 c[color=rgba(0, 0, 0, 0.749019607843137)]41
) O* ?9 ?" U7 k. g6 V[color=rgba(0, 0, 0, 0.749019607843137)]42
2 G8 _" z: e" N$ w6 t[color=rgba(0, 0, 0, 0.749019607843137)]43( H+ C7 h/ {( \& s1 Y
[color=rgba(0, 0, 0, 0.749019607843137)]444 [# B% {! |2 J* ^& k: h6 P, G
[color=rgba(0, 0, 0, 0.749019607843137)]45! W! R# i$ y! r+ Z
[color=rgba(0, 0, 0, 0.749019607843137)]46
5 G1 U, Y0 n+ ]5 R[color=rgba(0, 0, 0, 0.749019607843137)]47& }9 Z5 o7 i0 O1 g6 d
[color=rgba(0, 0, 0, 0.749019607843137)]487 M% C% b& P$ L- a3 Y! F3 @
[color=rgba(0, 0, 0, 0.749019607843137)]49
* C4 k9 { t) X( C! B[color=rgba(0, 0, 0, 0.749019607843137)]50
( v A4 J, Q9 z4 g M[color=rgba(0, 0, 0, 0.749019607843137)]51
! s& M K A8 [" G. O- R3 g[color=rgba(0, 0, 0, 0.749019607843137)]52. L' Y0 Y n, Z3 @% P% |3 n# I
[color=rgba(0, 0, 0, 0.749019607843137)]53
5 @2 D1 o4 ~# L: S* s[color=rgba(0, 0, 0, 0.749019607843137)]54
* N6 q( O9 s0 H5 s8 ]5 }[color=rgba(0, 0, 0, 0.749019607843137)]55. W9 v9 z# C2 Q5 y$ I) T
[color=rgba(0, 0, 0, 0.749019607843137)]56% M. b0 N6 g/ ^4 A* \, Z
[color=rgba(0, 0, 0, 0.749019607843137)]57
9 U( L! a& |! B7 `" a[color=rgba(0, 0, 0, 0.749019607843137)]58% \4 Q0 D5 l. e+ Q- v
[color=rgba(0, 0, 0, 0.749019607843137)]59
! k. T6 ?' }9 M! n[color=rgba(0, 0, 0, 0.749019607843137)]60
0 B, g$ h+ z2 L% _[color=rgba(0, 0, 0, 0.749019607843137)]61' O4 v- w* |1 G: R- f# I. Y
[color=rgba(0, 0, 0, 0.749019607843137)]62
9 C# X9 ]" U" {0 ][color=rgba(0, 0, 0, 0.749019607843137)]63) E* Q" c3 } ?7 c1 o* h8 X4 w
[color=rgba(0, 0, 0, 0.749019607843137)]64& e" ]( ]' u+ h0 J4 u
[color=rgba(0, 0, 0, 0.749019607843137)]65
$ N% K6 g( Y- Q" r V5 N2 F[color=rgba(0, 0, 0, 0.749019607843137)]66
/ T7 B( L& D- D5 v/ F[color=rgba(0, 0, 0, 0.749019607843137)]67
$ a! A) {0 H: D) u[color=rgba(0, 0, 0, 0.749019607843137)]68
. ]" _. d8 C/ Q. q/ I- ?2 D[color=rgba(0, 0, 0, 0.749019607843137)]69
2 g7 I: ~8 ]6 }& e" B2 H- E[color=rgba(0, 0, 0, 0.749019607843137)]70
% f6 J* {+ W% Y[color=rgba(0, 0, 0, 0.749019607843137)]71* B/ e. G- j1 N- ^# y3 E
[color=rgba(0, 0, 0, 0.749019607843137)]723 [9 f7 e. V2 V7 Q/ u, k2 [
[color=rgba(0, 0, 0, 0.749019607843137)]73% l6 D. H5 S; Q3 R4 Y8 |
[color=rgba(0, 0, 0, 0.749019607843137)]74- A' `! l6 @6 O: K
[color=rgba(0, 0, 0, 0.749019607843137)]75! ?% h9 P0 ^5 p7 ^$ f5 [7 C
[color=rgba(0, 0, 0, 0.749019607843137)]76! N1 \+ i/ L- l$ w
[color=rgba(0, 0, 0, 0.749019607843137)]77
$ a0 X& n) ^+ t* E& P9 Z% \[color=rgba(0, 0, 0, 0.749019607843137)]78
0 T8 [7 [4 H, } l# C[color=rgba(0, 0, 0, 0.749019607843137)]793 Y9 ]- }* c8 B( p* @
[color=rgba(0, 0, 0, 0.749019607843137)]80$ T1 Y7 J" G) U4 G; z
[color=rgba(0, 0, 0, 0.749019607843137)]81+ W U: J6 J0 p) a& _
[color=rgba(0, 0, 0, 0.749019607843137)]820 y7 c, N0 `8 R8 e
[color=rgba(0, 0, 0, 0.749019607843137)]83
. C7 t8 @1 ~ ]* M[color=rgba(0, 0, 0, 0.749019607843137)]84# C2 J' w# L* m: T X7 Q! M' l
[color=rgba(0, 0, 0, 0.749019607843137)]85
9 d6 E* K; E5 l: d! M }[color=rgba(0, 0, 0, 0.749019607843137)]86
, A! S. Q$ f3 U R" w% g[color=rgba(0, 0, 0, 0.749019607843137)]87
! _- N& B7 l' B) r[color=rgba(0, 0, 0, 0.749019607843137)]88+ i5 t# r6 ~$ e D0 ?4 ^. u
[color=rgba(0, 0, 0, 0.749019607843137)]89
E! o9 \3 Q: D' z[color=rgba(0, 0, 0, 0.749019607843137)]90
4 D, U) d2 ~) @2 {* q0 m[color=rgba(0, 0, 0, 0.749019607843137)]91
, K, ~; B) M: l$ U[color=rgba(0, 0, 0, 0.749019607843137)]92! S& V, q# I8 C; @1 ~. u; N4 g
[color=rgba(0, 0, 0, 0.749019607843137)]935 w+ y5 D3 \+ E
[color=rgba(0, 0, 0, 0.749019607843137)]94
% ~! S' x) R' Y. Y8 `[color=rgba(0, 0, 0, 0.749019607843137)]954 ]/ G- t; V3 z9 r4 H* p# M. C
[color=rgba(0, 0, 0, 0.749019607843137)]969 p- E" V- K6 }& l
[color=rgba(0, 0, 0, 0.749019607843137)]97
: q2 T$ l$ z/ u8 @# G" S3 C! j0 d[color=rgba(0, 0, 0, 0.749019607843137)]98
. k5 t3 G: _8 x4 o! y' T[color=rgba(0, 0, 0, 0.749019607843137)]993 n8 U4 g A) h6 l! D. t Q& F! y
[color=rgba(0, 0, 0, 0.749019607843137)]100
$ b, N# X7 J2 p$ ~& Q4 g[color=rgba(0, 0, 0, 0.749019607843137)]101
( @6 e r8 [# W[color=rgba(0, 0, 0, 0.749019607843137)]1022 c8 Y1 x3 [5 }3 S! x- ^
[color=rgba(0, 0, 0, 0.749019607843137)]103
. k( T' z u" y) ?[color=rgba(0, 0, 0, 0.749019607843137)]1040 _% y2 E! v7 ~7 S$ D0 j5 m. T
[color=rgba(0, 0, 0, 0.749019607843137)]105
3 e, a$ ]1 }& I) ]0 u[color=rgba(0, 0, 0, 0.749019607843137)]106
4 X+ J7 V! b- s3 d[color=rgba(0, 0, 0, 0.749019607843137)]107! }! E$ ~. K5 z- N& B
[color=rgba(0, 0, 0, 0.749019607843137)]108; `( D$ x _ t! ~) v
[color=rgba(0, 0, 0, 0.749019607843137)]109- v8 s2 b9 v9 o" f" T" ?
[color=rgba(0, 0, 0, 0.749019607843137)]110
: S" f6 q) F! i& ][color=rgba(0, 0, 0, 0.749019607843137)]111
0 j* H* H j' D/ o[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
9 T* k) P% }. _! H) G[color=rgba(0, 0, 0, 0.749019607843137)]
' b: b( R$ Q/ B% p) ]1 @
" N$ z; c0 z. J[color=rgba(0, 0, 0, 0.749019607843137)]
' |8 c6 ?4 }! t) |) g! e& S! X, c- v& U. S0 {) L: _. `
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
* w: }3 d: o8 y* o7 P$ M, q4 `. f[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
2 ~4 P: S. k6 A9 W[color=rgba(0, 0, 0, 0.749019607843137)]
2 ?8 w" ^- }0 J! w
1 R/ z& E- m3 v3 i6 O4 q[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
' i9 t: b& W/ }" N C6 y[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量7 Y4 y& L1 q; T6 h3 \8 B$ K9 z
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;; D0 g5 _' p; Y7 e( B m {
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
! D- A# m- ^8 a* p[color=rgba(0, 0, 0, 0.749019607843137)]//{! F" x4 b9 q8 R( N
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
+ Z( S" J0 x1 Z- q7 T7 m[color=rgba(0, 0, 0, 0.749019607843137)]// {7 O$ R v! }8 h; i
[color=rgba(0, 0, 0, 0.749019607843137)]// return;
- G+ L6 y8 k' o$ n[color=rgba(0, 0, 0, 0.749019607843137)]// }3 S6 e0 S* u8 T3 G! e
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;
& \: Y* t; }/ q. k% R[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
+ R* R2 ^5 L) Z0 t' S7 ~[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);6 L- [) [0 M2 ?+ P
[color=rgba(0, 0, 0, 0.749019607843137)]//8 ~' M% E+ e) P2 @$ c6 J6 v
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
9 N9 H& @) s& u8 a& Z[color=rgba(0, 0, 0, 0.749019607843137)]//}
2 u: N4 B+ \& v2 G: |* ?[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之& U4 e4 [- X& C4 _6 W0 D
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
' T( ?0 P. p# \2 r[color=rgba(0, 0, 0, 0.749019607843137)]{
7 q% U' O3 {. k5 t5 B; b[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;8 U0 S) H& |/ r0 g, j) v0 v
[color=rgba(0, 0, 0, 0.749019607843137)]}- g& z1 A+ z8 J
[color=rgba(0, 0, 0, 0.749019607843137)]15 h. I8 m5 Q& `9 j% B! N, Q
[color=rgba(0, 0, 0, 0.749019607843137)]2
2 m3 y8 B. a9 V. n9 `[color=rgba(0, 0, 0, 0.749019607843137)]3
7 w" c# e- `& n2 X4 j# z5 a! T[color=rgba(0, 0, 0, 0.749019607843137)]4
" C( e4 ~8 J4 {+ `5 u[color=rgba(0, 0, 0, 0.749019607843137)]51 K; k5 p+ V0 ^, L$ Z
[color=rgba(0, 0, 0, 0.749019607843137)]6- A. W. u O+ V) D/ p
[color=rgba(0, 0, 0, 0.749019607843137)]7
& Q) f3 s$ j4 y[color=rgba(0, 0, 0, 0.749019607843137)]8
1 J/ D/ y1 n( `" _ Q4 @+ u8 o2 ~0 D[color=rgba(0, 0, 0, 0.749019607843137)]9
( X5 n6 N/ A9 T) O6 g9 _& c4 y[color=rgba(0, 0, 0, 0.749019607843137)]10
8 d( b9 } ^( B8 l, ~[color=rgba(0, 0, 0, 0.749019607843137)]11; S5 i8 z1 C0 k5 v/ F, K4 V
[color=rgba(0, 0, 0, 0.749019607843137)]12- J3 ]- p! I6 ?* \6 m1 g
[color=rgba(0, 0, 0, 0.749019607843137)]13
3 d* p5 v2 \. i& w9 n& d[color=rgba(0, 0, 0, 0.749019607843137)]14* |3 O2 | B; Y5 d" A/ d
[color=rgba(0, 0, 0, 0.749019607843137)]15* q5 b; u2 A2 }6 j* w6 i
[color=rgba(0, 0, 0, 0.749019607843137)]16
9 J: \" i9 A) F e[color=rgba(0, 0, 0, 0.749019607843137)]177 h+ P. h( r. H: \, e
[color=rgba(0, 0, 0, 0.749019607843137)]18
0 c+ O" q6 }/ B3 ]' o: g V/ J/ {[color=rgba(0, 0, 0, 0.749019607843137)]196 Q- A. R1 z8 w0 Y# i" z8 X
[color=rgba(0, 0, 0, 0.749019607843137)]20
; Z! m5 D- H7 {4 `! }' ~" P' l$ |5 T[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数+ Q# [. A% J0 R( [; |9 K" k
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数" J. g) \; i& y6 t. H8 z( h3 N
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root); f& M. L1 |0 y7 s( E# A7 v7 [ E
[color=rgba(0, 0, 0, 0.749019607843137)]{: z$ z0 M* h3 {2 e: `/ @$ ~9 @
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点
# r/ z- j+ D/ D( c- h[color=rgba(0, 0, 0, 0.749019607843137)] {* a3 f" m2 {- G2 M
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;. i% S. `$ q4 |# |" ~4 |4 s7 c6 F
[color=rgba(0, 0, 0, 0.749019607843137)] }5 c$ \( j9 l. d, W0 ?8 z; A
[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空 C# I6 {2 P* R1 s1 b
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
4 j3 G+ \! f6 v0 d7 F[color=rgba(0, 0, 0, 0.749019607843137)] { q) y" k# A# u8 L# @) o2 s
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
8 Q) X. v6 S& n[color=rgba(0, 0, 0, 0.749019607843137)] }
+ h; S1 u' Q0 A5 G, A; M$ j1 e+ b[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
5 |# K N& H* V; `# \# f( C[color=rgba(0, 0, 0, 0.749019607843137)]}6 _$ `2 c: B1 H# ?
[color=rgba(0, 0, 0, 0.749019607843137)]15 T/ I0 F2 Q, w! l: K
[color=rgba(0, 0, 0, 0.749019607843137)]2) E1 w* Y! r* }* `
[color=rgba(0, 0, 0, 0.749019607843137)]3
V/ O/ q1 _$ V' b5 t/ t' s; _[color=rgba(0, 0, 0, 0.749019607843137)]41 B4 f$ S3 |+ a# _4 f0 g- m5 H2 U# o8 @
[color=rgba(0, 0, 0, 0.749019607843137)]5! i6 n. M$ C2 l' e4 B. a0 T* _
[color=rgba(0, 0, 0, 0.749019607843137)]6
0 ~$ Z) I9 h! S1 U( @[color=rgba(0, 0, 0, 0.749019607843137)]7
5 s$ y' R) x+ y[color=rgba(0, 0, 0, 0.749019607843137)]85 f1 d7 K6 W4 f) S, _
[color=rgba(0, 0, 0, 0.749019607843137)]9
" j4 p6 T F0 ^/ t1 Q[color=rgba(0, 0, 0, 0.749019607843137)]10/ [1 [) w& C& u2 _% l
[color=rgba(0, 0, 0, 0.749019607843137)]111 F; I5 a" O; k1 `+ F/ m2 |
[color=rgba(0, 0, 0, 0.749019607843137)]128 F& R5 s$ O7 W8 [3 O
[color=rgba(0, 0, 0, 0.749019607843137)]13' P2 p% ?- I8 K1 \' b
[color=rgba(0, 0, 0, 0.749019607843137)]149 ^- d* y' n+ L% A% a; B
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
7 Y; t- J! G. g. w9 j \[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
( R% D. O7 [2 F* X( D# y[color=rgba(0, 0, 0, 0.749019607843137)]{
2 ?: _/ e0 ?/ H1 `. a3 z9 P! W[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0- c: {* d/ h. M- S h& ~+ t
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)7 L' ~- R9 E* X
[color=rgba(0, 0, 0, 0.749019607843137)] {7 ~8 r0 n0 _9 q0 N( r
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
9 \& F. X- _3 Y( I g[color=rgba(0, 0, 0, 0.749019607843137)] }; p+ _$ s' P6 `0 N9 E. ~4 b: q
[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树
2 r0 @+ P0 X* x7 p[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
4 Z- N3 Q. @7 y" O" y! N6 u2 j9 k[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度
4 ?# e" {. S/ F" @/ P1 O[color=rgba(0, 0, 0, 0.749019607843137)]# E. T. D% z1 H$ M5 U+ A9 o
) T' S) \6 g) Z8 k; k1 `8 D# r8 N, t[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;
) s2 X, H& u6 H[color=rgba(0, 0, 0, 0.749019607843137)]}
& _$ g2 {) p" ^. g- k5 y% [[color=rgba(0, 0, 0, 0.749019607843137)]1" t+ H; X# a, q' n4 d# L) d% {7 g
[color=rgba(0, 0, 0, 0.749019607843137)]2
+ l) r' w* t9 r5 v[color=rgba(0, 0, 0, 0.749019607843137)]3. l- o2 \- v& B+ @# M; e$ k
[color=rgba(0, 0, 0, 0.749019607843137)]4 A: Z4 t! j! V/ I0 ^+ s# a; ^
[color=rgba(0, 0, 0, 0.749019607843137)]5
) `* F: @4 j, {0 O9 C9 `1 ^' X[color=rgba(0, 0, 0, 0.749019607843137)]6' q/ @9 X1 F7 T7 v0 o5 O) v: I
[color=rgba(0, 0, 0, 0.749019607843137)]7& j# s! W9 f8 r! e
[color=rgba(0, 0, 0, 0.749019607843137)]8
' @7 g% p$ T# l0 Q' J[color=rgba(0, 0, 0, 0.749019607843137)]97 k+ e7 o8 ^, j7 g5 U
[color=rgba(0, 0, 0, 0.749019607843137)]10. s+ k7 D. d5 S2 X' v
[color=rgba(0, 0, 0, 0.749019607843137)]117 x P; V% M6 \
[color=rgba(0, 0, 0, 0.749019607843137)]120 C9 D5 G) n" K8 S
[color=rgba(0, 0, 0, 0.749019607843137)]138 U2 F, ?1 L& }# v$ q& p
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
. l: [, ^9 L) b1 s5 F [! L[color=rgba(0, 0, 0, 0.749019607843137)]
. v. j" b) z- A; z; s8 Y* t2 Y2 r2 P4 ^& v$ \
[color=rgba(0, 0, 0, 0.749019607843137)]
! O- ~- t. O1 m0 x+ f, a7 Z; Q
) |7 W. K% k* G) S- {- s[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。$ D+ Y1 ]5 r/ r, m
[color=rgba(0, 0, 0, 0.749019607843137)]
- o; z# u$ C& Z6 ?. O& Z/ l% F" {7 |; ?* s
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数7 J9 @6 a* b5 B, ^( x
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
4 Q' P% A8 ~" I[color=rgba(0, 0, 0, 0.749019607843137)]{1 R1 _ Y0 {8 p0 S
[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);
9 l1 a1 g+ N* ` J7 @, R# B# X; u[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
& Y9 X8 b# o" }6 \7 c2 y: R& ^[color=rgba(0, 0, 0, 0.749019607843137)] {
( w% y) `& Y) E$ Q( @' f[color=rgba(0, 0, 0, 0.749019607843137)] return 0;1 X! `5 X/ w2 ]& x/ b
[color=rgba(0, 0, 0, 0.749019607843137)] }0 ~, |& R! q/ z* Y
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
. s9 z6 A0 j0 v- _8 B' c3 ~[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
9 Q8 N1 h1 [8 c: Y3 s' e[color=rgba(0, 0, 0, 0.749019607843137)] {
# o) `" @+ r9 d' H7 Y8 L2 F[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
* b' V' ]9 r7 R: \$ `+ g, K0 W[color=rgba(0, 0, 0, 0.749019607843137)] }3 E) e2 g5 G8 A
[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层! i' ~/ k8 ]$ ^
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
8 Z5 O0 N2 c* q6 r. d7 s[color=rgba(0, 0, 0, 0.749019607843137)]}. D7 A$ u8 Z# U: |* w2 V- N
[color=rgba(0, 0, 0, 0.749019607843137)]1" A* W- Q4 N9 ^$ g
[color=rgba(0, 0, 0, 0.749019607843137)]20 K3 K# v5 k% m. p& e
[color=rgba(0, 0, 0, 0.749019607843137)]3/ C! H& E9 H8 ~! y0 d$ q
[color=rgba(0, 0, 0, 0.749019607843137)]4' o7 b! G4 `# U2 X- z8 {& y
[color=rgba(0, 0, 0, 0.749019607843137)]57 J7 ~8 g/ B3 O# E/ |
[color=rgba(0, 0, 0, 0.749019607843137)]6% f8 C. l; W" m: L+ S4 Q0 N4 [0 E
[color=rgba(0, 0, 0, 0.749019607843137)]7& w2 u6 `; H+ r7 M. J6 M
[color=rgba(0, 0, 0, 0.749019607843137)]8
' j( e* ?+ x; R) L) b[color=rgba(0, 0, 0, 0.749019607843137)]9
. L0 @( s2 r+ V" [8 l[color=rgba(0, 0, 0, 0.749019607843137)]10' [0 I# P- b5 `5 }
[color=rgba(0, 0, 0, 0.749019607843137)]11
& {4 D# w* y7 J' b3 Z6 d0 m[color=rgba(0, 0, 0, 0.749019607843137)]12
8 q. b- U4 Z+ e5 W) r" Q3 y$ u% Z[color=rgba(0, 0, 0, 0.749019607843137)]133 W& H8 Q! R0 ]5 ^
[color=rgba(0, 0, 0, 0.749019607843137)]14
* n% q6 ]9 V# u0 F+ p[color=rgba(0, 0, 0, 0.749019607843137)]15
4 E! W9 t. E# H- M. K! m& e& G[color=rgba(0, 0, 0, 0.749019607843137)]163 |4 I1 w7 i) J
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找2 F0 p2 z. ?: H& k
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
# A; l, E7 y' x7 v[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
$ V) e% ?- F% u3 C[color=rgba(0, 0, 0, 0.749019607843137)]{
4 E& x7 F; R4 }1 W: |; N' R& F$ G[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL) r2 v0 e, s% ?$ R2 Y7 {1 c
[color=rgba(0, 0, 0, 0.749019607843137)] {
5 H* Q6 _& ~" W* F2 S# j5 s[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
4 |# [. q/ B( e; e& w[color=rgba(0, 0, 0, 0.749019607843137)] }
2 f; C+ _% y6 s[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)/ W" E& ~* J! R2 T
[color=rgba(0, 0, 0, 0.749019607843137)] {3 ^1 C1 t B4 D; Y3 R
[color=rgba(0, 0, 0, 0.749019607843137)] return root; b' t1 R" p/ B6 K
[color=rgba(0, 0, 0, 0.749019607843137)] }
; c1 O/ w& }. F! G7 {[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
3 c; ^( M4 L+ y8 N8 D1 S* T* W& x N[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
) n7 }8 G$ r3 W9 z5 b. S- K[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)+ z( O4 {. Q8 V+ Q ?
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;
0 k" t4 a% f1 H( D. b[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
) B1 a- g1 L! U8 d/ |! B u[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);
z% G3 d9 r: U: k4 T* t3 j( i! V[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
3 {. |9 P: T% _" \' [[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
' i3 p1 X' F5 _1 E- Q[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;( x* p# o% J5 L% g
[color=rgba(0, 0, 0, 0.749019607843137)]}4 o0 K& R! y$ ^9 Q' G/ ~( K
[color=rgba(0, 0, 0, 0.749019607843137)]————————————————0 P8 P/ V4 A5 K
[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
, U2 P; r" z2 q[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
; A) _7 h0 C1 r d0 Z' d
9 a$ h& r% u7 ^2 u% ^% v) w' v- j. \8 { @
[color=rgba(0, 0, 0, 0.75)]
* s, T, U. a# d5 T* m& z+ \. m) W2 L% S* \& E* X
+ j% d( S+ R' _8 s" n% O$ L! s7 L2 |
|
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
