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