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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：
   : e, B! c5 B! f  v& u3 J- T0 K+ j
2.        tree_nodename：节点名字或序号
   2 k+ V* a) w5 r* W
3.        tree_nodevalue：节点对应的值  Z; t2 \, w$ X6 f' a\" e5 j
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空+ U% f! ]  U* f& E& i4 d+ }
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空\" M' W( X, N3 K3 w( Z9 V/ d/ g/ b
   
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   \" f  d+ A' _! R7 Z! t
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。' b7 [1 L2 C5 ?) ^& _, N
   
8. 
   6 L' m# t\" }( v& J
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。% D# s0 C7 J9 o! o* M) l9 {
   
10. 
    ( a1 Z$ Z1 a2 S6 o\" i( h5 _
11.        %matlab源程序
    4 B& _4 w\" ]& b9 j
12.        %输入：树的深度、树的广度、搜索的值6 q9 a# n! |/ r- {
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    / j; v2 P\" R2 O5 L; F( U; _
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    - h* B$ |9 W3 n* r9 A4 f* E7 }
15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    3 i9 Z6 y\" w5 ~; J
16.        node_num = 0;0 ~\" M# ~+ a: f1 C! N) D
    
17.        for n= 0 : (tree_depth-1)0 K5 u$ N3 i7 G- V' U
    
18.               node_num = node_num + tree_width ^ n;
    . _/ @6 T\" V' L7 P% c, k  i* x
19.        end7 V$ r* r5 ~1 y% a; a0 n' r
    
20. 4 E' i( [. O; Z$ N5 }2 \( j
    
21.        %为树的存储空间赋值
    3 }6 O0 ^, l. s& y- L& K
22.        %node name，按照广度优先为节点排号6 x! }8 n+ H, U) u4 F$ ~( }! W
    
23.        tree_nodename = (1 : node_num);
    # V! `' H5 {- n6 `, H3 S
24.        %node value\" V; |2 H6 L. ]9 a/ I
    
25.        tree_nodevalue = rand(1 : node_num);) i/ y; c, ^4 o
    
26.        %node father and son; ^( y8 L: H\" Y\" ?0 A8 \
    
27.        tree_nodefather(1) = 0;
      }, q0 B& r% R9 O$ j0 {
28.        tree_nodeson = zeros(1, node_num);% H- Q\" y5 k8 q, g  ~5 p4 |# L1 T' V
    
29.        n = 2;' |( @9 |2 G) Z/ V& H- f/ M6 W
    
30.        k = 1;
    , [* D7 _5 y& n+ V  D! @6 u
31.        while n <= node_num
    + j1 y9 ?) W5 X( z
32.               for m = 1 : tree_width
    7 y& l) ^6 l2 d% A+ W
33.                      tree_nodefather(n) = k;. O( A2 T) i* x$ B- F: M4 A) m
    
34.                      if m==13 j) {# b) o1 ~6 {' ^
    
35.                             tree_nodeson(k) = n;0 u0 ~2 K- ]) i' X5 A$ b8 Z! i9 i- f
    
36.                      end
    8 e0 U5 ~& ]4 B
37.                      n = n + 1;/ n4 I* `! N& b' T2 U/ a
    
38.               end4 S3 {+ l! r! a% l- h0 W
    
39.               k = k + 1;
    ( Q# s5 ~- B, i% v. Y& Q
40.        end, R, a6 ?1 q; F2 [, e3 Z: @
    
41.        %node neighbor
    3 _: X- N' w5 c  c# H. o$ D! _
42.        tree_nodeneighbor(1) = 0;+ e6 j- w, G\" F. h4 M5 X$ l& n
    
43.        n = 2;
    : |7 s! Q. n! R! @/ s' o% B' Z  t\" C
44.        while n <= node_num
    , R, T# M: q, m1 q6 y
45.               for m = 1 : tree_width
    2 U# G( T4 r1 [& A: h
46.                      if m ==tree_width+ `; i( J4 |* ]
    
