求树的节点个数求法，求助啊！！！

qiandongdong

求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~

madio

就是一个遍历树的所有节点的算法，我帮你找到一个

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：0 c1 x, N$ B. r2 P
   
2.        tree_nodename：节点名字或序号# \: b, _5 e( X$ ~
   
3.        tree_nodevalue：节点对应的值
   ( L$ {* x2 y# Z+ ?
4.        tree_nodefather：节点父亲，如果没有父亲，值为空2 @: g. B  E4 }! Y  O$ u3 s# @
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   ) X8 I- }+ l: m! o
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空3 Y4 Z- }& a+ M) X' R: r) `- K
   
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   ( R\" H: L. \, c- Y! u) C1 {\" g+ k
8. 
   * S( ^$ V, a9 y9 H\" C. ^
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   + L; y) w& }# l! K8 a
10. ! t. h\" \: @& ^) x. G# ]' J2 S
    
11.        %matlab源程序# X0 ^5 F/ L$ T9 U2 y. C. `
    
12.        %输入：树的深度、树的广度、搜索的值/ i  L- t% K3 N  i6 A* G
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    6 r# k+ P( S3 o5 p  I6 ^. v8 x
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    \" i5 U2 s3 X. N, W& v
15.        %根据树的深度、节点的儿子数量计算树总的节点个数\" i6 F6 S\" B! ?
    
16.        node_num = 0;7 g1 ?3 z* d* {* y! n* Z
    
17.        for n= 0 : (tree_depth-1)
    % g2 k8 V# E* d* E/ e\" a8 `
18.               node_num = node_num + tree_width ^ n;
    ) l) x9 k5 ]* A7 m( u
19.        end
    8 Y  p1 w9 Q  S$ x& C* ^
20. 9 Z2 k$ Y* ~: s- \/ J! m: X\" N
    
21.        %为树的存储空间赋值9 a% N1 Z  A* I, e$ a6 i' {
    
22.        %node name，按照广度优先为节点排号) G4 j# z1 E( p6 M
    
23.        tree_nodename = (1 : node_num);; q9 R* L, n7 D7 X  N
    
