【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历
1 a) k+ M/ i" K! }4 Y5 T
( b6 ~; w0 N& v; P& q[color=rgba(0, 0, 0, 0.749019607843137)]文章目录: u! ]& N- _* c/ P, K* J
[color=rgba(0, 0, 0, 0.749019607843137)]前言
! ~5 u+ s! W# p7 x5 d2 N[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
! a8 K* O- q+ h; I x" e2 Y5 ?[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
# W5 t: U) V5 T[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
9 D( \0 L% v5 ?/ q! I: g$ [3 n[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小1 o; q* x% ? v
[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数8 Y L8 G0 Y7 G9 ^; E
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度, q; I7 @3 n3 {5 a% ]. G
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数: X( _/ i4 m2 {; F7 a
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找* j- t X* r# n! y# b
[color=rgba(0, 0, 0, 0.749019607843137)]前言1 ]" p u+ g8 L5 [8 p2 f% G. Z
[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。* Z. k2 A0 P2 Y; R/ H& }1 `7 d
[color=rgba(0, 0, 0, 0.749019607843137)]! i$ {, y- r5 F/ z4 y4 q" E
3 |3 r; d' c0 I4 U, ?$ M3 O% i
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式1 Y, t" ^* r4 d+ ^( b
[color=rgba(0, 0, 0, 0.749019607843137)]& J, a- Q" o9 `
8 q' N9 h) R) P[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：1 v0 v7 [" m% v# k4 e
[color=rgba(0, 0, 0, 0.749019607843137)]1 R# B* x( d. W) l& [& R% w# F7 a
1 l- z5 @' t& I[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树5 u% Y: L7 Q% C! H6 ?5 u+ |
[color=rgba(0, 0, 0, 0.749019607843137)]
: n* ]% P; Q& M: y- o) V0 D: _6 S2 J. T& b0 I x- g
[color=rgba(0, 0, 0, 0.749019607843137)]9 p- E8 E- K! q# \% y) ?) o
0 W4 ?3 [$ [; e3 I3 l: G, Q% w6 q1 F[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树
3 ?! b* `5 R) M' F& p4 h[color=rgba(0, 0, 0, 0.749019607843137)]
" k' B5 g( K/ E% ]: W4 i; G) W. a
[color=rgba(0, 0, 0, 0.749019607843137)]
8 w e8 f! J& l
8 }8 q! o# I. s' o) s[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根# r7 g6 Z9 S$ Z! \+ K
[color=rgba(0, 0, 0, 0.749019607843137)]
' L* y7 e; U6 V. A2 \ Y3 ^- j; r2 S6 F. G
[color=rgba(0, 0, 0, 0.749019607843137)]
# u7 {) P! {: r% m6 b& r$ [) m* o+ o
& l' v3 V8 l& u! N |1 ?' O[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
h7 ?6 D- Z6 e9 U! I4 `) @* I( v! c[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之/ B* j0 B1 i3 r" D& U
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；% X, w2 O) I* x' X9 z8 e
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；; ~( Q, [* }) R$ Z8 t @
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
; R. A6 E" i6 p: l; N1 ?[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；1 v/ x0 _0 V1 n3 I K
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；
2 p: W5 S; P5 V: s& d1 {[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
( r/ A9 Q3 L9 a9 {* m9 w[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
, v( r4 A0 F. U# C N[color=rgba(0, 0, 0, 0.749019607843137)]) S5 n4 V1 l6 g) R$ n
& A) N: M, |4 n0 H! c
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历1 K2 j L4 P/ r8 s
[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1
0 P- V7 x% r& o+ o[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>; B8 b4 ~1 [$ R8 A2 `( Y# A
[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>" V2 y6 O8 U2 W
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
6 v8 Q$ h3 |5 a6 B4 A3 Q[color=rgba(0, 0, 0, 0.749019607843137)]0 q' |2 k: O) x8 n
2 ~3 r7 n9 X0 B9 g3 p+ B/ P
[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;5 ]3 A0 |& X' P" d: I
[color=rgba(0, 0, 0, 0.749019607843137)]
* o4 r! h+ U# U+ n1 |+ p$ Z3 Z" J: n1 Z5 `2 Y& r% e3 Z% u( ~+ W# \( c, L0 U
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
0 q5 f" G/ N( d) s+ ?0 Z0 @[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode, }- ?1 P9 n3 M3 ?0 D2 ^
[color=rgba(0, 0, 0, 0.749019607843137)]{
! l0 `, a! W+ X[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;1 v) Y3 V( L! M- Q0 G
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
& G( B$ D3 H; O! d" S7 `* b[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;
2 L; l( t x# v2 Q* f2 p[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;/ Z( ~( T$ X; |3 I
[color=rgba(0, 0, 0, 0.749019607843137)]8 j4 V' I% |; H8 V' ~
' h, B' |7 }6 n$ p$ ~ b[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
/ o, d. {0 l, c4 m[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
' |# a% z0 |! r$ P$ H. l[color=rgba(0, 0, 0, 0.749019607843137)]{
8 r) ^+ `6 ?1 M% U$ y6 c2 K8 B[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)4 \8 n+ t2 U' L( q& |9 i+ J
[color=rgba(0, 0, 0, 0.749019607843137)] {8 u1 ~' z' X1 s0 p5 y
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL "); i( I( v# |1 G' E
[color=rgba(0, 0, 0, 0.749019607843137)] return;# s4 R4 z$ F; @) X
[color=rgba(0, 0, 0, 0.749019607843137)] }5 ]" g0 M' i C
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);6 z# ~! O' g& P* z
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left);. ?) H2 z. {" V: x- D) u; G
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);
6 E& Q! o/ d0 e7 j6 G# a[color=rgba(0, 0, 0, 0.749019607843137)]}. Q" e6 z2 z* l) N
[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历
) O; i7 M0 E3 O2 j' U! t[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)
$ c' d( r6 u0 D8 J) T$ s[color=rgba(0, 0, 0, 0.749019607843137)]{- C1 p3 c: ^& ~- v9 Q+ s1 A
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
" g$ \' S/ S! c& t3 ][color=rgba(0, 0, 0, 0.749019607843137)] {
9 v& {4 S1 b `[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");( ^: Z2 w# T3 P' F) q% O" d+ E/ h
[color=rgba(0, 0, 0, 0.749019607843137)] return;
' Q' N9 u8 g' N2 s& s# l7 T6 h6 t[color=rgba(0, 0, 0, 0.749019607843137)] }
+ q) O: P6 L q( _- @* o; ^[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);" S+ I S+ K3 [5 r) J% t/ D2 n3 F! C7 D
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);& `! i: T) x/ H, _
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
% T# W5 ]8 J2 d) V* y7 J[color=rgba(0, 0, 0, 0.749019607843137)]}
4 `5 M& M d/ P5 l# Z$ \" X[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历3 @6 y6 S# @: X1 D8 i
[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)
7 S8 X$ @( k$ w, C8 @[color=rgba(0, 0, 0, 0.749019607843137)]{2 _3 _! b: T* C% A6 x3 X
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
& l! i( ]6 ]3 z6 x3 o! v$ m/ D[color=rgba(0, 0, 0, 0.749019607843137)] {& @. Y v U. J7 `% B. ?
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
, D% k1 o7 ?# S. Q* f( z, a[color=rgba(0, 0, 0, 0.749019607843137)] return;+ ^. k/ s7 @( L, `. ^) c. \
[color=rgba(0, 0, 0, 0.749019607843137)] }
1 o" f) H% J9 t4 n6 Z# h1 O[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);
/ l/ ]6 Q" _$ M[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);
2 Q( h4 a* N0 H3 z. `[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
* I1 A4 m: ^7 F2 S+ U# d$ O9 c[color=rgba(0, 0, 0, 0.749019607843137)]}
& l) H9 ?1 \: d( k[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构' K3 U9 Q6 c4 f, r8 a/ s% Q
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()$ P1 C8 `& j* {+ Q; b' b: p$ G
[color=rgba(0, 0, 0, 0.749019607843137)]{6 \- N* D# D( t' d* l! I- ]
[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间
( h. ?* `4 ~9 Q; v[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));8 I- t# c9 r' T
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);$ V3 Q/ Z6 u0 t) {0 ^
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));
- j# |. F$ |7 r[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);9 N" o2 l& P& K/ m2 Z- j1 @8 { t
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
, S g$ F/ f6 Y/ L[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);
9 `, n5 K ]) A! a+ D[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));
! N# G9 z6 q" [7 B" @* ~[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
1 D9 j* C6 [+ K# a. ^, A- e[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));8 l {* N2 z) Z8 C8 _. r5 O+ d; R
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
+ m- K1 U% l+ h* h[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));
8 |1 N7 K1 t3 a[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);
- l' o6 K$ U! _3 Q# q1 ]8 {: }[color=rgba(0, 0, 0, 0.749019607843137)]
5 `! D2 S6 N8 Y% `
- ~) O& D: `- S[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;
7 N" W/ B k/ o* k, A[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
2 n. Z. I5 n/ V D5 z T& t& x[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;
0 w& @, z$ G! L/ `[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;5 J! g9 l3 h9 ], N% g
[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;
6 A& x6 ^2 v; G0 g( _[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;1 `" o; P) O: A) M/ S9 p
[color=rgba(0, 0, 0, 0.749019607843137)]
' a( X$ y- Q$ l9 {. F5 t j! G1 A6 |
[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;
3 v3 y2 P4 W* z[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;8 a z7 Q* i% k% @; m) ~
[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;( Z( ~* t( R4 c1 Q- L- f; j+ M
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;4 _0 ]9 r% }3 L( L& y* n# b4 o5 d1 B
[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;: A3 Q3 `* C4 \; F- g, c/ O
[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
7 v- ]1 B2 c7 q! o, p- t[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;# y# I9 W" V* [" x
[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;
( y& e4 c# o7 s/ F! q2 D( C0 {[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;
P! N$ [8 [7 [8 ][color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;
- [1 g9 @& P0 x4 y/ w[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
* \. N; h% X. Z4 |. S" C[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;7 x7 c2 Z0 X. R3 a/ T' h( L
[color=rgba(0, 0, 0, 0.749019607843137)]
& A' j* X" h$ A$ `+ f. a9 ~+ I I/ C [
[color=rgba(0, 0, 0, 0.749019607843137)] return n1;
9 o2 G! T( S0 C[color=rgba(0, 0, 0, 0.749019607843137)]}/ [' E+ H9 w- o2 p3 i) J3 ~
[color=rgba(0, 0, 0, 0.749019607843137)]
" p9 S( j1 {& s/ A* V
% E4 }4 a8 l' k# l: i2 h[color=rgba(0, 0, 0, 0.749019607843137)]int main()
8 H/ r6 R9 ^3 e, I; P# D, V3 ^[color=rgba(0, 0, 0, 0.749019607843137)]{" y% x5 j: Q$ w2 d6 P7 ]$ k5 A
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构( V) i4 F. W5 D9 P6 R6 z* P h2 g
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();8 h: e. V8 a: k+ e3 Q
[color=rgba(0, 0, 0, 0.749019607843137)]
+ [2 F) Z0 n# e1 j
5 \: b% W. F+ T( F: L; |[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历% v9 e0 J! _$ e) N) f
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");
1 D, O/ l$ _5 u7 c8 c" d[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);# R3 y8 M% L) ^1 ~ i( G- A
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
) N3 o B# H, n. d) y1 n[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历% M: ^# b4 B' g* f1 W5 I* W8 t
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
2 L7 T# w# Y* [7 g% H' l6 P6 j[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
, u. ~8 A, j; {[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");# }$ C0 i0 X5 U2 |
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历" m/ N% y/ c5 f6 _- C. m
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");3 F/ Y/ ~$ v1 R# Z$ m' L! L6 {9 n1 g
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
1 Z; X2 ~. A! O) K; P: k3 Y+ u[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");9 d1 U2 J. R! V7 \7 M @
[color=rgba(0, 0, 0, 0.749019607843137)]
. T3 n0 l+ M: o1 w! E3 K, K! z# T/ W# |' ^- g9 j
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
% l; ^5 w- S) P+ i) |[color=rgba(0, 0, 0, 0.749019607843137)]}
- H# `4 _4 f2 q; {# [0 _[color=rgba(0, 0, 0, 0.749019607843137)]1
# O8 m; o* u" M% t, J8 T# R2 c[color=rgba(0, 0, 0, 0.749019607843137)]2 @3 A n3 J& O2 Z% |
[color=rgba(0, 0, 0, 0.749019607843137)]3, ?3 [) P7 X; c0 ~; G# R: k
[color=rgba(0, 0, 0, 0.749019607843137)]4
- {: x5 }9 j0 _[color=rgba(0, 0, 0, 0.749019607843137)]58 |2 u4 S: Z4 l) U3 |
[color=rgba(0, 0, 0, 0.749019607843137)]6
( I0 {6 C/ H, U2 }6 y0 j[color=rgba(0, 0, 0, 0.749019607843137)]7: E9 _3 k: T8 U2 O9 N) u
[color=rgba(0, 0, 0, 0.749019607843137)]8
) `8 _3 o* x+ C- C( g' _! c3 I! g[color=rgba(0, 0, 0, 0.749019607843137)]9
8 p6 _4 D& l' u* c2 h[color=rgba(0, 0, 0, 0.749019607843137)]10
1 T( B9 \9 V! i( a5 V f3 P+ x& a[color=rgba(0, 0, 0, 0.749019607843137)]11; _! N/ o2 Y5 v1 M
[color=rgba(0, 0, 0, 0.749019607843137)]12* A6 j; l `, B% I8 m
[color=rgba(0, 0, 0, 0.749019607843137)]13
0 D. t! }) N0 ~. m* E, c/ c[color=rgba(0, 0, 0, 0.749019607843137)]14+ n5 O2 i' |# T) J$ y4 c: ?# F
[color=rgba(0, 0, 0, 0.749019607843137)]15' g, N3 W( e& W8 x, ]9 j
[color=rgba(0, 0, 0, 0.749019607843137)]16
- Z& s; j) N: P! b* g `[color=rgba(0, 0, 0, 0.749019607843137)]17
& H& Z5 W( b! k1 S S[color=rgba(0, 0, 0, 0.749019607843137)]18
2 J' \! M9 z% @( @[color=rgba(0, 0, 0, 0.749019607843137)]19
4 {7 v; G4 V9 S* X6 x6 _) z1 H+ J[color=rgba(0, 0, 0, 0.749019607843137)]20
% T1 \3 O1 P$ W7 G I4 [[color=rgba(0, 0, 0, 0.749019607843137)]21
; `: O1 ?- A" s[color=rgba(0, 0, 0, 0.749019607843137)]22
5 |7 X9 T& |0 Z8 M! g[color=rgba(0, 0, 0, 0.749019607843137)]236 w z- U' h& B% \# T# v
[color=rgba(0, 0, 0, 0.749019607843137)]242 `+ ?* J u; q0 y5 O* W
[color=rgba(0, 0, 0, 0.749019607843137)]259 G, F7 _; H3 a( U+ H Q
[color=rgba(0, 0, 0, 0.749019607843137)]26
9 N9 o6 x8 M% N: z2 \[color=rgba(0, 0, 0, 0.749019607843137)]27
8 x$ G; b# l5 X$ M) i7 [6 f4 G[color=rgba(0, 0, 0, 0.749019607843137)]283 p# D6 Z) O9 G
[color=rgba(0, 0, 0, 0.749019607843137)]29
9 H6 M3 c. j. j4 s4 {4 B0 C3 }[color=rgba(0, 0, 0, 0.749019607843137)]30
# Z( x" a$ g$ {6 W[color=rgba(0, 0, 0, 0.749019607843137)]31
* t+ {* X n0 \- Y0 y4 j9 l[color=rgba(0, 0, 0, 0.749019607843137)]32
& f3 O2 Z" l3 B* j[color=rgba(0, 0, 0, 0.749019607843137)]33
4 n4 }/ g) l! N8 ~[color=rgba(0, 0, 0, 0.749019607843137)]346 i1 w2 C9 M; A, r- N9 G# ]
[color=rgba(0, 0, 0, 0.749019607843137)]35+ ?- _2 l. E2 x; X& w. D+ K [% d
[color=rgba(0, 0, 0, 0.749019607843137)]36' f1 D5 o* M& V( [# p' k2 i
[color=rgba(0, 0, 0, 0.749019607843137)]37
. q: G7 h# N: c, {% X[color=rgba(0, 0, 0, 0.749019607843137)]38) N2 o# i3 ^( q2 X( x8 [& ?
[color=rgba(0, 0, 0, 0.749019607843137)]39' ?+ ?/ R \7 K+ c
[color=rgba(0, 0, 0, 0.749019607843137)]40) H$ c- ?+ e' e( l' F0 K) Z3 m
[color=rgba(0, 0, 0, 0.749019607843137)]41
( U4 }8 G. f) E2 L7 q+ B[color=rgba(0, 0, 0, 0.749019607843137)]428 K" F' K0 }. I" Y% k- z
[color=rgba(0, 0, 0, 0.749019607843137)]43
! s1 \/ e7 A, j" x3 R! U[color=rgba(0, 0, 0, 0.749019607843137)]44
" r+ U& H# ?% B5 i[color=rgba(0, 0, 0, 0.749019607843137)]45+ `! X: ]' |7 d& y! Z4 A
[color=rgba(0, 0, 0, 0.749019607843137)]46
1 S# T$ B, V2 y8 k( z, ?/ m1 B[color=rgba(0, 0, 0, 0.749019607843137)]47. _/ M% {( A( M9 F: A
[color=rgba(0, 0, 0, 0.749019607843137)]48; I# f {+ L1 m' Y4 U/ i/ Z5 v
[color=rgba(0, 0, 0, 0.749019607843137)]49
4 ?7 X/ e6 f7 j6 A- s5 P[color=rgba(0, 0, 0, 0.749019607843137)]50+ c% R. E; ~# ^
[color=rgba(0, 0, 0, 0.749019607843137)]51
3 e& K5 O! }" q+ J0 g[color=rgba(0, 0, 0, 0.749019607843137)]525 n$ H1 R6 g F) K
[color=rgba(0, 0, 0, 0.749019607843137)]53
2 n) z9 r1 b: ^4 a+ g[color=rgba(0, 0, 0, 0.749019607843137)]544 {5 I7 r, K$ |% D2 ]# w9 g
[color=rgba(0, 0, 0, 0.749019607843137)]55
+ a3 c0 ]! B1 n9 p) a0 x9 e[color=rgba(0, 0, 0, 0.749019607843137)]56
% K, B" ?! ^& g' j[color=rgba(0, 0, 0, 0.749019607843137)]576 d( ~. j W- b+ Y/ t/ _- M
[color=rgba(0, 0, 0, 0.749019607843137)]58
4 y6 y* v2 U- G( O1 U9 m Y[color=rgba(0, 0, 0, 0.749019607843137)]59
( Y; I/ ^5 g9 ~1 F$ M1 v[color=rgba(0, 0, 0, 0.749019607843137)]60) k! S! a5 ]8 q; B
[color=rgba(0, 0, 0, 0.749019607843137)]617 I. v* N: v) }1 k, s3 Q1 M
[color=rgba(0, 0, 0, 0.749019607843137)]621 v/ J" P" k3 e [( b
[color=rgba(0, 0, 0, 0.749019607843137)]639 l: Q: _5 h$ ?/ |
[color=rgba(0, 0, 0, 0.749019607843137)]64
, M9 |( D1 t. a" \6 o1 x[color=rgba(0, 0, 0, 0.749019607843137)]65
: a2 O; b; w5 o0 G9 o4 }. G[color=rgba(0, 0, 0, 0.749019607843137)]663 I" a3 I1 s% f& C5 `3 S
[color=rgba(0, 0, 0, 0.749019607843137)]67
# v5 T! R9 g9 M( Z6 x[color=rgba(0, 0, 0, 0.749019607843137)]68
& e2 ]* h3 ^/ g6 g6 a[color=rgba(0, 0, 0, 0.749019607843137)]699 c$ H5 T1 x. h% d v! {& J- c, O
[color=rgba(0, 0, 0, 0.749019607843137)]70
* p6 y5 S+ t' M% ?* b3 V o* T[color=rgba(0, 0, 0, 0.749019607843137)]71
0 l. z/ U9 g9 ?2 T8 Q[color=rgba(0, 0, 0, 0.749019607843137)]72$ E* B, p/ Q1 W5 O3 d- Q3 J( |
[color=rgba(0, 0, 0, 0.749019607843137)]73
, b! U+ S% D- K+ H5 T1 D. R. R4 N[color=rgba(0, 0, 0, 0.749019607843137)]74! G# K3 S8 c. A. j5 q
[color=rgba(0, 0, 0, 0.749019607843137)]751 K: M4 H- r! W. b3 i
[color=rgba(0, 0, 0, 0.749019607843137)]76
3 i% v- o/ o7 U; C0 C2 D[color=rgba(0, 0, 0, 0.749019607843137)]77
2 s8 N8 s$ [) O: `* z[color=rgba(0, 0, 0, 0.749019607843137)]78, T. g5 m! x4 i- }
[color=rgba(0, 0, 0, 0.749019607843137)]79
' M" t" s: l$ S$ d: S1 O[color=rgba(0, 0, 0, 0.749019607843137)]80$ Y& N8 x4 ?" j2 { V. m
[color=rgba(0, 0, 0, 0.749019607843137)]81: s; y: q1 k# m" h3 t. p0 Y# u
[color=rgba(0, 0, 0, 0.749019607843137)]82
) ~1 x" C- @+ A[color=rgba(0, 0, 0, 0.749019607843137)]83
- J6 l: j: u# i5 }1 [[color=rgba(0, 0, 0, 0.749019607843137)]84
: H6 n+ T( C3 ?/ f+ M/ S' z# v6 y" o[color=rgba(0, 0, 0, 0.749019607843137)]85
5 [8 [, q' r8 b0 K6 x. E[color=rgba(0, 0, 0, 0.749019607843137)]86$ B. Q/ z3 O+ I0 X! x, k% \
[color=rgba(0, 0, 0, 0.749019607843137)]879 }( u3 W3 B- q# j" |) R" d2 [4 _
[color=rgba(0, 0, 0, 0.749019607843137)]88% K5 O) b9 x5 p& }( y# f# s1 I
[color=rgba(0, 0, 0, 0.749019607843137)]89* ^/ @2 h- H4 C# }7 w* }
[color=rgba(0, 0, 0, 0.749019607843137)]90- P5 C' d2 R# g- b" a
[color=rgba(0, 0, 0, 0.749019607843137)]91
( P- w8 v4 y6 V$ c1 J3 I[color=rgba(0, 0, 0, 0.749019607843137)]92
3 l' `. R7 N0 K* {# i' V5 M[color=rgba(0, 0, 0, 0.749019607843137)]938 P8 T& k, S& U, h: [
[color=rgba(0, 0, 0, 0.749019607843137)]94# L: b$ t6 z m/ A5 [; ^; b
[color=rgba(0, 0, 0, 0.749019607843137)]95/ i* }2 ~. B7 P7 L
[color=rgba(0, 0, 0, 0.749019607843137)]96! S+ @, k4 s) J2 v) P5 Y. ]
[color=rgba(0, 0, 0, 0.749019607843137)]97/ J G* w. r- P6 x$ { z4 ^3 Z+ V
[color=rgba(0, 0, 0, 0.749019607843137)]98
6 }1 U5 K |: L& ^[color=rgba(0, 0, 0, 0.749019607843137)]99* L( Y9 {. _: u: c- Y
[color=rgba(0, 0, 0, 0.749019607843137)]1008 u: `& ^9 o2 p8 C, \; ?2 R! U9 I
[color=rgba(0, 0, 0, 0.749019607843137)]101
# i: H" X4 ?! U6 q1 Q[color=rgba(0, 0, 0, 0.749019607843137)]102
8 e' I' g$ N( \8 z[color=rgba(0, 0, 0, 0.749019607843137)]103
% K) v; J2 {* ~7 M; Q W[color=rgba(0, 0, 0, 0.749019607843137)]104$ ]/ [ c; w: c( w5 V o
[color=rgba(0, 0, 0, 0.749019607843137)]1057 E: ^7 [& v7 ]& K D4 }' E1 |
[color=rgba(0, 0, 0, 0.749019607843137)]106
, E1 M9 ~3 j ]1 G2 y[color=rgba(0, 0, 0, 0.749019607843137)]107
7 u, `6 g$ ^* I: N, H[color=rgba(0, 0, 0, 0.749019607843137)]1087 ], s+ O' w0 `' v
[color=rgba(0, 0, 0, 0.749019607843137)]109" Z+ P3 [' Z2 o; T/ I- _! l" A
[color=rgba(0, 0, 0, 0.749019607843137)]110" W3 h0 X9 z. T% W' R* k
[color=rgba(0, 0, 0, 0.749019607843137)]111) Q& q/ q5 i; v6 b1 ~
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：, t& B3 }% n. u% K2 g' l
[color=rgba(0, 0, 0, 0.749019607843137)]$ {% M! O1 N' Y! R" c
% v! o5 ~+ H# L# O, R2 n
[color=rgba(0, 0, 0, 0.749019607843137)]
- X. r' p: @: @0 x- N) v) G
: H& ^) H4 i) m6 j ]: \- T A[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小8 [4 l, `3 d$ }& l
[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)
$ [5 q& ?' G* A! y" n: Q8 u[color=rgba(0, 0, 0, 0.749019607843137)]3 z- N) n" g$ {- U9 ?0 B
' B+ o% |) K+ W) F; S) Q" ~' [
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小( B' x3 ^0 u' E9 h6 _4 h
[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量0 k% \) z! E& i5 Y, T
[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
" a1 \$ }. {; D i* E[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)' o0 x+ B4 }3 v- u; {. z4 q. {4 c, B
[color=rgba(0, 0, 0, 0.749019607843137)]//{ }0 C* u9 y, T/ w5 q& w8 o u2 X
[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)
5 @* Q# {1 S/ d[color=rgba(0, 0, 0, 0.749019607843137)]// {( ~/ b8 s( A3 Q. n4 j- `
[color=rgba(0, 0, 0, 0.749019607843137)]// return;2 ]% h& [0 W2 S& V
[color=rgba(0, 0, 0, 0.749019607843137)]// }
7 l4 }' |! \' \) R9 R: v+ J[color=rgba(0, 0, 0, 0.749019607843137)]// count++; `. Y! G" b2 D3 n
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);
5 ?8 P5 _: }* D" G9 S& ^[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);) B5 i2 ^: h/ L; N9 C; [
[color=rgba(0, 0, 0, 0.749019607843137)]//
% s. k1 c L4 Z( K[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
2 z3 R: U; u0 x7 h$ D[color=rgba(0, 0, 0, 0.749019607843137)]//}1 B% ]: x& G$ t: {
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
" V6 M6 o. |& h6 a0 ^! I. Q1 K[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)5 }" \! r% @1 q. T' `2 H, M6 w$ h
[color=rgba(0, 0, 0, 0.749019607843137)]{ `. Y! C- O/ `$ A# {& A. s
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;, Z, u D: L1 m h: n2 ?7 d3 D
[color=rgba(0, 0, 0, 0.749019607843137)]}
* X/ B2 h5 t; r$ k5 m: f1 r[color=rgba(0, 0, 0, 0.749019607843137)]1
1 w0 b" Y6 A3 J- W4 X# B/ t[color=rgba(0, 0, 0, 0.749019607843137)]2
& `/ ?* k) g2 s6 T0 G, Y[color=rgba(0, 0, 0, 0.749019607843137)]3% {: N) w+ W O, P6 D
[color=rgba(0, 0, 0, 0.749019607843137)]4
) B0 c6 D: o1 N7 p[color=rgba(0, 0, 0, 0.749019607843137)]54 T2 ?6 f+ C0 w6 ^6 G {0 Z G% p# p
[color=rgba(0, 0, 0, 0.749019607843137)]67 Z# Y: ?" W2 i0 v+ k
[color=rgba(0, 0, 0, 0.749019607843137)]79 {* H3 H7 X6 X, M
[color=rgba(0, 0, 0, 0.749019607843137)]8; d; u+ j' Q$ Z9 x8 |. \& A7 q+ C
[color=rgba(0, 0, 0, 0.749019607843137)]9
0 Z( B$ @( T! O m: _# J8 s[color=rgba(0, 0, 0, 0.749019607843137)]10
- f2 s# y$ D$ j[color=rgba(0, 0, 0, 0.749019607843137)]11
( x3 C8 l. P0 g, j5 o; O/ n[color=rgba(0, 0, 0, 0.749019607843137)]12
; D3 N2 j9 S9 ]7 g[color=rgba(0, 0, 0, 0.749019607843137)]13
3 F' f7 t! q4 z+ I& }; r$ n[color=rgba(0, 0, 0, 0.749019607843137)]14
$ S# R) O: W6 l[color=rgba(0, 0, 0, 0.749019607843137)]15
8 C' P! J/ a2 p4 D[color=rgba(0, 0, 0, 0.749019607843137)]16( G& h9 n$ x6 v: T/ D) b
[color=rgba(0, 0, 0, 0.749019607843137)]172 ^; _2 h; V8 W" ^2 j
[color=rgba(0, 0, 0, 0.749019607843137)]187 U2 U( P/ w, d9 F
[color=rgba(0, 0, 0, 0.749019607843137)]19
8 y3 K) q* p+ P2 c4 v" v! \! ?[color=rgba(0, 0, 0, 0.749019607843137)]20
7 q+ m; {1 A0 W! H[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数$ ^& D$ B" i+ _
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数3 Q$ D7 m7 @/ _/ l, k5 ^
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
& q8 x# N3 A/ l* Z[color=rgba(0, 0, 0, 0.749019607843137)]{% G. J, Q" T/ j1 C8 U3 }
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点% N8 @; z( ]7 U6 M# O' E
[color=rgba(0, 0, 0, 0.749019607843137)] {
& t6 b, y% s) W% u: ]$ A7 A[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
# Y: M+ s: e1 B7 l& B! P[color=rgba(0, 0, 0, 0.749019607843137)] }
$ T0 g/ D, t: J. \. z3 V. |[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
" Q% a6 B& i% w: ]- I# i# s[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)5 N, m+ T* v( n8 O* t. x
[color=rgba(0, 0, 0, 0.749019607843137)] {1 e' P/ C- d2 ^* L
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;0 j3 L0 B# q- V# m
[color=rgba(0, 0, 0, 0.749019607843137)] }' M& g8 \9 }2 t7 }% {; E' p
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);- u! b% {: g* p( X' M( b
[color=rgba(0, 0, 0, 0.749019607843137)]}4 r1 y5 f) N7 a' m
[color=rgba(0, 0, 0, 0.749019607843137)]1
" m. o4 F* h* r1 L4 f% R: Z[color=rgba(0, 0, 0, 0.749019607843137)]2
1 i- _+ B# q2 y5 t9 v/ X S[color=rgba(0, 0, 0, 0.749019607843137)]3
/ U9 O" S: M* z7 {[color=rgba(0, 0, 0, 0.749019607843137)]4" M& q* Q. L0 D2 K5 x
[color=rgba(0, 0, 0, 0.749019607843137)]56 \: o! y+ k+ s8 `7 B
[color=rgba(0, 0, 0, 0.749019607843137)]6
) l8 Q6 c/ u0 w' N. G: \[color=rgba(0, 0, 0, 0.749019607843137)]7
5 h( p& V# ?) A) i+ ~( _[color=rgba(0, 0, 0, 0.749019607843137)]8/ j0 ]5 }: X$ k" q/ j
[color=rgba(0, 0, 0, 0.749019607843137)]9
9 r& P) D5 G; J% E[color=rgba(0, 0, 0, 0.749019607843137)]10
$ f; M: z& Z& r! u4 l[color=rgba(0, 0, 0, 0.749019607843137)]11
- c0 J$ v( h3 ~. A3 ?. h: J/ _5 h! B[color=rgba(0, 0, 0, 0.749019607843137)]126 F, h. X1 Z- X/ B. [" ~% E+ l
[color=rgba(0, 0, 0, 0.749019607843137)]13
! D" t- |9 y i( I8 J7 O[color=rgba(0, 0, 0, 0.749019607843137)]14! ~- D: X J2 h4 ~& ?
[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度
0 g1 d6 `% ?0 J3 x) v; Y, Z7 ^" @* u[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root). R: G3 Y* h' M
[color=rgba(0, 0, 0, 0.749019607843137)]{
3 g. W5 ~9 ]" j. S* }" m' V* Q[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0/ I; }/ o% C- l4 ~" v
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)- q& S: B( s. {( k
[color=rgba(0, 0, 0, 0.749019607843137)] {
* L5 M8 K" Y- s4 x[color=rgba(0, 0, 0, 0.749019607843137)] return 0;5 W* }2 {+ s) F9 E3 Z7 m& h
[color=rgba(0, 0, 0, 0.749019607843137)] }
* c2 c9 K- @ V1 q& H! V[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树" X* }% _0 t: U
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度, Q5 \/ b4 {' G0 E9 S4 b4 c" t+ t9 s2 E
[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度1 P3 Z& J( c( b) ]
[color=rgba(0, 0, 0, 0.749019607843137)]
1 s ^4 N5 ]8 k6 j4 ] Q' n* [& i0 C9 l
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;% G! U: {2 \0 Y
[color=rgba(0, 0, 0, 0.749019607843137)]}
( e) o# X) q. n- ]' w/ D[color=rgba(0, 0, 0, 0.749019607843137)]1& c4 z; j3 p4 P! p; E+ _
[color=rgba(0, 0, 0, 0.749019607843137)]2
2 {4 w+ b- t$ Y6 p2 r% t, I& ?[color=rgba(0, 0, 0, 0.749019607843137)]3) j6 }4 G% r% w" B% l
[color=rgba(0, 0, 0, 0.749019607843137)]4
& y' f, |# a5 \% Z3 E. a, Q[color=rgba(0, 0, 0, 0.749019607843137)]50 o: V6 B. ?! w; R, S' |
[color=rgba(0, 0, 0, 0.749019607843137)]6
/ o' i% |+ v' @ L1 F[color=rgba(0, 0, 0, 0.749019607843137)]7
$ k* n J; Z6 j& \9 k* f[color=rgba(0, 0, 0, 0.749019607843137)]85 ?4 U7 C2 L% ^. C7 Y7 x
[color=rgba(0, 0, 0, 0.749019607843137)]9
& [; R4 q R# f" x- J[color=rgba(0, 0, 0, 0.749019607843137)]10
* N! ]4 u3 ^ n; U, [[color=rgba(0, 0, 0, 0.749019607843137)]11# g6 L! [& p% k5 e! G
[color=rgba(0, 0, 0, 0.749019607843137)]12) B) |$ \/ F& A) U& g8 d
[color=rgba(0, 0, 0, 0.749019607843137)]139 _) T8 W% t0 K8 o8 y4 J: H6 g3 H
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
/ a* |8 s( }: P" M[color=rgba(0, 0, 0, 0.749019607843137)]
" f; @. R4 H0 V) z9 n8 X& g; [9 p o* p! i. t6 X
[color=rgba(0, 0, 0, 0.749019607843137)]
$ u& l1 P1 o: p, q/ o& I7 n6 d; X0 Y6 e- K; X1 n; N
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。- Z C' X0 X- Z( T) {
[color=rgba(0, 0, 0, 0.749019607843137)]
/ A; F5 r# g3 E8 o$ t+ m- J9 D) ]. p$ z
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数6 ^; u0 p7 j% H4 `- G5 C; i1 {
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)5 F" C! t6 [! @% B! m) `- D
[color=rgba(0, 0, 0, 0.749019607843137)]{
* a5 m( E. \& p$ [1 l[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);) B: D2 `! {$ c' w
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)0 X; I6 e. C) Q
[color=rgba(0, 0, 0, 0.749019607843137)] {
Y3 D' }5 ~! Y( Y" z- j0 x( n: W[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
8 S. j& W# z" M5 g5 ^) v( e( W3 l[color=rgba(0, 0, 0, 0.749019607843137)] }
) v1 t! K8 _ s/ O |[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)5 Y" ?9 \8 }) H; S
[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
* k( D- t& L3 Z! |. ]9 d2 Q( w[color=rgba(0, 0, 0, 0.749019607843137)] {% I: i, |, i! e0 \5 v$ j
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;5 U; [. R; y" M9 J# M9 T% N' }
[color=rgba(0, 0, 0, 0.749019607843137)] }
- \4 G0 @5 U( ?5 G4 N[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层$ ?- B0 Z8 ^+ c8 o0 H" [3 c% G
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);( k5 k/ W# L, ?
[color=rgba(0, 0, 0, 0.749019607843137)]}3 n& ?3 P) b$ f) S
[color=rgba(0, 0, 0, 0.749019607843137)]1+ Q; {/ ~: x7 Q8 `" z
[color=rgba(0, 0, 0, 0.749019607843137)]2
" a& b! ]9 r' P. n. q[color=rgba(0, 0, 0, 0.749019607843137)]3+ z/ N1 n# @4 [+ S# z3 R- K$ M
[color=rgba(0, 0, 0, 0.749019607843137)]4
: o" s% B5 t8 m2 ~. \( S! O[color=rgba(0, 0, 0, 0.749019607843137)]5% ?4 F0 f) j- x& I
[color=rgba(0, 0, 0, 0.749019607843137)]6' B$ P. u$ P+ v9 x
[color=rgba(0, 0, 0, 0.749019607843137)]7, r1 I5 U# f7 Q+ z
[color=rgba(0, 0, 0, 0.749019607843137)]83 h* _: b5 B% m" K- Q
[color=rgba(0, 0, 0, 0.749019607843137)]9
. C: J/ o1 p" Y1 o1 D, b. C[color=rgba(0, 0, 0, 0.749019607843137)]10
* M5 w! P4 K3 F% G[color=rgba(0, 0, 0, 0.749019607843137)]11/ d3 _$ c+ _( S" k1 k, ?7 V# n
[color=rgba(0, 0, 0, 0.749019607843137)]12+ D, s4 {: |, i: S7 \* y* n3 I
[color=rgba(0, 0, 0, 0.749019607843137)]13$ f1 N+ w4 k- ^% a5 h) D1 b
[color=rgba(0, 0, 0, 0.749019607843137)]147 J ^! s' K! O8 O0 L
[color=rgba(0, 0, 0, 0.749019607843137)]15
* `" j9 Y, i" N+ l. R& I[color=rgba(0, 0, 0, 0.749019607843137)]16! r8 y, c; w$ f8 y* r0 g
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找( O) Y/ d0 l. g$ x3 V7 W; _
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找/ @5 ~8 A/ g9 G' m
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)* f8 a' g# }# m& C' w
[color=rgba(0, 0, 0, 0.749019607843137)]{4 @9 [2 X# ?) @5 [) k% h
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
, a" D9 H( N$ M5 n( B[color=rgba(0, 0, 0, 0.749019607843137)] {
3 u+ e$ _8 A2 t[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
7 g, e$ m6 `8 z' k# m5 o- L[color=rgba(0, 0, 0, 0.749019607843137)] }+ I7 k _* e$ q9 e( k
[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)9 [/ X" Z' \" i
[color=rgba(0, 0, 0, 0.749019607843137)] {9 s% m$ T% n1 P/ [
[color=rgba(0, 0, 0, 0.749019607843137)] return root;3 I2 \2 }, S( f* p! w8 ^( G
[color=rgba(0, 0, 0, 0.749019607843137)] }
8 E. m5 T& z4 D& ?[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
3 @- Q1 {& c% g# }" ?: s( m[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);
e# i. D4 s/ e1 F$ n+ N4 a[color=rgba(0, 0, 0, 0.749019607843137)] if (lret), M" d6 ~2 [' V0 h; S" h
[color=rgba(0, 0, 0, 0.749019607843137)] return lret;
- ^. ?+ }3 L6 J, m[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树
; H% d4 p }* Z, x) q[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);
% y0 Q* F |* T' c1 w- J3 f+ ~[color=rgba(0, 0, 0, 0.749019607843137)] if (rret). R( [, d! k) K8 q; i! n: t
[color=rgba(0, 0, 0, 0.749019607843137)] return rret;/ @# K" P5 u& \0 g; I
[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;
6 q% e4 r/ w' K2 @$ O[color=rgba(0, 0, 0, 0.749019607843137)]}
( Z7 ~7 C5 E) _: t6 Z) A$ K[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
, s: k% |7 ?8 G7 J[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
; ?8 O. [/ C1 T. n/ p$ J2 y; u[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/126841212
4 ?& W- B8 [# \5 ^6 p1 m, A; Y4 @
5 D0 V/ d- E2 h- h
( W q4 i+ r! Y; M- V9 C[color=rgba(0, 0, 0, 0.75)]
1 a5 g C9 x+ z8 J ?1 B7 ^4 c% D$ `4 o; I+ Z6 t- P9 K: _& Z3 _
4 z: m6 c+ _# Z7 G: }' o
) l2 o' D! @5 n |
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
