【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历- o4 k6 A1 u9 z# N- @8 Z- z5 n$ T" K& W
/ I# h% m( q) N4 g[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
( z! G/ J2 A# `1 _: I2 [& x[color=rgba(0, 0, 0, 0.749019607843137)]前言8 ^; _0 s- S1 S2 C
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式& n4 @+ | O- x6 o
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
7 k6 U( o" x( t+ g1 B- ^5 c( `[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历* M: }; S' z* ]/ R6 f8 w' h8 m
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
" l$ p5 X t5 ^9 f p[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数+ `8 w5 F4 u$ \$ X3 a
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度* q# J: j/ c, T8 d# f
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数! J0 [, e7 H2 ]0 ~3 E5 E
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找* a1 h- X9 @* \
[color=rgba(0, 0, 0, 0.749019607843137)]前言
5 Q7 C: }% j% W, ^; L[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。& U3 b% E1 J8 Z& }2 B: t) f
[color=rgba(0, 0, 0, 0.749019607843137)]& j& ~" _( Z( ] Y- y! u7 x* I/ o
2 c% V% n5 m/ |: i6 o) S[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式) P: `6 M3 c4 U$ ~
[color=rgba(0, 0, 0, 0.749019607843137)]. z; [$ K, p" T; [" d; n5 k8 u9 ?
! x+ j! D6 U/ e[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：! ]4 }$ w. [' ^ ]8 @8 x
[color=rgba(0, 0, 0, 0.749019607843137)]
; ~- [$ {% D: G7 q1 y, s( a4 z' B9 O5 K6 M
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树4 H9 h& L* w' E. Q, T1 [" e
[color=rgba(0, 0, 0, 0.749019607843137)]: }8 D0 q. w4 Q6 [) x2 Z$ c5 [
% l$ P: S+ Y" ] x* Q; Z/ x
[color=rgba(0, 0, 0, 0.749019607843137)]' y! ~* E+ i" _5 \6 v4 A* E
2 Y3 h0 l9 M2 J, u; l9 F! O
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树: ]+ A$ _0 h9 Z+ u. ]1 V
[color=rgba(0, 0, 0, 0.749019607843137)]
$ ?. u8 a; L6 W/ J! W7 [4 z$ g
: a0 w; ^$ S# x; z" ~9 p[color=rgba(0, 0, 0, 0.749019607843137)]1 C- `" ^) q% E: d; u) I* C
2 H. s# k. `1 \ W* b% R: i# {
[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根2 G u" r9 B& I& y# T+ d
[color=rgba(0, 0, 0, 0.749019607843137)]% H3 T' ]$ W, N) s) D3 `; \
4 H$ a; W9 u' v3 L F# f[color=rgba(0, 0, 0, 0.749019607843137)]
2 m" k9 o: j+ J$ v+ E1 P! n% _9 I% J5 N$ J6 j
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）3 Q! v4 T2 C# n" x; s$ y, Q" N3 @
[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之. K/ j: d9 X: }0 W$ \
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；( S6 K/ {: o/ @; q, m4 A
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；
3 S* Y, F; o; Y) q% b7 F3 _% [[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
0 `; [" B; h- j4 T1 z[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；- I6 {; K2 W4 C* S
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
- M! e K1 U* T3 T: b0 _$ S[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；$ q/ M, u/ O6 t$ q
[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
2 X) V$ {8 Z# N3 g7 n[color=rgba(0, 0, 0, 0.749019607843137)]% K8 f: w1 b- P7 Z3 ^+ g7 d
& \/ E/ J0 N6 \- ?% j g[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历3 M# w: N! J, G
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1$ A2 _( D/ o. L
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>+ H) B- y& Y0 B5 ]# z1 C% t
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>
/ G) c( f8 z X5 _8 F" {& T3 M[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>- v8 o1 E, p: \' J. ]
[color=rgba(0, 0, 0, 0.749019607843137)]2 W7 R @$ a0 y3 Z. U3 F& Y( p
' T( R- |! {- f
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;. Q; l: M! g$ h0 w9 J
[color=rgba(0, 0, 0, 0.749019607843137)]! b& P3 p0 q) H; ~( x% z' ]4 z
, K( P) Z9 Y& u6 r' R! X" p% Q0 e
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体# `4 E! |5 U9 r3 L/ Y
[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode9 V( b9 z& P/ }& d; i/ H
[color=rgba(0, 0, 0, 0.749019607843137)]{
* r2 V/ }7 O- `[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;6 j7 E7 S1 ?8 p8 G" G! X5 ~
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;4 v _, e9 p1 n* p# U) i$ d9 \; k
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
9 o; Q2 g( `3 H2 q. L7 X0 l[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;: b- |- c& u" B, `& ?5 U; _
[color=rgba(0, 0, 0, 0.749019607843137)]
X3 i& @* n$ V* W& L* P+ j0 ~! W2 ^5 g% x
[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
) j% d* P- d! ~* X5 G[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
/ Y/ j1 s7 m* ^+ ~* e9 p1 u[color=rgba(0, 0, 0, 0.749019607843137)]{
^' n1 M0 \" U. E0 K, M/ \/ v[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
1 ~2 H2 d$ d F+ h1 E[color=rgba(0, 0, 0, 0.749019607843137)] {8 p L3 u$ u" f1 U% \. m0 H0 B
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");% r4 v& K% c' @& z2 c) I
[color=rgba(0, 0, 0, 0.749019607843137)] return;
! v' K6 B! U$ S2 m# [8 w[color=rgba(0, 0, 0, 0.749019607843137)] }0 H$ S$ y+ \7 T; E3 v
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);. s1 h7 s' V, |8 J+ C" F
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);
' s+ h! v. D# A[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);
: k0 F1 d, t1 v$ K6 I4 X; q% |( ]; L[color=rgba(0, 0, 0, 0.749019607843137)]}
% v2 j3 Z9 }5 E5 h1 c+ M[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
, v$ y% D& Y5 _2 \. A; ?[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)0 L& f8 l6 E" y; F) o" ~; l
[color=rgba(0, 0, 0, 0.749019607843137)]{
1 o4 j, \( g7 x' n6 f[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL); j9 ^/ B0 {* M' _
[color=rgba(0, 0, 0, 0.749019607843137)] {
$ }2 E) B9 ]3 R! R4 D/ h: Q[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");4 U- O# @2 Z; c# l+ D
[color=rgba(0, 0, 0, 0.749019607843137)] return;
; z3 ]- N: C. s6 C) ?[color=rgba(0, 0, 0, 0.749019607843137)] }
" F$ L- H( c) N3 C: S3 p8 _[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);
7 c9 j: X- d6 [9 v. k/ u[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
9 D+ n" q' C# J: `9 t[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);. M A- X, @3 p$ Z1 B2 a
[color=rgba(0, 0, 0, 0.749019607843137)]}
$ A7 b1 J6 y& q, v[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历. l2 f2 G, o5 Z$ I9 r
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)! }3 S6 @9 r) s$ _8 k2 q
[color=rgba(0, 0, 0, 0.749019607843137)]{
7 |, J' D ?+ h _0 _5 M[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
( O2 J7 t* ^* @4 v! r[color=rgba(0, 0, 0, 0.749019607843137)] {
: O% H. n) T4 g3 ~* @9 P+ e[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
; U9 S1 f+ g1 l. Q+ j[color=rgba(0, 0, 0, 0.749019607843137)] return;7 E8 K, K8 `% _4 t+ G
[color=rgba(0, 0, 0, 0.749019607843137)] }8 b9 k, `5 z0 L6 d( p5 H
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);7 @( {) v9 Z, \2 Q+ e5 L
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
+ c; \" `& m; g) }2 U[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);8 [/ V1 R1 y4 u0 Z8 `& d0 M
[color=rgba(0, 0, 0, 0.749019607843137)]}
3 [2 ^* o+ R" X& U[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构: t# Z) L% r- l( h/ K# ~: f1 l w
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()0 c: Y: f1 Z: ?5 y7 e" f
[color=rgba(0, 0, 0, 0.749019607843137)]{6 Q; Y- r) W5 Y( f- x2 [$ j7 v
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间! G- ?. B* O# w) e: }
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));
- t% `6 f% R# |# N( n+ S% N& S5 R) d[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
, U4 f# C' P1 o6 t+ u8 Z9 ~- J[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
^ m! ]2 i) G) ?" N1 J[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);9 \" X1 X8 T, Y D5 V, K! Q
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
9 B. V4 W' t* L; i( `/ ~ s/ c8 T. [[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);" C5 @9 e% y v! x
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
5 ? o& u. r U[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);/ Q9 K% [% p) E
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
1 l9 ~ t4 O) D[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
8 j! d J j. z! N[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));* H, R: F1 z2 _, y/ x& V/ j
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);7 a8 f' A f: [
[color=rgba(0, 0, 0, 0.749019607843137)], ]* o' t% d' n% V |
$ j, X5 T5 K l2 q |[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;
+ I2 _0 N) h) I[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
1 n- y3 H" g! G/ T/ u[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
3 O4 w" n* K* F# t3 {9 ^8 m4 f1 o[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;# |- O1 `) d5 ^& {# v) b3 L$ _
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
& R/ k. a4 G" d[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;5 i, K8 i1 r* I3 r, e( |
[color=rgba(0, 0, 0, 0.749019607843137)]
i$ j# j7 \1 b2 Q
% H5 e2 _, `1 P[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;. J `; V- o. _
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
6 y3 z" ^$ e, }: A. N! @6 r$ D[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;# j2 h8 A" p k, Q7 v: ^2 q: p
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
+ \+ w- E. f# I, T[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;/ X% ]/ N' G$ s8 W' I& F
[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;1 n5 c5 A- l5 ]- Q1 ?6 j4 |
[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;; n% U9 O" y( H4 K8 i
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
3 e* H' x1 l1 {- H$ P. z[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;1 b. ~! o- E6 i2 G
[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;3 n- Y2 Z# f- P4 l2 p+ D
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
, v. a9 F- Z V' E" Q. V! G[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;1 T" ?( P& {' z! Q4 f( }; i
[color=rgba(0, 0, 0, 0.749019607843137)]
/ i6 n: z0 l( [) M" C& Y2 s |" K/ ~; L o, t
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;& ^ G, E( ?# v( Y' Q
[color=rgba(0, 0, 0, 0.749019607843137)]}5 q" y# C4 G4 O
[color=rgba(0, 0, 0, 0.749019607843137)]% C/ i7 d. i9 t. S/ D
0 l" }, U) N5 `2 m. T$ t, }9 j4 e[color=rgba(0, 0, 0, 0.749019607843137)]int main()8 u/ c5 f7 w' C
[color=rgba(0, 0, 0, 0.749019607843137)]{
* { m. A* z4 v' G& o, ?( V/ N6 A[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构, w6 Z2 Y( G9 ? z0 S1 m
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();9 R! V+ A6 \. x+ ^, T. M
[color=rgba(0, 0, 0, 0.749019607843137)]: L+ E8 A0 e% P
* r9 N6 R6 K' E0 I[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历& Q X! }$ Y' ]1 a- j
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");$ m5 s, Y5 ^* P z, P% x6 U( p
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);
- k/ X# Z* [* T. t: ^1 N! n[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");/ G8 b6 M2 x v9 P2 p8 D
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历0 T2 z2 N5 q8 ]" z
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
+ n' l+ ` T% R& o/ w/ e& U[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);8 C* n3 H `' ~
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");% B" @0 g$ o* Z; H! d7 T
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历
F- }# ]1 I( R) q7 L5 D, u[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");% q3 o/ M$ z) R- }8 a% e" @
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
% d# }' \4 h) v[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
+ K0 R1 G( q7 H5 D/ s: r' a2 V, B[color=rgba(0, 0, 0, 0.749019607843137)]
- ^3 {2 |) t) B3 _# ~- }2 Z" N1 S9 N% ?
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
! v/ |& n! J+ Y0 U8 i[color=rgba(0, 0, 0, 0.749019607843137)]}
* j+ H. V; B, D. D( X[color=rgba(0, 0, 0, 0.749019607843137)]10 W- F/ N6 ?6 u
[color=rgba(0, 0, 0, 0.749019607843137)]28 \" ~' V; M) E, q( R
[color=rgba(0, 0, 0, 0.749019607843137)]3% E+ b. Z( _: F; e. H" w. `; x
[color=rgba(0, 0, 0, 0.749019607843137)]4
5 H6 L. B! x j7 G6 L% J[color=rgba(0, 0, 0, 0.749019607843137)]57 G% {4 k. I- _; g2 X/ c
[color=rgba(0, 0, 0, 0.749019607843137)]6
& e+ T3 y- `7 o4 l+ Q[color=rgba(0, 0, 0, 0.749019607843137)]7! g' t- ^ f Y
[color=rgba(0, 0, 0, 0.749019607843137)]8
$ i; l4 c1 f/ a/ @& z0 n/ r# V[color=rgba(0, 0, 0, 0.749019607843137)]9! O- d7 b- Z( e; h
[color=rgba(0, 0, 0, 0.749019607843137)]10; y5 t! Y$ `) B& p5 l6 t% ]/ \: @/ j' A
[color=rgba(0, 0, 0, 0.749019607843137)]11/ y1 j4 ]( o% b6 m! _" n6 O
[color=rgba(0, 0, 0, 0.749019607843137)]12, A U* A* w; K6 d
[color=rgba(0, 0, 0, 0.749019607843137)]13
; H- i5 x6 |, H; `[color=rgba(0, 0, 0, 0.749019607843137)]14
: |+ M% ~+ R' ?& x1 x6 o[color=rgba(0, 0, 0, 0.749019607843137)]15
8 k0 E) `2 @+ a8 i[color=rgba(0, 0, 0, 0.749019607843137)]16
6 @0 X7 \* I; Z2 O4 G& R) |[color=rgba(0, 0, 0, 0.749019607843137)]17& I! m2 r4 y2 |2 ^9 W
[color=rgba(0, 0, 0, 0.749019607843137)]18
- G/ z( {" L" R[color=rgba(0, 0, 0, 0.749019607843137)]199 `" O. c- k, a1 M* q
[color=rgba(0, 0, 0, 0.749019607843137)]207 b! M0 g }: X4 Z% \
[color=rgba(0, 0, 0, 0.749019607843137)]21
4 p0 ^/ ^6 b' Z6 j[color=rgba(0, 0, 0, 0.749019607843137)]22. g7 C8 P3 S% @: ^
[color=rgba(0, 0, 0, 0.749019607843137)]23- `, \# U0 n4 s
[color=rgba(0, 0, 0, 0.749019607843137)]24$ o* p1 s; U" ~! x
[color=rgba(0, 0, 0, 0.749019607843137)]25
0 n% M; ]/ I( l- i' m[color=rgba(0, 0, 0, 0.749019607843137)]261 h* F- g4 F5 m( g7 _! M7 x, W
[color=rgba(0, 0, 0, 0.749019607843137)]27& I* Y6 L) w8 K+ T
[color=rgba(0, 0, 0, 0.749019607843137)]28
7 B, \, D/ G0 A' s- Q* c[color=rgba(0, 0, 0, 0.749019607843137)]29" _ g. O3 t' `5 k1 [" @
[color=rgba(0, 0, 0, 0.749019607843137)]30
5 z/ x6 [( O S9 f[color=rgba(0, 0, 0, 0.749019607843137)]31! L; l* b9 B% b7 b
[color=rgba(0, 0, 0, 0.749019607843137)]32
/ n! S3 B5 R" k* c) |[color=rgba(0, 0, 0, 0.749019607843137)]33
3 z' @ D7 h7 b3 d[color=rgba(0, 0, 0, 0.749019607843137)]34
" \8 Y4 Q* t' B4 h% q' }[color=rgba(0, 0, 0, 0.749019607843137)]35- Q+ O" K) t+ I4 f6 S* F
[color=rgba(0, 0, 0, 0.749019607843137)]368 l0 @7 v' r& h! O7 ^
[color=rgba(0, 0, 0, 0.749019607843137)]37
1 @, A6 |6 `, u B% M Y) Z[color=rgba(0, 0, 0, 0.749019607843137)]38# E4 z5 Y! r! E; D" N0 m3 A8 @
[color=rgba(0, 0, 0, 0.749019607843137)]39
% H* z2 b* T# Q" i. [+ i! e a2 r9 X[color=rgba(0, 0, 0, 0.749019607843137)]40 W6 P( y3 J' X v/ X8 h1 b3 @2 Q
[color=rgba(0, 0, 0, 0.749019607843137)]41
8 _1 D1 K1 N/ H& h4 d[color=rgba(0, 0, 0, 0.749019607843137)]420 B- p8 W, `* J/ \" r1 r
[color=rgba(0, 0, 0, 0.749019607843137)]439 m0 Z/ `! H7 E/ g+ t
[color=rgba(0, 0, 0, 0.749019607843137)]44' @- @+ T3 b. ?* ^; P. a2 o% \# C
[color=rgba(0, 0, 0, 0.749019607843137)]45- P1 G& T, Y7 Q$ w+ w& N
[color=rgba(0, 0, 0, 0.749019607843137)]46
2 b( S6 c# p& _+ ?" i, U4 s% r[color=rgba(0, 0, 0, 0.749019607843137)]47% a, x. w& q; k% X: ~
[color=rgba(0, 0, 0, 0.749019607843137)]48
# e4 t Q; ?; t& g# M2 ` g" p$ G% i[color=rgba(0, 0, 0, 0.749019607843137)]49) K5 D6 A4 n9 ^/ u$ b6 O$ |
[color=rgba(0, 0, 0, 0.749019607843137)]500 O7 _+ c2 X+ I" O' E" Z3 |
[color=rgba(0, 0, 0, 0.749019607843137)]51
1 P* J1 u6 c' Q/ K P$ m2 }$ f[color=rgba(0, 0, 0, 0.749019607843137)]526 y8 L7 }5 ?8 i) j5 N
[color=rgba(0, 0, 0, 0.749019607843137)]53
4 b, @" R, f5 G; r# ], Z[color=rgba(0, 0, 0, 0.749019607843137)]54
3 P* D: A, j1 ~0 q/ y1 g, K+ a[color=rgba(0, 0, 0, 0.749019607843137)]55& s& `8 m6 y5 A+ `9 T5 U* `5 J
[color=rgba(0, 0, 0, 0.749019607843137)]56
; I/ Z1 J4 |9 S% p$ e[color=rgba(0, 0, 0, 0.749019607843137)]571 g+ C4 v# F6 t8 X
[color=rgba(0, 0, 0, 0.749019607843137)]588 L' s# S+ G% m' A0 |6 M
[color=rgba(0, 0, 0, 0.749019607843137)]59
$ v( `9 Q( E* p2 q# z[color=rgba(0, 0, 0, 0.749019607843137)]60
( [$ s+ J% ] ~0 @[color=rgba(0, 0, 0, 0.749019607843137)]61
: _ ]. ~3 `" S# ^: A7 e[color=rgba(0, 0, 0, 0.749019607843137)]62! V. l! X+ k& _# n# g* E
[color=rgba(0, 0, 0, 0.749019607843137)]63
. I) ^, W% K3 O2 @0 V8 s: [[color=rgba(0, 0, 0, 0.749019607843137)]64
) v% n, j5 ?" X9 s1 b# q; {+ W[color=rgba(0, 0, 0, 0.749019607843137)]65
$ A* N9 f7 s1 ^7 A$ `, c& F[color=rgba(0, 0, 0, 0.749019607843137)]66
. |( b M* Y9 Q[color=rgba(0, 0, 0, 0.749019607843137)]675 o2 @+ z1 }- H3 \2 @6 O2 S [
[color=rgba(0, 0, 0, 0.749019607843137)]68# m! `0 `$ v1 v- E
[color=rgba(0, 0, 0, 0.749019607843137)]69
8 `2 H( W, j1 k, o E( O[color=rgba(0, 0, 0, 0.749019607843137)]70
8 j- i" K. w" r+ ^[color=rgba(0, 0, 0, 0.749019607843137)]71
+ V- W0 l- V6 Z0 Z( l4 z[color=rgba(0, 0, 0, 0.749019607843137)]72/ u( @/ S+ V7 j' `" x5 i X
[color=rgba(0, 0, 0, 0.749019607843137)]73
6 }* Y1 p/ S; \0 s( k# B[color=rgba(0, 0, 0, 0.749019607843137)]74
! `4 P/ V2 I- D& ?6 j7 c% \, ?8 ~) B[color=rgba(0, 0, 0, 0.749019607843137)]75
! B( K: L3 M* [* D X3 ~& S3 J4 N[color=rgba(0, 0, 0, 0.749019607843137)]76, @" H! E) W+ _4 `0 M8 K
[color=rgba(0, 0, 0, 0.749019607843137)]77# d2 a# w4 H* k8 Y( J4 k$ x* |4 z
[color=rgba(0, 0, 0, 0.749019607843137)]78/ W# [# s5 y( ~
[color=rgba(0, 0, 0, 0.749019607843137)]790 S8 A; {3 u s+ ~* ]
[color=rgba(0, 0, 0, 0.749019607843137)]804 F; U/ ?/ v" y/ F- j
[color=rgba(0, 0, 0, 0.749019607843137)]81! D# ^7 K) q. {* x' ~* X) K8 ]9 R1 }
[color=rgba(0, 0, 0, 0.749019607843137)]82( L* n: Q2 v" T
[color=rgba(0, 0, 0, 0.749019607843137)]83
# M; h7 i0 E% I3 { X0 q9 W6 u[color=rgba(0, 0, 0, 0.749019607843137)]84 W: W/ p* C( O. z" s5 I
[color=rgba(0, 0, 0, 0.749019607843137)]854 }; A& s3 X/ H+ l
[color=rgba(0, 0, 0, 0.749019607843137)]86
" `, S( R7 @' v) F[color=rgba(0, 0, 0, 0.749019607843137)]87
) `0 Q! C3 l# v1 f[color=rgba(0, 0, 0, 0.749019607843137)]88
: D* u6 u% }8 B7 r/ D7 K[color=rgba(0, 0, 0, 0.749019607843137)]89- x9 L; ^: m7 w: ?. u
[color=rgba(0, 0, 0, 0.749019607843137)]90
- R/ m. Z+ W! R) c- R) Q1 y1 c$ a[color=rgba(0, 0, 0, 0.749019607843137)]914 X2 m" G. }8 {0 J% u7 D' U
[color=rgba(0, 0, 0, 0.749019607843137)]92
R3 T( t! V4 q[color=rgba(0, 0, 0, 0.749019607843137)]93! x+ D" j$ @) l [# ]
[color=rgba(0, 0, 0, 0.749019607843137)]94
! t3 r5 t9 @) D1 U* g[color=rgba(0, 0, 0, 0.749019607843137)]95
I5 {. R5 k! p4 ?' Y[color=rgba(0, 0, 0, 0.749019607843137)]96+ c/ _0 { ?9 f3 \0 u" R
[color=rgba(0, 0, 0, 0.749019607843137)]97, H+ U n1 h [) t+ n
[color=rgba(0, 0, 0, 0.749019607843137)]98
6 q1 y# M8 V/ [[color=rgba(0, 0, 0, 0.749019607843137)]994 E/ a7 f6 Q" ]5 }8 G
[color=rgba(0, 0, 0, 0.749019607843137)]100) I9 W; ^: c) Z( b9 K
[color=rgba(0, 0, 0, 0.749019607843137)]101$ ~( E6 M6 S8 s- [7 [$ g
[color=rgba(0, 0, 0, 0.749019607843137)]102, K- j: n+ S, o0 E' ]. p
[color=rgba(0, 0, 0, 0.749019607843137)]1035 C* r- ]" a/ W: u" P* ]8 T
[color=rgba(0, 0, 0, 0.749019607843137)]104( Y f; _: J* c: M
[color=rgba(0, 0, 0, 0.749019607843137)]105
5 v* c4 _+ o& N/ b, r, q' c[color=rgba(0, 0, 0, 0.749019607843137)]106; u' }: M: ~4 J
[color=rgba(0, 0, 0, 0.749019607843137)]1071 {3 ?0 M v4 e
[color=rgba(0, 0, 0, 0.749019607843137)]108, C' f$ V/ L! w0 a U
[color=rgba(0, 0, 0, 0.749019607843137)]109
+ |8 r9 k( T6 J2 y5 u8 J! i4 E[color=rgba(0, 0, 0, 0.749019607843137)]110( ~) r/ A) [* }6 L
[color=rgba(0, 0, 0, 0.749019607843137)]1111 P0 g# v' P; h' S
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
, b& _: [$ ?& {' O# g3 V/ h6 u' X[color=rgba(0, 0, 0, 0.749019607843137)]7 I) L6 ^8 y1 a/ s ?5 y
0 z8 d9 b7 Z ]: b* ?8 L- g
[color=rgba(0, 0, 0, 0.749019607843137)]3 x+ r/ V! I: r4 p1 |
/ Z. D4 d) D& f+ v8 u3 B) G# ~
[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
; p, ~; S: c( u0 \% g[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)& }2 q+ ~8 D F. d- b
[color=rgba(0, 0, 0, 0.749019607843137)]
+ s" z* ], r' J) a
2 _, r& [+ q' S0 y; s+ T- I: t[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
- u; x0 n4 ^4 m( g$ ?* R[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
1 o5 p# F2 T1 h: ?# g$ a( ]; T[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;: S5 }2 @- ]" {6 k6 b
[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)/ {" {- P9 Q6 w1 j) _( {+ P* Y
[color=rgba(0, 0, 0, 0.749019607843137)]//{- j q0 ^* i+ o4 c* H9 L
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
0 Z; f8 W0 L1 M. H[color=rgba(0, 0, 0, 0.749019607843137)]// {6 P# C, y# E* }6 J% S
[color=rgba(0, 0, 0, 0.749019607843137)]// return;! U/ z5 V# s$ [1 X
[color=rgba(0, 0, 0, 0.749019607843137)]// }1 ?' s8 W3 Z2 G) x3 ]! w$ X; M2 O) D
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;6 g& f8 D+ W7 E
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
$ J1 W# M. f! c$ c* v5 l[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);8 h2 C! H& S6 Z( N
[color=rgba(0, 0, 0, 0.749019607843137)]//5 ~" ~- _& i4 M" W
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量- X" y, z7 z4 {, g6 U0 K
[color=rgba(0, 0, 0, 0.749019607843137)]//}7 f3 G; c& @& r6 w' l
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
2 h6 I3 ]5 }6 \$ `5 f: x[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)
, G5 Z7 U8 ~6 K6 j. c[color=rgba(0, 0, 0, 0.749019607843137)]{% @$ N u* S K0 d
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
3 e: I8 s: T! u# h- m; k[color=rgba(0, 0, 0, 0.749019607843137)]}5 M ]- _& ~: c. y v
[color=rgba(0, 0, 0, 0.749019607843137)]1
1 q. m, h/ R/ ^! N7 S' {[color=rgba(0, 0, 0, 0.749019607843137)]2
4 J' i- Y- r) {- m% g5 T[color=rgba(0, 0, 0, 0.749019607843137)]30 V7 s/ o' s) o$ Q1 C
[color=rgba(0, 0, 0, 0.749019607843137)]4
8 [4 s" { a6 Y( v( l1 W. S5 \[color=rgba(0, 0, 0, 0.749019607843137)]5' t. i7 O1 w+ X- ]+ A! _
[color=rgba(0, 0, 0, 0.749019607843137)]6
% }2 ^9 n$ r- Q. F! L9 J[color=rgba(0, 0, 0, 0.749019607843137)]7
6 M9 E) B: h3 w. ?; h2 b; {[color=rgba(0, 0, 0, 0.749019607843137)]8* |, W3 |" i+ v6 n1 I. K( T
[color=rgba(0, 0, 0, 0.749019607843137)]99 O, e( ^3 a+ i1 Z& @7 D
[color=rgba(0, 0, 0, 0.749019607843137)]10
2 z1 |9 d4 A( {[color=rgba(0, 0, 0, 0.749019607843137)]11
3 f# x3 {3 J' Z[color=rgba(0, 0, 0, 0.749019607843137)]12
( I: X3 n2 i0 [# w+ l: @, J7 w[color=rgba(0, 0, 0, 0.749019607843137)]13/ y. L" Q6 y+ ^1 G- K9 v7 i3 [
[color=rgba(0, 0, 0, 0.749019607843137)]14! \8 ~- P( Y% ~7 u
[color=rgba(0, 0, 0, 0.749019607843137)]15
' O v, ?, ?9 B+ L[color=rgba(0, 0, 0, 0.749019607843137)]16
0 @1 v& ]2 t" U2 m. ?, L[color=rgba(0, 0, 0, 0.749019607843137)]17, d* n: E+ M/ H, h5 _
[color=rgba(0, 0, 0, 0.749019607843137)]18
0 J* W& M5 t. S: A0 x6 w) t[color=rgba(0, 0, 0, 0.749019607843137)]19% Q. I, \( ^0 o+ r3 B# `, G
[color=rgba(0, 0, 0, 0.749019607843137)]207 n; X0 X/ c! c, {& @
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数+ R- e+ g3 u% e: a
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数; k! n2 ^ ?$ S0 F9 x' x+ E; i
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root), W' e8 g+ L2 y( |7 L. s' z9 l
[color=rgba(0, 0, 0, 0.749019607843137)]{2 l$ e2 R, A* b- u2 l- ~' L1 H. A
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点
/ K6 {; k( n; C[color=rgba(0, 0, 0, 0.749019607843137)] {; o: e1 M4 H( ~8 W/ k0 R0 C
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;2 i! Y, ^& T% P3 X1 w8 S/ h8 Q( \# @
[color=rgba(0, 0, 0, 0.749019607843137)] }
. w" Q$ {. Q- |7 U3 l[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
$ L0 S" N# `# z. [[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)/ Z, Y, k9 p6 s7 i* {
[color=rgba(0, 0, 0, 0.749019607843137)] {$ H1 k0 I! T0 a- j4 B9 |
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;
* b* w0 _6 e/ x: ?[color=rgba(0, 0, 0, 0.749019607843137)] }
4 ?- o7 i) ^0 s9 X H7 D( f9 P r# h[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
5 p6 o; ^8 v. l: H4 K3 o! L0 I0 R[color=rgba(0, 0, 0, 0.749019607843137)]}9 r, }' m# b$ ]* x: U6 J
[color=rgba(0, 0, 0, 0.749019607843137)]1' [% Q1 I) L9 J- Y) Y: ^4 q
[color=rgba(0, 0, 0, 0.749019607843137)]2
) _& n- A+ R- O* h[color=rgba(0, 0, 0, 0.749019607843137)]3: K% J% [/ \# _
[color=rgba(0, 0, 0, 0.749019607843137)]4
# J& t2 k8 h5 v7 w. I9 U+ @3 P[color=rgba(0, 0, 0, 0.749019607843137)]5; f0 w6 n1 e R: e
[color=rgba(0, 0, 0, 0.749019607843137)]62 g4 C4 J. Z( g0 q$ F7 O! S) N0 o
[color=rgba(0, 0, 0, 0.749019607843137)]7) z" K0 e0 c9 x1 E. c! }+ n" r+ |
[color=rgba(0, 0, 0, 0.749019607843137)]82 Q' K: y& y* D
[color=rgba(0, 0, 0, 0.749019607843137)]9
+ O# }, d) ?4 h) }' h[color=rgba(0, 0, 0, 0.749019607843137)]10
* t2 W0 c3 G; c[color=rgba(0, 0, 0, 0.749019607843137)]111 ]! X4 K& h3 Y+ V
[color=rgba(0, 0, 0, 0.749019607843137)]12
( H- G9 V- s6 N. T2 d[color=rgba(0, 0, 0, 0.749019607843137)]13
) h. K5 R1 N, C& ?2 w[color=rgba(0, 0, 0, 0.749019607843137)]14( |& L4 x2 e8 f7 @. W9 u4 s) M
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
6 A) }* C: T, b1 M[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root). S6 e" w+ I2 H+ {& U
[color=rgba(0, 0, 0, 0.749019607843137)]{
. b3 R0 @+ t4 x- v- ]% b: { |5 Z9 M[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0. [; h" H" H. o9 K; S8 ]* z
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
! Q4 W+ i6 p; k; N& K[color=rgba(0, 0, 0, 0.749019607843137)] {
0 Y U$ @3 N+ q% ^, V5 w& S[color=rgba(0, 0, 0, 0.749019607843137)] return 0;* X( `5 f* d, u# U. c
[color=rgba(0, 0, 0, 0.749019607843137)] }
0 K1 C8 n0 {7 B$ g9 b& d[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树3 G( b, [6 G5 P9 V! u
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度& B9 e5 S% l) H* Z* r0 b; n
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度/ v- D- D. u# U9 j- j
[color=rgba(0, 0, 0, 0.749019607843137)] u2 X' S# p+ `4 q* X" k
}, _; p l9 |# E* @
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;) U+ L$ ~0 T: j8 I6 G4 O) A
[color=rgba(0, 0, 0, 0.749019607843137)]}$ E5 g6 W6 n) \/ V
[color=rgba(0, 0, 0, 0.749019607843137)]11 x2 ^& B3 H0 _2 n# l5 \
[color=rgba(0, 0, 0, 0.749019607843137)]26 F& c1 S# B, O1 ~9 }$ A0 Z
[color=rgba(0, 0, 0, 0.749019607843137)]3
+ \1 f5 ^% k% S# q[color=rgba(0, 0, 0, 0.749019607843137)]43 B2 Y6 I+ @2 |2 {4 H
[color=rgba(0, 0, 0, 0.749019607843137)]53 l! o) | \ p7 U5 D. n
[color=rgba(0, 0, 0, 0.749019607843137)]6# a& T S M4 M* j- Q
[color=rgba(0, 0, 0, 0.749019607843137)]70 ?) x4 o6 Y0 v
[color=rgba(0, 0, 0, 0.749019607843137)]87 a2 {) a h8 w
[color=rgba(0, 0, 0, 0.749019607843137)]9* D. }2 c7 a% ~6 @+ o3 A; K: w5 q
[color=rgba(0, 0, 0, 0.749019607843137)]10# d( t) |# G/ A. j8 m
[color=rgba(0, 0, 0, 0.749019607843137)]11
% v7 ^$ B6 V% m5 {[color=rgba(0, 0, 0, 0.749019607843137)]12
5 w) z5 x' x8 i/ d1 M. G[color=rgba(0, 0, 0, 0.749019607843137)]13 @6 |9 e& T5 h/ M; h) i ~1 K& H
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数* m$ I3 F" a2 y: X: _8 ]* h
[color=rgba(0, 0, 0, 0.749019607843137)]
# M% a# S# w0 `1 Z! X% L& J/ Y5 ^
0 R$ a: f8 L( q; R. C[color=rgba(0, 0, 0, 0.749019607843137)]4 ]- }- J+ u& k
3 g8 D0 |2 S2 y3 I
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。: ^$ L4 j P2 Q# \" X/ k( [- T1 C
[color=rgba(0, 0, 0, 0.749019607843137)]
& Y7 ?5 v: f2 D* Z% X$ w" j5 G
# k9 x1 E |+ ` J' b! ^5 w$ ^[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数# p0 r2 [- U2 V6 m1 i3 M
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)
& i( O% T4 a0 \- ^[color=rgba(0, 0, 0, 0.749019607843137)]{! {+ y/ n# k b4 r4 R
[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);% j5 }3 _" ] W, |1 `! w1 r* F1 e2 D
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
0 ~: A- R! k0 V0 p* V[color=rgba(0, 0, 0, 0.749019607843137)] {( S+ Z9 p- Z( z& C( ]
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
9 w' K/ ] ~5 R1 h3 o3 o4 u# I6 L4 {[color=rgba(0, 0, 0, 0.749019607843137)] }* X# S; V% L7 k
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
L3 S! n( [* j: g; _[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)9 R+ N: B8 W$ k
[color=rgba(0, 0, 0, 0.749019607843137)] {
9 `- ^. o1 }( n Q& l/ _[color=rgba(0, 0, 0, 0.749019607843137)] return 1;9 o1 e7 l% Y5 {( J# t% n" Q( M3 v
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 k, V; o. E8 K9 y' q0 w2 n& @2 S[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层
: A% H9 O( ~ e+ i8 l[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);: T% A) n; t0 s. z% j
[color=rgba(0, 0, 0, 0.749019607843137)]}0 H0 P! K* _9 h. n' {% u
[color=rgba(0, 0, 0, 0.749019607843137)]1
( T4 b4 t: X. [2 S& P[color=rgba(0, 0, 0, 0.749019607843137)]2
% f6 F6 i& a5 V[color=rgba(0, 0, 0, 0.749019607843137)]3
8 [$ ]1 w4 _! O* S2 p[color=rgba(0, 0, 0, 0.749019607843137)]4
" E! m7 F( j- X8 I" n8 E4 W[color=rgba(0, 0, 0, 0.749019607843137)]5
3 [! E7 B' Q) E2 o% A2 x* p[color=rgba(0, 0, 0, 0.749019607843137)]6
& F, M! G$ P) a: y8 r, [[color=rgba(0, 0, 0, 0.749019607843137)]7
. [$ O. {# p0 B Z8 B3 T[color=rgba(0, 0, 0, 0.749019607843137)]8
7 r9 ]; L3 _ w; o5 |[color=rgba(0, 0, 0, 0.749019607843137)]9' X, _5 k$ M7 A# \6 W5 r6 P* p
[color=rgba(0, 0, 0, 0.749019607843137)]10
- l4 K& s# Q4 _% M[color=rgba(0, 0, 0, 0.749019607843137)]11+ Q6 H' t6 K- C6 N0 [6 }2 t# A
[color=rgba(0, 0, 0, 0.749019607843137)]123 W" w$ G7 P" g- Y8 j9 i/ h
[color=rgba(0, 0, 0, 0.749019607843137)]13
7 J/ z- l! h6 O& G0 d. V9 p[color=rgba(0, 0, 0, 0.749019607843137)]14" b5 l' j0 |9 \4 K, R
[color=rgba(0, 0, 0, 0.749019607843137)]15
) O' [! P4 O4 z2 e[color=rgba(0, 0, 0, 0.749019607843137)]16
9 M# m; C1 [* V9 B9 G( p[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找$ S/ b+ F5 b1 R4 `' K8 A8 d
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
; [" r1 [3 c6 z4 ]0 E: A[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
4 ~ }9 a' ?# l. F2 h: A! |[color=rgba(0, 0, 0, 0.749019607843137)]{
. H4 u* [* i8 S4 }1 T1 u[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
* V! C' _" h+ `% A9 Q& @[color=rgba(0, 0, 0, 0.749019607843137)] {. g/ u: v _7 w( E4 s* i
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
$ d6 x/ u6 U! F, e3 w% V: D[color=rgba(0, 0, 0, 0.749019607843137)] }
' {$ E5 C3 h6 J+ _/ {8 g[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)" \* W/ F9 E9 A/ |( Q. d! y3 G& B
[color=rgba(0, 0, 0, 0.749019607843137)] {
" u" R8 s. v: A/ K: i9 r[color=rgba(0, 0, 0, 0.749019607843137)] return root;9 j) u+ S# P) y+ _. _$ E0 C
[color=rgba(0, 0, 0, 0.749019607843137)] }
7 \' y K7 a5 p3 L[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
' n) k2 D+ ]. W6 V) ^/ \% G& P[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
) J0 W* a3 p, o# W[color=rgba(0, 0, 0, 0.749019607843137)] if (lret), e( Y) |- m- ^9 M0 t( w
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;
6 C2 G& R) ~2 |& b[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
( L2 Y; G7 H: Y8 m[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);% \4 T4 r5 n8 U& g
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
- A* w! G" [& h/ \; B. P[color=rgba(0, 0, 0, 0.749019607843137)] return rret;% ?! K- o$ t! P! K1 O" y
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;) I. a, u! C+ k) @. R
[color=rgba(0, 0, 0, 0.749019607843137)]}
. G6 o2 t4 c% _9 |) k7 ~* H[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
, y4 ?0 d! A& g5 q( }$ D[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。6 [9 c' r B/ }( {. R
[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
& A: D: U& S. w$ `# g" d5 N7 t
* ^' l% ^3 Q- G( v- _3 c$ b2 v! `0 N1 q2 z$ W [! P
[color=rgba(0, 0, 0, 0.75)]# I* u7 T: ~2 V: @" c, G: l
4 j/ W/ A+ m8 B* S# ]5 F3 l. f3 M3 j7 Y/ \5 j* S: o
+ P1 O% v9 Z/ w Q0 b8 g
|
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