47.                             tree_nodeneighbor(n) = 0;
    ) d: c: m& S; c( C7 U% k
48.                      else. s/ O4 V  g' O
    
49.                             tree_nodeneighbor(n) = n + 1;0 B& u) v\" C) t, W+ J1 m
    
50.                      end
    ! Y\" o5 T\" T! a/ c
51.                      n = n + 1;' J& f  n: J, B- H$ U% p
    
52.               end( k  N9 X* [( H+ G3 ^5 r# \
    
53.        end
    ! @1 I5 }$ j. L: \; `/ v
54. 0 Z; c8 e- F( ?2 _  w
    
55.        %下面是有效程序段，用栈实现
    2 z, \- C& D/ s) Y
56.        stack = zeros(1, tree_depth);
    6 ~! G1 J3 {+ Z3 K
57.        nodeinstack = zeros(1, node_num);
    , Q; y) m  U* z, {0 S3 A
58.        stack_ptr = 1;: S* y$ Q' [  z6 C3 z) W' C9 z* x
    
59.        stack(1) = 1;
    0 m6 |& |5 |' g; m) F
60.        nodeinstack(1) = 1;: A2 x. w5 `3 F0 ~0 j$ G
    
61.        valueintree = seek_value;$ e3 R' U8 u: C# f
    
62.        nodeintree = 0;& @/ F, b2 K8 t: }6 a
    
63. 
    - w1 ^' S4 t. t4 o
64.        while stack_ptr > 0& l. c( n! {) A: ~6 v* K0 R
    
65.               n = stack(stack_ptr);
    4 c/ ]* u. h9 ~# {+ g$ e
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-36 x* l' g3 r' K( L: k
    
67.               %如果搜索到值，返回# N2 Y. Y% V+ r3 [& A  E7 f9 h\" Y
    
68.                      valueintree = tree_nodevalue(n);, y* G* }. E: E+ F( N
    
69.                      nodeintree = tree_nodename(n);) I7 U# k- Z& d% Z9 {7 ]7 W
    
70.                      break;
    ' R% R7 h  ^! @' b
71.               end8 |; t# W$ n9 q, ?0 t\" B# i
    
72. 
    * |5 F8 v3 B6 i: g/ n
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    \" ~! _\" A! f9 N; ?# d& r
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈& G1 E- r: v2 ]5 U
    
75.                      stack_ptr = stack_ptr + 1;
    * ^# b: ~+ \$ [: y  M. V
76.                      m = tree_nodeson(n);- d3 E7 q) k& _% O\" `( j9 x2 t3 w
    
77.                      stack(stack_ptr) = m;
    1 u2 z) _! S* O4 g% M  V# V
78.                      nodeinstack(m) = nodeinstack(m) + 1;
    \" C  G9 S# E8 P6 R  g
79.               elseif tree_nodeneighbor(n) ~= 09 O/ `\" N9 R% Z
    
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈. m! y6 Z! |6 l% X0 C. ~
    
81.                      m = tree_nodeneighbor(n);/ p9 G9 L: I- O2 k
    
82.                      stack(stack_ptr) = m;
      a/ [# O5 |$ y+ i! p
83.                      nodeinstack(m) = nodeinstack(m) + 1;
    5 Y6 y0 M' \9 O# A! j
84.               else
    8 U  R7 V: s7 Y% r1 N6 b
85.               %再否则，出栈，然后将父亲节点的入栈次数加一: h7 R* ^8 p' s) T8 Z+ M
    
86.                      stack_ptr = stack_ptr - 1;& B% M: W0 X3 n1 l\" s$ i# Q4 I
    
87.                      m = stack(stack_ptr);
    # [2 g; y  s' O! b2 k: d
88.                      nodeinstack(m) = nodeinstack(m) + 1;1 J7 z- l( m% ?4 q) ~3 Z
    
89.               end
    ) h- O! ~+ [$ z: m4 h) B* S
90.        end

复制代码