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