24.        %node value
    , [- ^  o2 {% t3 f4 i, w
25.        tree_nodevalue = rand(1 : node_num);: x\" l2 u- R5 K) I% A0 m
    
26.        %node father and son$ A4 t5 L( V$ J, ^
    
27.        tree_nodefather(1) = 0;
    ' B& T0 f: n7 _( S* ]+ U! v* g- K0 J
28.        tree_nodeson = zeros(1, node_num);* C  `( b4 P8 ^0 P4 N$ M\" y6 @
    
29.        n = 2;( ^9 ~0 a& o: O: _0 d/ k/ I4 a
    
30.        k = 1;; n\" \* n( `( c2 Q& G
    
31.        while n <= node_num/ m. e& O. `% h0 j; r8 c
    
32.               for m = 1 : tree_width
    ! W8 ?) d6 |$ V$ a9 ]+ y: i\" Z
33.                      tree_nodefather(n) = k;
    3 Z* c5 g: N0 S, h
34.                      if m==1
    4 ^2 n% i& b; t$ f. H. m1 x, @( X
35.                             tree_nodeson(k) = n;* h& ]6 B. i  T: Y' l( v% E
    
36.                      end. M  `- [. \, W1 j. x+ o
    
37.                      n = n + 1;- @7 z/ O4 W- i% P\" [' B
    
38.               end
    7 s, S\" F\" }$ }6 F& c
39.               k = k + 1;
    , m4 {2 f6 T  G3 Z4 F
40.        end& p' Y3 [( B. Y8 E. e
    
41.        %node neighbor
    - M3 v3 h\" \1 U( G/ Z7 V' \& W
42.        tree_nodeneighbor(1) = 0;
    - u3 r' @% g2 x. J7 M4 H$ U; A
43.        n = 2;  j) d. [* I; P5 I3 F, `
    
44.        while n <= node_num1 {% B8 q\" r# X9 R2 C0 [
    
45.               for m = 1 : tree_width
    9 _8 ~2 J* T3 c  }  s
46.                      if m ==tree_width
    / c% O1 r) ]) v+ W. C, Y
47.                             tree_nodeneighbor(n) = 0;- k/ i# a\" h! e
    
48.                      else
    ; w; v+ S* X% ]2 R* n4 S
49.                             tree_nodeneighbor(n) = n + 1;0 c% [7 I+ W) m+ a: G
    
50.                      end
    1 D; G. k4 ^1 w! }7 \
51.                      n = n + 1;# p\" X' j9 m) d( U1 T7 ]: ?3 O  n
    
52.               end
    : Q& m\" ?. i. h1 |# ~5 u7 n, z) Y
53.        end2 X6 j- H- u* }3 Q1 |: o8 P- S
    
54. 
    3 g# e& B# O% T% q! J# [: X
55.        %下面是有效程序段，用栈实现
    . e0 k9 P$ \) g4 V; i
56.        stack = zeros(1, tree_depth);
    & Y0 L( ^4 T* v, |7 U
57.        nodeinstack = zeros(1, node_num);4 W/ d7 Q6 F, R9 A1 _
    
58.        stack_ptr = 1;! X, x$ M& t! o4 o+ l) p
    
59.        stack(1) = 1;
    0 @) `( A; t0 i* k( b: _0 s: ~& V
60.        nodeinstack(1) = 1;# Q- Z6 e5 F2 @, e6 L% h
    
61.        valueintree = seek_value;
    4 l\" l: D5 p. v: Q3 H# ?
62.        nodeintree = 0;' t! |/ n2 o! b0 S+ S; D
    
63. , V; q2 O6 v# V+ M5 ]6 Y
    
64.        while stack_ptr > 0# m, U2 w% q7 X( ], |: `) Z
    
65.               n = stack(stack_ptr);$ Q5 o! ^- J. |. Y* X\" a
    
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-30 x; P7 }* P0 G, `! U& |( I
    
67.               %如果搜索到值，返回. L4 N% s7 N! ~* L
    
68.                      valueintree = tree_nodevalue(n);
    9 ~* U# J7 f\" c% Y6 X' c. }$ T
69.                      nodeintree = tree_nodename(n);' @, Q6 Y, L8 J$ K$ U% w( u; K
    
70.                      break;: z3 f8 Z0 O) E\" E) [3 z# b4 R
    
71.               end# N1 N$ |$ ~8 P3 H5 K% i
    
72. 
    0 q, T3 \. ^3 N2 R0 O
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    - w) _5 L; z/ e
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    / B) U. V- E. E# g. [7 i7 M
75.                      stack_ptr = stack_ptr + 1;8 \# m+ b# s: u+ c, E: H
    
76.                      m = tree_nodeson(n);+ a8 d; C$ Z1 U& e9 a, U
    
77.                      stack(stack_ptr) = m;
    1 B: P9 T( Y\" O- v& |; ?# N, o8 t
78.                      nodeinstack(m) = nodeinstack(m) + 1;% M5 X2 Z\" g3 _# U' A8 ~9 l
    
79.               elseif tree_nodeneighbor(n) ~= 0
    , h# |. H- q3 q# z. u* d
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈2 p0 u' F* i2 ?# r
    
81.                      m = tree_nodeneighbor(n);' t\" N3 k% B8 }2 u4 i; {& i) Z
    
82.                      stack(stack_ptr) = m;' i6 H. B& h3 k
    
83.                      nodeinstack(m) = nodeinstack(m) + 1;+ `/ R' y/ R3 h& Z6 z0 A
    
84.               else! n5 f7 }7 i0 d. ?4 l8 T( \. k
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一. f2 ~\" G! j( B1 Z
    
86.                      stack_ptr = stack_ptr - 1;
    6 Z1 h& g/ c\" `, o+ F
87.                      m = stack(stack_ptr);\" V6 m+ ^1 P; }) \
    
88.                      nodeinstack(m) = nodeinstack(m) + 1;+ z7 C2 T2 c8 ]
    
89.               end
    , G0 i5 L! a7 v/ Q  ]
90.        end

复制代码