【数据结构】二叉树的遍历：前序，中序，后序的递归结构遍历9 l h, ?) Q6 l; ^" A7 Z0 ?$ f4 b' K
7 ], N/ ?) Q0 k8 r1 {: _. ^[color=rgba(0, 0, 0, 0.749019607843137)]文章目录
/ n6 R9 I5 h& M- W& k% I[color=rgba(0, 0, 0, 0.749019607843137)]前言7 `- t7 p0 @: Q+ Y& q
[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
+ }4 W$ f# |; O H, f- F[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）. ]3 w6 f0 _5 e- H" q8 f2 @
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
/ ]: E+ D7 o- t- J; D, l[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
8 E: N$ j. e k! J7 k7 j4 l[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数
3 I8 x1 C$ O# b7 f+ z[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度9 B: f! G7 U9 t7 P7 b5 b0 G) y
[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数3 A7 H2 V( f2 W: C
[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找
2 ]% h6 }4 J# z[color=rgba(0, 0, 0, 0.749019607843137)]前言
% |* E$ h7 _ `2 d* e. Y[color=rgba(0, 0, 0, 0.749019607843137)]在学习二叉树的遍历之前，我们需要先创建一棵二叉树，然后才能学习其相关的基本操作，由于现在我们对二叉树结构的掌握还在初阶部分，为了降低大家的学习成本，我们先手动快速创建一棵简单的二叉树，快速进入二叉树的操作学习，这个方法在我们调试程序代码的时候，也非常适用。等二叉树结构了解的差不多时，我们再继续研究二叉树真正的创建方式。4 m/ Y+ C/ R- ^
[color=rgba(0, 0, 0, 0.749019607843137)]
: f7 V2 |0 |, t2 g4 {: I" X
# q3 S6 E6 V: m8 u/ I[color=rgba(0, 0, 0, 0.749019607843137)]1.二叉树的遍历方式
+ k1 g$ n6 D2 \4 x2 l5 E[color=rgba(0, 0, 0, 0.749019607843137)]9 G5 i7 u5 S6 F/ G. |# T
) ~, f' u% l+ }/ T: s* ?8 a[color=rgba(0, 0, 0, 0.749019607843137)]按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历访问顺序：' s8 J$ m+ u3 d; r0 |$ A
[color=rgba(0, 0, 0, 0.749019607843137)]
: }7 t: O U# p1 e2 U+ Y" `0 W/ _6 C& E R: S
[color=rgba(0, 0, 0, 0.749019607843137)]1. 前序遍历（先序，先根):根——左子树——右子树
o9 q$ I$ N" U' J: x[color=rgba(0, 0, 0, 0.749019607843137)]6 }2 ^% s; @3 L5 L) L0 f" D8 C
+ X, P1 b$ d& q1 c
[color=rgba(0, 0, 0, 0.749019607843137)]8 s9 m7 Y; S4 V# Q9 X
) w( z# ~) A6 Z: a" y# ]
[color=rgba(0, 0, 0, 0.749019607843137)]2. 中序遍历（中根）：左子树——根——右子树' R' }6 w. m( f. a6 J0 U4 v+ ^
[color=rgba(0, 0, 0, 0.749019607843137)]
8 q, O. d4 d9 X5 u9 g
+ y" [, q; u5 {6 _9 H* J1 B2 i. c4 P[color=rgba(0, 0, 0, 0.749019607843137)]
: _5 c0 p+ {& W- p5 D* \1 v
% e8 \, U$ B+ f) {$ S" A. I ^[color=rgba(0, 0, 0, 0.749019607843137)]3. 后序遍历（后根）：左子树——右子树——根
v% K- U7 Q- l1 e[color=rgba(0, 0, 0, 0.749019607843137)]3 t. a y$ s, w% g! @
: i! A( W$ C2 N4 s# I
[color=rgba(0, 0, 0, 0.749019607843137)]; Z$ ^2 W3 Z/ X3 [3 [2 |( T0 d2 h8 l
, L' L" x$ W0 f" N: V( ]6 R% X3 E/ N( z
[color=rgba(0, 0, 0, 0.749019607843137)]2.二叉树的遍历及相关函数（代码实现）
& X6 Q$ B" y6 e7 I[color=rgba(0, 0, 0, 0.749019607843137)]思路：分而治之' k; }/ [9 O2 N1 q% h6 Q- m
[color=rgba(0, 0, 0, 0.749019607843137)]1.首先我们要用简单的方式先创建出一棵二叉树，并赋予数据；/ h( g. V; V$ H; r, @
[color=rgba(0, 0, 0, 0.749019607843137)]2.采用递归的方式，分别实现前序/中序/后序遍历这棵二叉树；+ ^5 E9 C. f1 B( h/ t
[color=rgba(0, 0, 0, 0.749019607843137)]3.尝试计算这个二叉树的大小（利用递归）；
. i2 j4 W5 x6 G) ] [[color=rgba(0, 0, 0, 0.749019607843137)]4.尝试计算叶子结点的个数（利用递归）；' a) x3 J2 C+ U, h: |
[color=rgba(0, 0, 0, 0.749019607843137)]5.尝试计算二叉树的高度（利用递归）；$ p7 K. \ y# ]
[color=rgba(0, 0, 0, 0.749019607843137)]6.尝试写出计算第K层结点的个数的函数（利用递归）；
; V: N$ Q. y. Q[color=rgba(0, 0, 0, 0.749019607843137)]7.尝试写出二叉树查找的函数（利用递归）。
6 K |: n* ~+ |9 F/ t[color=rgba(0, 0, 0, 0.749019607843137)]
6 ]4 r% |# ]( Z$ o/ |; L# @$ t8 e* \ |) `; O2 s6 r
[color=rgba(0, 0, 0, 0.749019607843137)]2.1前序/中序/后序的遍历
6 h: L0 S4 Q: d! _4 }[color=rgba(0, 0, 0, 0.749019607843137)]#define _CRT_SECURE_NO_WARNINGS 1: @% v% ~$ C0 A O; w: D
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdio.h>
9 D6 R, F: N' `" {" E5 G, X[color=rgba(0, 0, 0, 0.749019607843137)]#include<assert.h>5 g9 l* @1 u$ A' N
[color=rgba(0, 0, 0, 0.749019607843137)]#include<stdlib.h>
% a, t1 |' p0 H4 U+ \( Q$ ?[color=rgba(0, 0, 0, 0.749019607843137)]! H9 P! h, c8 D$ N- y- J$ C9 ~/ m
: m8 l5 d" d: K/ b) E1 _( h[color=rgba(0, 0, 0, 0.749019607843137)]typedef int BTDataType;* W# {& j, X: m f+ R
[color=rgba(0, 0, 0, 0.749019607843137)]
5 A1 ]* d8 Q/ G% K! [% H1 E3 k" Q% H M2 `7 n f+ a4 T# {" o2 l* [
[color=rgba(0, 0, 0, 0.749019607843137)]//定义二叉树结点的结构体
8 J, R+ ~% y2 L- O; `9 g4 {2 }[color=rgba(0, 0, 0, 0.749019607843137)]typedef struct BinaryTreeNode
! g5 ^/ \# O( ?: L[color=rgba(0, 0, 0, 0.749019607843137)]{
" H6 U6 @0 f1 W9 j[color=rgba(0, 0, 0, 0.749019607843137)] BTDataType data;: y; v7 G1 X. d: h/ ~
[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* left;
% f! h I5 }7 K; u# T[color=rgba(0, 0, 0, 0.749019607843137)] struct BinaryTreeNode* right;" Z9 W; \- E# Z% V9 t
[color=rgba(0, 0, 0, 0.749019607843137)]}BTNode;
$ ]- a. @, |. i# o0 W. {( W[color=rgba(0, 0, 0, 0.749019607843137)]
) U/ p5 {8 b6 t3 ~0 b4 L+ {
! T/ H6 N9 l0 a3 [* l! n$ X$ s[color=rgba(0, 0, 0, 0.749019607843137)]//前序遍历
[. y: C0 K6 x) W: N/ @[color=rgba(0, 0, 0, 0.749019607843137)]void PreOrder(BTNode* root)
$ E; M9 o# c! H8 i8 v# I[color=rgba(0, 0, 0, 0.749019607843137)]{
- `5 y( y, V5 j[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
4 n5 f7 o/ A8 o* V U[color=rgba(0, 0, 0, 0.749019607843137)] {; |. Z/ N* c# ^7 [9 c2 e) @5 b
[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");
( c) q7 K( C) f4 D# M( @[color=rgba(0, 0, 0, 0.749019607843137)] return;8 ~6 K1 L' N u' |# @5 `
[color=rgba(0, 0, 0, 0.749019607843137)] }
0 p: v6 b; e& S6 z9 ?/ C[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
; M3 c/ P o# o, i9 |9 Q, ]# d[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->left); V2 X3 R. h% s
[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root->right);& C$ K$ M! |, j: n$ c6 J
[color=rgba(0, 0, 0, 0.749019607843137)]}
" [$ g: n1 r/ U[color=rgba(0, 0, 0, 0.749019607843137)]//中序遍历% y) {$ q. b, m1 N3 a5 J( k% y+ H
[color=rgba(0, 0, 0, 0.749019607843137)]void InOrder(BTNode* root)* P }! b! o W
[color=rgba(0, 0, 0, 0.749019607843137)]{
, R3 |4 N4 u+ s: Z6 \[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)+ C8 y1 D2 `9 Y7 _, `% n* ?
[color=rgba(0, 0, 0, 0.749019607843137)] {
0 l& ?6 A) ]4 T! Y% | T[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");( d; X( `$ x, J1 X. _9 s
[color=rgba(0, 0, 0, 0.749019607843137)] return;: b, ~4 c; V/ B
[color=rgba(0, 0, 0, 0.749019607843137)] }
# x6 z7 L5 n6 ]# L4 c% h0 f; B1 y[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->left);0 v, \! ?1 E8 k& g: @0 |7 g9 H
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);, y1 O$ n. {8 }& M
[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root->right);
1 w o% P' b6 J( H[color=rgba(0, 0, 0, 0.749019607843137)]}8 l# W3 O. [8 C
[color=rgba(0, 0, 0, 0.749019607843137)]//后序遍历
3 e3 q. [+ Z9 ^7 Y# B[color=rgba(0, 0, 0, 0.749019607843137)]void PostOrder(BTNode* root)) a% }6 A( c' {5 X
[color=rgba(0, 0, 0, 0.749019607843137)]{
$ a7 ], n$ O( ^+ d, h% d( }[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
! J @- [! I2 j3 M/ y[color=rgba(0, 0, 0, 0.749019607843137)] {
# P+ Y! @: w A7 E7 i[color=rgba(0, 0, 0, 0.749019607843137)] printf("NULL ");9 F ~3 _2 ?% ^! i1 l+ j4 X7 D, B
[color=rgba(0, 0, 0, 0.749019607843137)] return;
( S4 b: }% c, w! Z; M7 w[color=rgba(0, 0, 0, 0.749019607843137)] }
1 B: g+ F$ W5 \! l; l2 N! G[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->left);0 t' E2 Z, }7 B& |& j" B1 h7 ^
[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root->right);$ c# D# m/ Q4 M! k+ j
[color=rgba(0, 0, 0, 0.749019607843137)] printf("%d ", root->data);
; F/ O) i0 p$ h( b; I[color=rgba(0, 0, 0, 0.749019607843137)]}
6 Z# t$ T5 v: `+ a8 C+ T. i[color=rgba(0, 0, 0, 0.749019607843137)]//先创建一个简单的二叉树结构2 Z3 z# _# d, }' Q/ R( y
[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* CreateTree()7 z0 R: P8 F+ G( n, B
[color=rgba(0, 0, 0, 0.749019607843137)]{
; p% X4 M2 l0 D6 I' a) ~4 X7 v[color=rgba(0, 0, 0, 0.749019607843137)] //先动态开辟6个结点的空间8 l# D) N3 s9 ~6 H
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n1 = (BTNode*)malloc(sizeof(BTNode));+ ]% Q& w$ p# L/ }2 N
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n1);
/ ?9 `6 x) }( ~$ G) \2 j[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n2 = (BTNode*)malloc(sizeof(BTNode));$ p1 r; T! q( Q! {# f
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n2);
/ E! H& K, x0 o3 s* G' E7 \( K[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n3 = (BTNode*)malloc(sizeof(BTNode));
$ D- I8 ?" \3 p6 C; V+ ?+ Z[color=rgba(0, 0, 0, 0.749019607843137)] assert(n3);
! K8 P& h7 s* T; R' u5 k0 F[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n4 = (BTNode*)malloc(sizeof(BTNode));0 ^/ b$ z2 i* l# m1 X; @) H
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n4);
7 w- e) r8 O6 e- u) b) {[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n5 = (BTNode*)malloc(sizeof(BTNode));
4 V" J% s! V. t+ [[color=rgba(0, 0, 0, 0.749019607843137)] assert(n5);
4 C# |; N: {% X/ ]( A% A5 |[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* n6 = (BTNode*)malloc(sizeof(BTNode));& ^( S; L7 U- S n
[color=rgba(0, 0, 0, 0.749019607843137)] assert(n6);7 M9 |& L7 n" L% ?% ?
[color=rgba(0, 0, 0, 0.749019607843137)]# z& C' K& `* j7 t$ g5 q
. w) D, Z* Q2 u+ \; @[color=rgba(0, 0, 0, 0.749019607843137)] n1->data = 1;( U% d- N. p* X, J' I8 f
[color=rgba(0, 0, 0, 0.749019607843137)] n2->data = 2;
" C/ J. J# d# b$ F# u& N[color=rgba(0, 0, 0, 0.749019607843137)] n3->data = 3;" R; F, I$ h: f, P Q
[color=rgba(0, 0, 0, 0.749019607843137)] n4->data = 4;
: \2 o! i* V: r& y[color=rgba(0, 0, 0, 0.749019607843137)] n5->data = 5;: K; E4 B3 p) r6 |0 ^; o! l
[color=rgba(0, 0, 0, 0.749019607843137)] n6->data = 6;
0 t3 |1 h0 e, M[color=rgba(0, 0, 0, 0.749019607843137)]' J* `6 e1 Q# n3 T7 h$ F! M
( `; n3 U. _1 D9 W( G[color=rgba(0, 0, 0, 0.749019607843137)] n1->left = n2;& L# L+ y" A' ~# [& a
[color=rgba(0, 0, 0, 0.749019607843137)] n1->right = n4;
# D* U. u* t8 k' w, J8 F[color=rgba(0, 0, 0, 0.749019607843137)] n2->left = n3;9 {+ h5 K# i2 X1 B' V) t! e9 b
[color=rgba(0, 0, 0, 0.749019607843137)] n2->right = NULL;
, [% o3 W% w+ i. {, G[color=rgba(0, 0, 0, 0.749019607843137)] n3->left = NULL;
; R% J9 J% L1 f. w[color=rgba(0, 0, 0, 0.749019607843137)] n3->right = NULL;
* _# |$ }) M2 R# Q# ?[color=rgba(0, 0, 0, 0.749019607843137)] n4->left = n5;
4 l ]9 l5 r9 I/ |8 z7 _+ @[color=rgba(0, 0, 0, 0.749019607843137)] n4->right = n6;' F5 X7 H, O! d" I* Q+ P0 ?
[color=rgba(0, 0, 0, 0.749019607843137)] n5->left = NULL;
5 R' `# h3 C; W$ S# |6 a[color=rgba(0, 0, 0, 0.749019607843137)] n5->right = NULL;1 F1 V- M2 z7 p3 T, ^0 X
[color=rgba(0, 0, 0, 0.749019607843137)] n6->left = NULL;
, A5 V5 Z* C* I' X2 Y4 C[color=rgba(0, 0, 0, 0.749019607843137)] n6->right = NULL;
2 ?2 K& r! X$ R( H[color=rgba(0, 0, 0, 0.749019607843137)]
' z: `: r1 P4 z" V
' a; y/ I! y$ D# W7 ]. O[color=rgba(0, 0, 0, 0.749019607843137)] return n1;
# @$ r' S4 d3 \5 {[color=rgba(0, 0, 0, 0.749019607843137)]}& [! Q: m3 q5 N; \
[color=rgba(0, 0, 0, 0.749019607843137)]
8 _& J, @: D z" T2 I. d% Z
% @0 [8 ~( c4 L' N# b# u+ P: x; g[color=rgba(0, 0, 0, 0.749019607843137)]int main()
6 p; D2 ~: Y9 Z! V[color=rgba(0, 0, 0, 0.749019607843137)]{% f$ l V# B3 M' E% c( ~
[color=rgba(0, 0, 0, 0.749019607843137)] //先创建一个简单的二叉树结构
0 A! V+ X, Y* v2 g9 g8 C- }[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* root = CreateTree();" F) \. H! y/ r) m/ j
[color=rgba(0, 0, 0, 0.749019607843137)]
/ s, N% |" O" d2 q! ~' E
0 s! o- b4 Q+ G( D[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树前序遍历
6 j- y: ~& ]8 }6 n3 J[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树前序遍历:");
$ h0 E( {5 m" A2 ?: S[color=rgba(0, 0, 0, 0.749019607843137)] PreOrder(root);$ ^: H% u3 e3 T3 B6 K4 B# r _
[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");# _$ K- e- x$ ^6 O
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树中序遍历" W3 c) R; B1 \
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树中序序遍历:");
) s; X) P. y" r6 {: l3 o1 T( {* |[color=rgba(0, 0, 0, 0.749019607843137)] InOrder(root);
9 b( Y% h1 z M[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");, A& W& N3 X1 |
[color=rgba(0, 0, 0, 0.749019607843137)] //二叉树后序遍历* X$ a4 c( D" b7 p, B
[color=rgba(0, 0, 0, 0.749019607843137)] printf("二叉树后序遍历:");
8 E) H3 ?% N+ q" q0 e( d[color=rgba(0, 0, 0, 0.749019607843137)] PostOrder(root);
* k( U% M: o. c7 p8 [5 J[color=rgba(0, 0, 0, 0.749019607843137)] printf("\n");
, \- K' C' S1 z0 T; e3 \: U N! x[color=rgba(0, 0, 0, 0.749019607843137)]
, }( T8 W8 L$ H2 u' y2 e2 b/ k, x5 Y+ o. {# z& D5 S
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;3 d0 w* d* A' p/ U. D0 E
[color=rgba(0, 0, 0, 0.749019607843137)]}
6 X7 x8 _8 L- Q1 N1 _! ~* a: @$ z[color=rgba(0, 0, 0, 0.749019607843137)]1
! I# K, `: \0 t# k& @0 K6 @[color=rgba(0, 0, 0, 0.749019607843137)]2" L+ D- Y: X, N. Y0 k) [
[color=rgba(0, 0, 0, 0.749019607843137)]3
" h9 P) z5 S9 R) {$ S: G[color=rgba(0, 0, 0, 0.749019607843137)]4
' Y6 Y \9 q$ p3 P D- a8 [- f |+ `[color=rgba(0, 0, 0, 0.749019607843137)]5+ l$ _; I6 Y$ I" ~% B5 p3 ~; W& C7 {
[color=rgba(0, 0, 0, 0.749019607843137)]6
' f) C$ Y- O8 k- w6 ^[color=rgba(0, 0, 0, 0.749019607843137)]7
: g8 k0 K& w& k( d6 n3 m[color=rgba(0, 0, 0, 0.749019607843137)]8
$ }6 o# C( G" ^[color=rgba(0, 0, 0, 0.749019607843137)]9
) h- x: G6 y, Q! H+ k[color=rgba(0, 0, 0, 0.749019607843137)]10
5 Y$ X' |0 \" B" [! q3 Q[color=rgba(0, 0, 0, 0.749019607843137)]11
4 [; g4 K* ^/ j6 O; o+ C1 G[color=rgba(0, 0, 0, 0.749019607843137)]12
7 c! b7 M m7 J) K$ D1 \[color=rgba(0, 0, 0, 0.749019607843137)]13
, n) T. E9 x6 ~/ ^$ A[color=rgba(0, 0, 0, 0.749019607843137)]14
" ?3 ^" ]1 r6 g( q8 D1 I: l( x[color=rgba(0, 0, 0, 0.749019607843137)]155 p6 `8 y) }3 o. ~
[color=rgba(0, 0, 0, 0.749019607843137)]16& U) l. P0 t( i/ i# z1 ]2 k2 V
[color=rgba(0, 0, 0, 0.749019607843137)]175 X; ~" w8 f- c0 m+ H9 c# i
[color=rgba(0, 0, 0, 0.749019607843137)]18' q9 ~0 I' j3 B: k. t2 @
[color=rgba(0, 0, 0, 0.749019607843137)]19
. v+ O% ] q. ^/ ?, y[color=rgba(0, 0, 0, 0.749019607843137)]20
/ j, g3 k1 V L/ N[color=rgba(0, 0, 0, 0.749019607843137)]21
4 {" n8 Z! \1 B: F[color=rgba(0, 0, 0, 0.749019607843137)]222 S/ O5 x( a6 X& o4 N ?- Z
[color=rgba(0, 0, 0, 0.749019607843137)]23
, q1 B/ ^1 O( I9 e% i0 h8 z[color=rgba(0, 0, 0, 0.749019607843137)]24
6 H. h7 U- Z+ G[color=rgba(0, 0, 0, 0.749019607843137)]25
# C j! q S; i$ i- }[color=rgba(0, 0, 0, 0.749019607843137)]26
$ O. t/ F4 l! n8 b0 K[color=rgba(0, 0, 0, 0.749019607843137)]27
2 Y) Z3 X' g; M5 b5 }[color=rgba(0, 0, 0, 0.749019607843137)]284 z+ {, Q" K p6 ~# T
[color=rgba(0, 0, 0, 0.749019607843137)]29
9 t7 a. i& X: Y" X/ ?& A9 O[color=rgba(0, 0, 0, 0.749019607843137)]30
' b& f3 A9 F9 @) G) ^[color=rgba(0, 0, 0, 0.749019607843137)]31
. o" c$ h0 z3 u" Y& ^ v[color=rgba(0, 0, 0, 0.749019607843137)]327 H9 A `) Z( X, F
[color=rgba(0, 0, 0, 0.749019607843137)]332 ?5 f- N4 L( y0 v$ _, ~
[color=rgba(0, 0, 0, 0.749019607843137)]341 J" r8 H: {5 m, A: W7 a' v
[color=rgba(0, 0, 0, 0.749019607843137)]351 r) z9 ?; l9 t; Q
[color=rgba(0, 0, 0, 0.749019607843137)]36 K% ^5 q% t. _( w ] P$ g
[color=rgba(0, 0, 0, 0.749019607843137)]37
# N. _& C4 C1 V7 E7 u! b[color=rgba(0, 0, 0, 0.749019607843137)]38
- K; u9 O7 Q. h" Q) P$ L4 C; |# ^) R1 W[color=rgba(0, 0, 0, 0.749019607843137)]39
3 H: l* d; r& V ^$ k[color=rgba(0, 0, 0, 0.749019607843137)]40* I" y9 k; v6 y2 {' Z& t7 t
[color=rgba(0, 0, 0, 0.749019607843137)]41' i4 J4 }' c9 I: k
[color=rgba(0, 0, 0, 0.749019607843137)]426 s+ ], q0 N$ b3 V5 K6 L/ @- o
[color=rgba(0, 0, 0, 0.749019607843137)]438 G( l: V; U" Y. F) h* O( y8 U" Z
[color=rgba(0, 0, 0, 0.749019607843137)]44
, G- ]( _. u, y" ~% d[color=rgba(0, 0, 0, 0.749019607843137)]45
4 C9 \8 q" Z( L3 L% ~/ j[color=rgba(0, 0, 0, 0.749019607843137)]46
' ?* v% E1 s+ u) h9 ?" ][color=rgba(0, 0, 0, 0.749019607843137)]47. m1 h6 K0 R" e% l& W Z% [' R
[color=rgba(0, 0, 0, 0.749019607843137)]48
" R0 K- C; _3 S) q$ M W0 _[color=rgba(0, 0, 0, 0.749019607843137)]49, W. w9 O/ l' ?$ i) E
[color=rgba(0, 0, 0, 0.749019607843137)]50
* b8 l: F' g# G z3 T" g( C+ w/ y[color=rgba(0, 0, 0, 0.749019607843137)]51
% I2 ^! v& K; v: S2 q) C |/ B[color=rgba(0, 0, 0, 0.749019607843137)]52
0 O4 |/ R9 ^# |( m) [/ c[color=rgba(0, 0, 0, 0.749019607843137)]53
$ p" z# _' x* x/ ~0 b' ?9 }[color=rgba(0, 0, 0, 0.749019607843137)]54
, i8 A& ~1 n3 D' V% N! l[color=rgba(0, 0, 0, 0.749019607843137)]555 K# a% O: Y* ~$ k) Y
[color=rgba(0, 0, 0, 0.749019607843137)]56
% \, x/ [. I W f) ?; N[color=rgba(0, 0, 0, 0.749019607843137)]57/ D! g- }3 n* V; N& F* Z
[color=rgba(0, 0, 0, 0.749019607843137)]583 M. \& F& r" y4 p4 r
[color=rgba(0, 0, 0, 0.749019607843137)]59$ O7 S- h e. Y8 e3 Z+ O+ Z" a6 G/ s
[color=rgba(0, 0, 0, 0.749019607843137)]60% T$ t( t- V0 C1 w. c8 ~# \7 d& b% z
[color=rgba(0, 0, 0, 0.749019607843137)]614 P8 p: F! E# M1 f2 c
[color=rgba(0, 0, 0, 0.749019607843137)]62
+ m. z* t8 w6 H, n( m. \[color=rgba(0, 0, 0, 0.749019607843137)]63
, B) e* S: G# I, \7 V[color=rgba(0, 0, 0, 0.749019607843137)]642 k- n8 Z& s' o; h0 V
[color=rgba(0, 0, 0, 0.749019607843137)]65/ H* n' n% t/ m2 [+ |( Y, y
[color=rgba(0, 0, 0, 0.749019607843137)]66
2 E7 r1 F$ ^# J# [[color=rgba(0, 0, 0, 0.749019607843137)]67
# d3 U& L; V e- m" C6 i4 Y[color=rgba(0, 0, 0, 0.749019607843137)]68
3 T! n% A4 g; n( j# `: m[color=rgba(0, 0, 0, 0.749019607843137)]697 \9 r4 `& d! f) t U( p, @+ T
[color=rgba(0, 0, 0, 0.749019607843137)]70
& E: y4 R$ i: p; u- `, w4 t[color=rgba(0, 0, 0, 0.749019607843137)]712 b: ]4 p, V0 A# `
[color=rgba(0, 0, 0, 0.749019607843137)]72
" k& u. K/ o) g2 i[color=rgba(0, 0, 0, 0.749019607843137)]73
5 r- c0 s& A' n. X4 B[color=rgba(0, 0, 0, 0.749019607843137)]74
! s2 n0 E, f7 y" }; H5 j) x[color=rgba(0, 0, 0, 0.749019607843137)]75- b1 e' @0 [! U' C
[color=rgba(0, 0, 0, 0.749019607843137)]76
7 U1 @7 `6 T. s% V# \! ^[color=rgba(0, 0, 0, 0.749019607843137)]77/ w T3 e; H) q) H0 g2 V. T
[color=rgba(0, 0, 0, 0.749019607843137)]78( a+ }, \: p1 z& `/ v( u
[color=rgba(0, 0, 0, 0.749019607843137)]790 R" F& e3 [/ L# u& l2 P* e
[color=rgba(0, 0, 0, 0.749019607843137)]80+ f, d. ^! L/ g9 Y' V% E
[color=rgba(0, 0, 0, 0.749019607843137)]814 z7 o& j1 x" w) c; y
[color=rgba(0, 0, 0, 0.749019607843137)]82
5 K9 @& d, J: C/ t8 C2 I[color=rgba(0, 0, 0, 0.749019607843137)]839 f/ v$ Z5 @" ?' u
[color=rgba(0, 0, 0, 0.749019607843137)]84
" o8 {+ d9 G" f" Z* X[color=rgba(0, 0, 0, 0.749019607843137)]85
- C7 C" s- ^- \# a" r: R[color=rgba(0, 0, 0, 0.749019607843137)]86 \6 v" Q9 X0 U: O$ C. c8 }3 u
[color=rgba(0, 0, 0, 0.749019607843137)]87
6 ^: \' k* \6 F! T[color=rgba(0, 0, 0, 0.749019607843137)]884 J7 V! m ^! Q) }
[color=rgba(0, 0, 0, 0.749019607843137)]895 r! t* W& J; A- Q7 N' j+ ?
[color=rgba(0, 0, 0, 0.749019607843137)]900 j* Y! F' e: T# `! F) Z
[color=rgba(0, 0, 0, 0.749019607843137)]91
' c s; |( p+ j) @6 c. ?[color=rgba(0, 0, 0, 0.749019607843137)]92
* F# T6 |) l& D; e[color=rgba(0, 0, 0, 0.749019607843137)]93
Y' T! R! D2 }! A6 ~ v" u[color=rgba(0, 0, 0, 0.749019607843137)]94
0 z& `3 h0 P) N7 Q' S4 O# m[color=rgba(0, 0, 0, 0.749019607843137)]959 q! |5 L5 I5 i4 E5 ?3 q
[color=rgba(0, 0, 0, 0.749019607843137)]96
; v, q: Y& I& _1 h: ?[color=rgba(0, 0, 0, 0.749019607843137)]97# o Q+ E/ U3 p2 c0 i B- C5 X
[color=rgba(0, 0, 0, 0.749019607843137)]98
8 e( ]' b% ]! j[color=rgba(0, 0, 0, 0.749019607843137)]99& F1 [; A" p2 h o+ @8 i' t9 @
[color=rgba(0, 0, 0, 0.749019607843137)]100
/ K, S' l5 v/ Y9 t. z[color=rgba(0, 0, 0, 0.749019607843137)]101$ R; h! c n( ?$ \$ H* m) V& h# ^
[color=rgba(0, 0, 0, 0.749019607843137)]102
& P' |) z( C5 | d2 I3 j' @# u9 C[color=rgba(0, 0, 0, 0.749019607843137)]103. M! k7 N( _9 R& [9 P1 Q
[color=rgba(0, 0, 0, 0.749019607843137)]104
- C6 H" a" y- {. [7 \! S2 t/ K[color=rgba(0, 0, 0, 0.749019607843137)]1057 r- ]+ I9 b( n' T- V5 I7 _
[color=rgba(0, 0, 0, 0.749019607843137)]106
F" Z7 {6 \. c0 I[color=rgba(0, 0, 0, 0.749019607843137)]107
$ `' x2 {; V- I1 J( t0 V6 L( T[color=rgba(0, 0, 0, 0.749019607843137)]108' r; ^6 u6 @1 h& h% N5 q Q- z: H
[color=rgba(0, 0, 0, 0.749019607843137)]109' | t7 l5 f5 L. N+ k
[color=rgba(0, 0, 0, 0.749019607843137)]1108 x& |) }0 Y2 c, g; a% ~# Y D
[color=rgba(0, 0, 0, 0.749019607843137)]1110 _; X0 }& c# |
[color=rgba(0, 0, 0, 0.749019607843137)]测试结果：
. R! k2 a* m% T8 y$ K[color=rgba(0, 0, 0, 0.749019607843137)]
- ?8 w, G/ }2 ]5 v' d" F; F* V P+ b
$ I. v4 z* Z6 I' y7 K[color=rgba(0, 0, 0, 0.749019607843137)]
; G" m7 Q, L9 j \3 v2 C
9 B! F {* w$ {5 g& f% o[color=rgba(0, 0, 0, 0.749019607843137)]2.2计算二叉树的大小
6 ~/ C/ o! V* C[color=rgba(0, 0, 0, 0.749019607843137)]时间复杂度为O(N)7 G7 L( \% I3 M t/ D
[color=rgba(0, 0, 0, 0.749019607843137)]4 D" }' H4 ]1 S9 d) D, ~& `
/ C4 Z% S6 D2 ?& y4 J8 ~
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树的大小
d6 ?8 G$ Z# b6 h[color=rgba(0, 0, 0, 0.749019607843137)]//法一：全局变量
4 h4 l+ ~" i4 w$ q4 C[color=rgba(0, 0, 0, 0.749019607843137)]//int count = 0;
- w/ c6 x; e( L[color=rgba(0, 0, 0, 0.749019607843137)]//void TreeSize(BTNode* root)
1 K, Q6 |+ Y* j& d3 J9 t2 J[color=rgba(0, 0, 0, 0.749019607843137)]//{
1 q, L& |. q# L5 r. u[color=rgba(0, 0, 0, 0.749019607843137)]// if (root == NULL)8 c6 p2 D9 ~ z& c1 |! g- E
[color=rgba(0, 0, 0, 0.749019607843137)]// {% K1 P C2 ~! N
[color=rgba(0, 0, 0, 0.749019607843137)]// return;
. w# I. @. X9 G+ Q9 s- Z[color=rgba(0, 0, 0, 0.749019607843137)]// }4 d3 b% }! \5 f, g+ X5 j# ~3 X
[color=rgba(0, 0, 0, 0.749019607843137)]// count++;8 J( @9 C+ U5 c* h
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->left);4 |% L3 n0 Q" l3 d$ ^
[color=rgba(0, 0, 0, 0.749019607843137)]// TreeSize(root->right);1 b) w% y! V" v7 r5 e' y
[color=rgba(0, 0, 0, 0.749019607843137)]//+ g4 q u6 D9 v& E0 Y
[color=rgba(0, 0, 0, 0.749019607843137)]// return;//函数栈帧层层返回，最后回到根节点1，结束了1的右子树函数，什么都不返回，因为count是全局变量
, v. U) p% V. X( v2 a[color=rgba(0, 0, 0, 0.749019607843137)]//}. V0 S8 L9 Y% a2 L
[color=rgba(0, 0, 0, 0.749019607843137)]//法二：子问题思路：分而治之
; `4 g4 q6 u! p1 k! O[color=rgba(0, 0, 0, 0.749019607843137)]int TreeSize(BTNode* root)7 w3 y3 g z0 V- P
[color=rgba(0, 0, 0, 0.749019607843137)]{; l {0 P0 j/ L
[color=rgba(0, 0, 0, 0.749019607843137)] return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
9 V, D" Q Q- ]3 o: _- e, ?[color=rgba(0, 0, 0, 0.749019607843137)]}
$ [$ K3 [5 u( D[color=rgba(0, 0, 0, 0.749019607843137)]1% B! n7 A' b8 D! t
[color=rgba(0, 0, 0, 0.749019607843137)]22 i/ c. b' }" S( V2 E( C. P- [
[color=rgba(0, 0, 0, 0.749019607843137)]3! T% t d6 g& F* y! g/ S$ K
[color=rgba(0, 0, 0, 0.749019607843137)]4+ X5 A: g5 A6 t! C; j
[color=rgba(0, 0, 0, 0.749019607843137)]5
% a" w6 n$ I6 d; j! s/ f[color=rgba(0, 0, 0, 0.749019607843137)]6& K) w- M l; O9 Z
[color=rgba(0, 0, 0, 0.749019607843137)]7
% J! H3 l5 s+ f4 s5 i8 N8 B[color=rgba(0, 0, 0, 0.749019607843137)]88 ] k9 E4 r1 {9 r( M+ p
[color=rgba(0, 0, 0, 0.749019607843137)]9
0 Y4 f& c" K' t. s/ u" B[color=rgba(0, 0, 0, 0.749019607843137)]107 [& R6 B' r+ Q5 ?! i6 p8 K8 B- y
[color=rgba(0, 0, 0, 0.749019607843137)]11
+ j! G" ~7 v b6 A- Q- v[color=rgba(0, 0, 0, 0.749019607843137)]12
# y" P8 T# d' c" Q5 p[color=rgba(0, 0, 0, 0.749019607843137)]13% J$ Q' k' y3 ]1 M: [3 o2 t
[color=rgba(0, 0, 0, 0.749019607843137)]14
7 i9 g4 r( m5 W, V9 u5 C, p[color=rgba(0, 0, 0, 0.749019607843137)]152 X! G9 i* W# _* s; h, b. [
[color=rgba(0, 0, 0, 0.749019607843137)]16
! F; B( d2 a8 W/ a: R& H1 m l[color=rgba(0, 0, 0, 0.749019607843137)]17/ A; U. t5 R* ~3 ^& w% r9 p
[color=rgba(0, 0, 0, 0.749019607843137)]18
) ]) M1 x2 F7 T; x$ w; \7 G[color=rgba(0, 0, 0, 0.749019607843137)]19
& z% A0 { o+ R[color=rgba(0, 0, 0, 0.749019607843137)]20
3 b( a, H" f1 ~. h[color=rgba(0, 0, 0, 0.749019607843137)]2.3计算二叉树叶子结点的个数- Z5 a9 t0 S( L# \" [4 p% S
[color=rgba(0, 0, 0, 0.749019607843137)]//计算二叉树叶子结点的个数 E$ y, B* N$ l1 q2 `" J/ {
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLeafSize(BTNode* root)
* A3 l* n3 D. [# z# e1 }0 Y[color=rgba(0, 0, 0, 0.749019607843137)]{# S- \2 H& u: E6 W5 G' w. R4 P
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)//首先得考虑空树的情况,0个叶子结点 X) e" R/ a3 e: _( R* V" j+ t4 s
[color=rgba(0, 0, 0, 0.749019607843137)] {
0 [5 ?- ^/ S& I8 a0 o[color=rgba(0, 0, 0, 0.749019607843137)] return 0;$ |3 D$ s; N/ P
[color=rgba(0, 0, 0, 0.749019607843137)] }
6 A& f" M- m6 G' z[color=rgba(0, 0, 0, 0.749019607843137)] //叶子结点的特征就是左右子树为空
, A* A8 u. w: }! l7 o[color=rgba(0, 0, 0, 0.749019607843137)] if (root->left == NULL && root->right == NULL)
" R4 _" L, a5 @- Q5 }% w[color=rgba(0, 0, 0, 0.749019607843137)] {; `3 m9 n) B m; K3 w( u7 l
[color=rgba(0, 0, 0, 0.749019607843137)] return 1;( Y9 x% K' J/ Z& Q
[color=rgba(0, 0, 0, 0.749019607843137)] }1 C( H: A* s6 h: B+ Q a+ Z; j
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLeafSize(root->left) + TreeLeafSize(root->right);
0 {$ i& }; p' O[color=rgba(0, 0, 0, 0.749019607843137)]}" ~; `# c9 [+ k8 U1 D0 t1 D5 [4 n a
[color=rgba(0, 0, 0, 0.749019607843137)]1# \5 Y4 D) v9 g$ O: L
[color=rgba(0, 0, 0, 0.749019607843137)]23 \; `0 C6 |: E( j4 r
[color=rgba(0, 0, 0, 0.749019607843137)]37 b n- Z1 s5 j0 G: [! p0 i% \+ v
[color=rgba(0, 0, 0, 0.749019607843137)]4) z- C C; k3 {7 H3 \. L4 V5 D
[color=rgba(0, 0, 0, 0.749019607843137)]5
& s N( u+ @# U* ?0 r5 R[color=rgba(0, 0, 0, 0.749019607843137)]6, b' [, Y; ^ T% a% T. V& b
[color=rgba(0, 0, 0, 0.749019607843137)]7; [- O9 N* {+ Q6 R4 {6 K6 _. }
[color=rgba(0, 0, 0, 0.749019607843137)]8) x$ y6 o1 l* I
[color=rgba(0, 0, 0, 0.749019607843137)]9
8 _% e4 t; ^' g. G: P. I[color=rgba(0, 0, 0, 0.749019607843137)]10
]9 `! P3 A: c* J6 G+ a[color=rgba(0, 0, 0, 0.749019607843137)]118 H* s4 d+ O# ^# M# }4 H; n
[color=rgba(0, 0, 0, 0.749019607843137)]12
8 ~4 `; V( F8 k0 `9 t4 N4 G: m[color=rgba(0, 0, 0, 0.749019607843137)]13
: {3 g2 _$ p2 V- L8 O) S' c+ O: s[color=rgba(0, 0, 0, 0.749019607843137)]14
) {! w' U9 e l/ ]$ g' n6 x- o- `[color=rgba(0, 0, 0, 0.749019607843137)]2.4计算二叉树的高度; o7 ]3 q$ z( o; `/ @
[color=rgba(0, 0, 0, 0.749019607843137)]int TreeHeight(BTNode* root)
+ l1 p2 T% m5 X- l6 O/ t2 _[color=rgba(0, 0, 0, 0.749019607843137)]{2 J5 L0 R. c6 d
[color=rgba(0, 0, 0, 0.749019607843137)] //空树高度为0, p6 }, A O2 B: s
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)- y5 F! _9 A) o7 a2 }. R
[color=rgba(0, 0, 0, 0.749019607843137)] {+ M7 A, q' \+ H" V/ p8 g2 i
[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
$ K+ C: ^. l% T[color=rgba(0, 0, 0, 0.749019607843137)] }/ I- M2 f! a0 |
[color=rgba(0, 0, 0, 0.749019607843137)] //树的高度是较高的那棵子树! A& s* |/ D0 L0 T1 ?
[color=rgba(0, 0, 0, 0.749019607843137)] int lh = TreeHeight(root->left);//左子树的高度
0 { `6 q: v! a! _% q" m[color=rgba(0, 0, 0, 0.749019607843137)] int rh = TreeHeight(root->right);//右子树的高度1 ]! N9 ~ T/ h9 Q" j
[color=rgba(0, 0, 0, 0.749019607843137)]4 l" C6 w. `# T3 ]! x6 A
) r3 s- h9 j9 D* j4 }0 n
[color=rgba(0, 0, 0, 0.749019607843137)] return lh > rh ? lh + 1 : rh + 1;" X. w% ?: |) N# `
[color=rgba(0, 0, 0, 0.749019607843137)]}
8 ?: Z( V; B( n4 L[color=rgba(0, 0, 0, 0.749019607843137)]10 I. G5 i5 e3 h
[color=rgba(0, 0, 0, 0.749019607843137)]2
+ I$ C* ?9 A' }: I, }! a+ H4 X[color=rgba(0, 0, 0, 0.749019607843137)]3
3 @& w: _/ ^2 f3 O9 S1 R( p, Y[color=rgba(0, 0, 0, 0.749019607843137)]42 [4 N/ k+ Z) @
[color=rgba(0, 0, 0, 0.749019607843137)]5) Y" w$ i% u5 o
[color=rgba(0, 0, 0, 0.749019607843137)]6! ] ~! y5 Q3 G# F8 I6 x+ J
[color=rgba(0, 0, 0, 0.749019607843137)]7
: m' C* X4 ?' u# D, V0 V% J[color=rgba(0, 0, 0, 0.749019607843137)]8
# v( X. O! ~% w) G$ p i[color=rgba(0, 0, 0, 0.749019607843137)]90 A/ `8 q, H8 s( ^) S! z% H/ H/ z
[color=rgba(0, 0, 0, 0.749019607843137)]10
) n/ d4 _7 m; D3 c/ o7 h- f* l% Z[color=rgba(0, 0, 0, 0.749019607843137)]11+ P, G! i5 x2 W( W" F( [' V
[color=rgba(0, 0, 0, 0.749019607843137)]122 V/ q! b4 C2 o' {# u
[color=rgba(0, 0, 0, 0.749019607843137)]13
1 ]/ k' @6 F/ t1 X[color=rgba(0, 0, 0, 0.749019607843137)]2.5计算第K层结点的个数
7 j7 {% r1 s' \9 R& e% P u[color=rgba(0, 0, 0, 0.749019607843137)]
& A" U- h$ p6 g; m; h! f) `
- L* X" i( W! ~[color=rgba(0, 0, 0, 0.749019607843137)]
3 s# y/ O4 Q- e8 I7 Q, ^( e0 m% I6 w& O j8 B; x3 J* `
[color=rgba(0, 0, 0, 0.749019607843137)]求第K层的结点个数，转换成求子树第K-1层的结点个数。举个栗子：如果我们要求这棵二叉树第3层的结点个数（为3），就转换成求左子树根结点2的第2层的结点个数+右子树4第二层的结点个数。。。
( D" u4 M) P( v N) F {- e[color=rgba(0, 0, 0, 0.749019607843137)]) y9 g9 S% ^1 U! W
# O3 o, ~! r5 O' \# T9 a7 W
[color=rgba(0, 0, 0, 0.749019607843137)]//计算第K层结点的个数
: S; k% ~- x" }% A7 c$ d[color=rgba(0, 0, 0, 0.749019607843137)]int TreeLevel(BTNode* root,int K)5 F- ~) A$ G' \2 M+ w: v+ G) o
[color=rgba(0, 0, 0, 0.749019607843137)]{
' T8 T) A$ i+ c4 S( g[color=rgba(0, 0, 0, 0.749019607843137)] assert(K > 0);
& P4 E k) E6 Q; i8 a6 w- X[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)& A0 x6 H5 H3 w; C/ o1 t: X
[color=rgba(0, 0, 0, 0.749019607843137)] {
0 w6 E3 b: T2 ?9 y: D[color=rgba(0, 0, 0, 0.749019607843137)] return 0;
4 t7 q1 m/ h; w) e7 L[color=rgba(0, 0, 0, 0.749019607843137)] }* V' ~, z$ ] Q, m4 I
[color=rgba(0, 0, 0, 0.749019607843137)] //如果是第一层(递归出口)
7 s6 Q: B1 _3 b- J; J[color=rgba(0, 0, 0, 0.749019607843137)] if (K == 1)
- C ~* [3 O6 L( a* a5 p6 l[color=rgba(0, 0, 0, 0.749019607843137)] {
$ p: U6 y7 w7 S[color=rgba(0, 0, 0, 0.749019607843137)] return 1;- q. z, \4 T/ L9 P
[color=rgba(0, 0, 0, 0.749019607843137)] }& ]" K3 Z7 I% i- h; V( m! F$ u
[color=rgba(0, 0, 0, 0.749019607843137)] //转换成子树的第K-1层9 d- P" A7 y1 b: A) H1 A
[color=rgba(0, 0, 0, 0.749019607843137)] return TreeLevel(root->left,K-1) + TreeLevel(root->right,K-1);
1 Y7 {* g$ B1 ]8 |1 q3 O! d6 b[color=rgba(0, 0, 0, 0.749019607843137)]}
6 }- c, J' A0 J& r- n: N2 y- D[color=rgba(0, 0, 0, 0.749019607843137)]1, |4 }( A/ c0 l5 l5 b8 n7 j9 w
[color=rgba(0, 0, 0, 0.749019607843137)]27 q7 s4 B4 f$ Z4 B
[color=rgba(0, 0, 0, 0.749019607843137)]3, `3 l* }2 {5 M+ ?
[color=rgba(0, 0, 0, 0.749019607843137)]4
% O2 O9 a4 G& h) T& f0 z, X[color=rgba(0, 0, 0, 0.749019607843137)]58 o% X- r1 r, M: Y" S! T# {
[color=rgba(0, 0, 0, 0.749019607843137)]6
" D4 v, P/ i! ]3 `( ~2 S! j' E F[color=rgba(0, 0, 0, 0.749019607843137)]7
: x4 m/ h. Y# E) Z+ g) w* r; P9 B[color=rgba(0, 0, 0, 0.749019607843137)]8' e6 J3 A% Y8 `" x7 D9 f
[color=rgba(0, 0, 0, 0.749019607843137)]9! W" I# l9 F7 x& ~; F2 c: h; Z
[color=rgba(0, 0, 0, 0.749019607843137)]10
9 X+ V$ D8 z% S6 T6 {- d* u6 e+ e[color=rgba(0, 0, 0, 0.749019607843137)]116 g' {% q I( U- q( p% {% r3 N
[color=rgba(0, 0, 0, 0.749019607843137)]12
2 Y" ~- ]; @: X[color=rgba(0, 0, 0, 0.749019607843137)]13& @5 ?; N7 @! U- p' p' p
[color=rgba(0, 0, 0, 0.749019607843137)]14+ l! C0 S, \- d, d
[color=rgba(0, 0, 0, 0.749019607843137)]15
" ]. x9 z) r# Y. v3 w3 ?# Q[color=rgba(0, 0, 0, 0.749019607843137)]16
. k1 Z, a+ r8 q3 `, O' T. a[color=rgba(0, 0, 0, 0.749019607843137)]2.6二叉树查找& n/ M" z7 W) M( r1 H8 p. z
[color=rgba(0, 0, 0, 0.749019607843137)]//二叉树查找
0 {: j# y6 ~6 g4 m% H, m[color=rgba(0, 0, 0, 0.749019607843137)]BTNode* TreeFind(BTNode* root, BTDataType data)
- L5 ^6 y4 S( N2 @9 v[color=rgba(0, 0, 0, 0.749019607843137)]{5 n v# S. V ]6 w! k
[color=rgba(0, 0, 0, 0.749019607843137)] if (root == NULL)
9 D2 e `/ Z% m6 g: n/ C[color=rgba(0, 0, 0, 0.749019607843137)] {
! q3 t+ J2 y$ w3 d" L[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;) D! M( Y7 Y+ h" W; T
[color=rgba(0, 0, 0, 0.749019607843137)] }
E0 X) G. V& L0 v F[color=rgba(0, 0, 0, 0.749019607843137)] if (root->data == data)9 v" Y% B/ E+ t
[color=rgba(0, 0, 0, 0.749019607843137)] {; `4 r% g' u* r8 D9 f3 d' e5 q
[color=rgba(0, 0, 0, 0.749019607843137)] return root;" S8 _4 |5 |. _1 v+ Y/ W
[color=rgba(0, 0, 0, 0.749019607843137)] }4 m- d) }$ S S/ ^5 J3 `/ r- T5 W
[color=rgba(0, 0, 0, 0.749019607843137)] //先查找左子树
, K4 X4 _1 Q1 g$ Q. [[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* lret = TreeFind(root->left, data);3 ~* j! `9 m/ G/ E- f) i) y( v
[color=rgba(0, 0, 0, 0.749019607843137)] if (lret)
3 \" G! `; F0 C Z* D$ e[color=rgba(0, 0, 0, 0.749019607843137)] return lret;$ f# W+ ?) D. e
[color=rgba(0, 0, 0, 0.749019607843137)] //再查找右子树* y* H6 k; i( k# Z; ~
[color=rgba(0, 0, 0, 0.749019607843137)] BTNode* rret = TreeFind(root->right, data);" g3 l0 {( E, k" z4 ?
[color=rgba(0, 0, 0, 0.749019607843137)] if (rret)
* A: c! \4 k5 x3 ~$ `[color=rgba(0, 0, 0, 0.749019607843137)] return rret;
" e% U( r; r4 ~/ {# ^6 l7 h" `[color=rgba(0, 0, 0, 0.749019607843137)] return NULL;9 e2 |2 _) ?/ Z* \9 } _
[color=rgba(0, 0, 0, 0.749019607843137)]}
4 V$ h4 T+ `, s" j' @' w$ Z[color=rgba(0, 0, 0, 0.749019607843137)]————————————————
9 s& o/ k. {2 q: ]$ G* H e5 M {[color=rgba(0, 0, 0, 0.749019607843137)]版权声明：本文为CSDN博主「SouLinya」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
" f/ _% q% Y( Q& z4 {& ~: ^- U7 x[color=rgba(0, 0, 0, 0.749019607843137)]原文链接：https://blog.csdn.net/weixin_63449996/article/details/1268412125 \4 ?! p& ` x9 Z4 m
# s1 o0 k) W" x E* H" ~# O5 U% E! l
[color=rgba(0, 0, 0, 0.75)]/ S/ v( I& Z' a6 \
+ b4 P7 h. ]( Z, M
9 C5 k9 ? j. n; g" b
6 C& a5 ?" W* E, C# \4 z |
IP卡
狗仔卡
发表于 2022-9-15 11:55
转播
淘帖
分享
收藏
支持
反对
微信
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
抢沙发
显身卡
