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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：+ O! V, Y/ k2 O\" S: Z
   
2.        tree_nodename：节点名字或序号$ r1 _3 V3 t6 U; ]
   
3.        tree_nodevalue：节点对应的值5 @; \% b1 N8 B* u/ N( z! y
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空
   $ l/ k% b0 {: {8 b+ U5 J1 p
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空- m& c# N# v# g1 v9 s6 e
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   3 t  d/ ?( D! b4 \  R: c% e) q  O; u
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   3 ~7 Z( S' @' E) w
8. 
   9 L4 @3 G2 M- @4 D# B
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   ' j1 K( w( r7 E\" o: o
10. ' W6 j! \; V( N$ T$ C0 J
    
11.        %matlab源程序
    8 R' i; u3 O3 j( Y. @
12.        %输入：树的深度、树的广度、搜索的值  R; _7 t+ _* i( m
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空( s& _4 B; d5 U- h  h
    
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    * K' C, v) r  \2 T3 p
15.        %根据树的深度、节点的儿子数量计算树总的节点个数. [- H; D5 V\" h0 h
    
16.        node_num = 0;
    7 e\" F! n/ X/ R9 N; R
17.        for n= 0 : (tree_depth-1)
    - h1 e0 N0 s$ J4 _6 n. ?  i. S% c
18.               node_num = node_num + tree_width ^ n;; m1 S* j- K* d0 a9 ^  h
    
19.        end
    2 G; w5 d2 b) ]) l3 o
20. * C5 n8 t8 c9 [6 |/ L& r
    
21.        %为树的存储空间赋值0 H, w  f6 Y9 K' R\" d! a
    
22.        %node name，按照广度优先为节点排号7 J6 N$ R# ~$ H3 H9 o
    
23.        tree_nodename = (1 : node_num);
    % {1 y+ |9 f4 Q- R' k
24.        %node value6 X\" X\" A6 q, q# i; m
    
25.        tree_nodevalue = rand(1 : node_num);( n\" X6 z4 U1 l# Q7 ?/ q
    
26.        %node father and son
    / H! k, `- ~. _9 L
27.        tree_nodefather(1) = 0;
    ( Q& ^7 q/ h\" j( N3 N8 q
28.        tree_nodeson = zeros(1, node_num);* C0 y' i4 O& p9 b
    
29.        n = 2;
    + H\" U' ?. b7 N, I\" G/ g
30.        k = 1;! |: U- x0 V9 @3 S- N
    
31.        while n <= node_num
    ( ^! q) M3 A  j* q: A. [( H5 f- J* f; m
32.               for m = 1 : tree_width
    # ]9 S# W( `+ _* m3 G* w! s. w, N# [
33.                      tree_nodefather(n) = k;4 T. Q3 h! ?+ [& t- }\" ~
    
34.                      if m==1
    0 F* ], y& M* W- g
35.                             tree_nodeson(k) = n;
    ! W% ?6 B/ R+ p' x8 C
36.                      end+ [6 @$ p! X1 o\" ]6 c! g
    
37.                      n = n + 1;
    5 L5 t% G% z7 l
38.               end3 t- v\" {3 d+ G: m1 d* s1 x, Q
    
39.               k = k + 1;/ k! A/ H7 f' P- j* X\" I
    
40.        end
    0 B0 U0 y# I6 z3 j3 T1 X; i
41.        %node neighbor0 N$ V8 J/ S% L1 x3 W
    
42.        tree_nodeneighbor(1) = 0;
    6 A5 B$ }+ t6 ~/ ~0 g, `& P
43.        n = 2;9 I1 i& X- a\" j' R$ \& ?5 p
    
44.        while n <= node_num
    7 }5 \/ ~) R( H& \
45.               for m = 1 : tree_width' L8 M  z+ e: b  V
    
46.                      if m ==tree_width8 {1 t1 x0 i. q& y' {  N
    
47.                             tree_nodeneighbor(n) = 0;$ b0 E/ Z5 k% S7 t
    
48.                      else; E8 j. Y& W7 F* |& E7 |- q
    
49.                             tree_nodeneighbor(n) = n + 1;' R! A/ t. l+ d: P+ x7 o2 a- L
    
50.                      end
    ( s  j, |. \9 _0 R) k
51.                      n = n + 1;1 }1 U6 `! I0 u2 _, n9 ?8 o
    
52.               end
    8 ?; N4 R  q  p1 ^# r9 m\" `6 w& Z1 g
53.        end
    $ p. y- d, y/ g6 d
54. + t5 Q- p, `+ ]4 ?
    
55.        %下面是有效程序段，用栈实现- Z8 K7 o9 H\" S; X& C0 W) F$ g\" Y2 f5 l- t
    
56.        stack = zeros(1, tree_depth);& g% |0 c6 O( D2 R8 S! V, K' S# U
    
57.        nodeinstack = zeros(1, node_num);. i( W* s! W6 e9 `. \
    
58.        stack_ptr = 1;8 U) D3 j! n0 b6 g
    
59.        stack(1) = 1;: s- K0 V& A: |* n) [
    
60.        nodeinstack(1) = 1;
    0 J/ k! q. w) E& ?: ^: x( ^
61.        valueintree = seek_value;4 ~) A$ l( x8 f/ H; f4 u, f; N
    
62.        nodeintree = 0;
    4 S- m( Y; [8 @& k+ x\" ~% n+ ~& Y
63. . z/ V: ?; u& V5 _+ X  c
    
64.        while stack_ptr > 0
    3 {( t# R- X( q* \
65.               n = stack(stack_ptr);
    0 q* v) h7 q# O9 L- Q
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3  B( d+ g! H0 P) ?
    
67.               %如果搜索到值，返回
    3 [0 g\" i6 {: Y+ Q: x
68.                      valueintree = tree_nodevalue(n);4 \' r( B: p8 L& O
    
69.                      nodeintree = tree_nodename(n);
    6 P2 ?# S+ W, _5 g2 G. Z- Y- d! ]2 _
70.                      break;
    : d* H9 r( t/ ]
71.               end
    0 b. b8 D; `$ c9 O& `. P
72. 
    0 O: I9 I8 i; ~. d0 J1 j/ B/ F
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    : L$ E5 h4 ^' _
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈7 W' K+ f$ A- K, i* g; B1 k
    
75.                      stack_ptr = stack_ptr + 1;
    0 }& X% L6 J& C4 H
76.                      m = tree_nodeson(n);
    0 U* g7 Q8 D5 H) B1 g! D
77.                      stack(stack_ptr) = m;
    1 z( ~* N; K& L6 t' \' ~) G& i7 C
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    , u5 u: {) m4 R0 P# G' U
79.               elseif tree_nodeneighbor(n) ~= 06 R$ g* ^/ W: @3 C
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈. A; ^( r: T3 ^
    
81.                      m = tree_nodeneighbor(n);
    $ z0 H- W- b. k
82.                      stack(stack_ptr) = m;
    4 p: n! D) _# l- {8 H& J( Y\" K/ L
83.                      nodeinstack(m) = nodeinstack(m) + 1;$ Z; P4 M- ^) @- Y
    
84.               else
    / L0 @1 y# K9 a
85.               %再否则，出栈，然后将父亲节点的入栈次数加一7 ~5 E\" [; N3 m/ M. ?\" Y
    
86.                      stack_ptr = stack_ptr - 1;* _( ?0 h& V# x8 q, \$ k2 w3 s  M# \
    
87.                      m = stack(stack_ptr);
    ) e, }; K4 d$ @5 A\" H
88.                      nodeinstack(m) = nodeinstack(m) + 1;, f& ^  L  z8 \2 Y: |
    
89.               end9 a8 g7 K/ f. @7 a$ j\" F
    
90.        end

复制代码