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

qiandongdong

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

madio

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

1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：* T8 p) j5 \5 R. h) D; s
   
2.        tree_nodename：节点名字或序号
   / S$ u5 `* B9 l4 L0 K* [
3.        tree_nodevalue：节点对应的值; P! ~: @1 O: c7 k; J3 y
   
4.        tree_nodefather：节点父亲，如果没有父亲，值为空  B8 [& L' c/ k4 O
   
5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
   ( l; M- C+ f& p
6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
   . w4 D1 K* k, r! \
7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。
   # I: ~% ]* y9 M: j9 e
8. 
   \" n# R1 k$ L0 E# L) k. {
9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
   & f- L' [6 J8 P0 B& l
10. 2 P( ^- Z( X3 h: w9 r
    
11.        %matlab源程序7 T3 L* ~( F. t4 y6 w6 C9 A
    
12.        %输入：树的深度、树的广度、搜索的值  p# S7 z+ a5 P/ J
    
13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空
    + X! ?/ _9 K; @0 ]1 M$ E( c
14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    , h3 [  [\" X7 b( ]5 H$ V8 A
15.        %根据树的深度、节点的儿子数量计算树总的节点个数8 d; {& n1 t2 `- o
    
16.        node_num = 0;
    . z! l8 x; l, o- W5 A
17.        for n= 0 : (tree_depth-1)2 @8 l\" S6 _! Z8 d
    
18.               node_num = node_num + tree_width ^ n;. J! e4 \  J% e% p0 f
    
19.        end
    ( k' z: N  E! K
20. * Y! q# C, e5 G
    
21.        %为树的存储空间赋值! S) v) N5 Y1 P
    
22.        %node name，按照广度优先为节点排号
    ! }% d: Y2 |9 l) h
23.        tree_nodename = (1 : node_num);
    # k* X\" J( s8 c/ G) n/ Z3 F2 V* N
24.        %node value! T# U/ ?) s) \0 L1 D
    
25.        tree_nodevalue = rand(1 : node_num);$ T# K9 J, ^* d7 S
    
26.        %node father and son; o1 a4 A' `$ e+ u) Y
    
27.        tree_nodefather(1) = 0;
    & {! R- Q/ L2 @; P% ~* [7 J: x
28.        tree_nodeson = zeros(1, node_num);$ \7 I% G7 v6 |, _- J6 V4 O
    
29.        n = 2;
    - d! b0 P1 x\" h3 n! h1 O
30.        k = 1;
    6 Z1 R1 s- ~7 P# O7 P\" v! [- u- O
31.        while n <= node_num& |. p# A0 {- L) ~! C$ H, D: m- ]\" v* Y
    
32.               for m = 1 : tree_width
    ! ]( Y. M$ X+ ?
33.                      tree_nodefather(n) = k;
    : Y: Y  m0 ^/ v+ y) G! y# [
34.                      if m==1
    2 |' F% x; {\" {& W, q( A
35.                             tree_nodeson(k) = n;
    * o8 J) B\" e2 {5 q  A) y
36.                      end
    & i; O; U: A5 O5 h
37.                      n = n + 1;
    2 ]3 {6 Z9 A' d9 ?. z6 r
38.               end% u3 R! L2 K8 K, W0 N  f
    
39.               k = k + 1;
    : p. K  N# U5 }3 R: ]6 D
40.        end
    8 U3 ?  H$ w: q. j/ `, {
41.        %node neighbor
    % z* }1 \0 }% w( G3 S3 F0 [
42.        tree_nodeneighbor(1) = 0;
    0 V% d4 b* n8 H  J1 ~) F6 s+ F
43.        n = 2;
    , Q# J) F1 P# L8 E; \\" C
44.        while n <= node_num
    6 d+ L6 c/ p  O+ ?
45.               for m = 1 : tree_width7 A+ `$ F3 e7 Y# G1 h
    
46.                      if m ==tree_width
    ( D4 z. r- P* \  H' t
47.                             tree_nodeneighbor(n) = 0;
    : }& j\" F# t& E. Z
48.                      else* `4 N+ D* z* V% I$ u\" g. \( h
    
49.                             tree_nodeneighbor(n) = n + 1;
    1 o' C$ [3 j5 `/ I+ j2 v
50.                      end
    ; y7 C' R/ B4 F( x9 p( e! H
51.                      n = n + 1;* o1 w1 u+ m+ ?# o% P3 {# @
    
52.               end5 C2 G# f2 T; v7 u' L
    
53.        end
    * }8 ]$ m! h5 h5 z4 G+ F, `
54. 9 G+ c( n$ |- ~7 a8 j8 F\" {
    
55.        %下面是有效程序段，用栈实现
    0 j# `' W, I! v+ i6 k' _
56.        stack = zeros(1, tree_depth);
    8 N5 G) b9 T# W7 u4 ?
57.        nodeinstack = zeros(1, node_num);
    # f8 R6 t4 O6 l
58.        stack_ptr = 1;! ^( j6 q0 D  T1 c2 E' }
    
59.        stack(1) = 1;, S! l5 u$ X/ ~- u5 O
    
60.        nodeinstack(1) = 1;
    + d% q% e; l( K( L- v1 ?
61.        valueintree = seek_value;& Q; Y0 Y' I# `  i, n8 O
    
62.        nodeintree = 0;
    # w/ L, x) K/ U9 Y3 n6 u2 K
63. ) X+ P2 q- X' a\" _- l
    
64.        while stack_ptr > 0' i6 D7 X# O6 Y$ j\" d: e
    
65.               n = stack(stack_ptr);
    ' ^3 Y( R+ f  _! R% P6 w3 G( Z' U
66.               if abs(tree_nodevalue(n) – seek_value) < 1e-3
    & [% M0 m1 }8 M) J5 {\" y/ g
67.               %如果搜索到值，返回/ e4 m* p7 h$ y6 r- e1 [& Y
    
68.                      valueintree = tree_nodevalue(n);. ^5 d\" \) Z, V- W( s
    
69.                      nodeintree = tree_nodename(n);
    $ B8 U' C) U+ Y
70.                      break;
    2 B& c  V/ {! R
71.               end
    0 e9 x& \( L3 [
72. 
    ' j9 e! w8 A' Z) r8 I; Q# O+ ?. \
73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    % O. }) m\" g3 [' O  P3 t: E
74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈# g( K5 f$ U: F9 r) F
    
75.                      stack_ptr = stack_ptr + 1;
    9 S& D& J: e- J- a+ c. b7 o  e
76.                      m = tree_nodeson(n);
    7 ?7 o1 o7 T\" H) ^4 M  H
77.                      stack(stack_ptr) = m;3 @3 _% ]( z3 s7 k+ A6 Q9 @
    
78.                      nodeinstack(m) = nodeinstack(m) + 1;- U0 ^1 x+ w8 N* a& d/ k
    
79.               elseif tree_nodeneighbor(n) ~= 0
    1 j8 U5 h$ m. O
80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈: G( X8 I( }0 H& o& s: H
    
81.                      m = tree_nodeneighbor(n);/ n* f) }. H8 T1 I- ~: }; H
    
82.                      stack(stack_ptr) = m;
    ( A& L7 I* x2 m# H' F
83.                      nodeinstack(m) = nodeinstack(m) + 1;3 m& [$ _% J0 R, U
    
84.               else/ a& [\" J4 `: b5 m- D9 l2 ]
    
85.               %再否则，出栈，然后将父亲节点的入栈次数加一
    ) t5 h1 }0 N! |( h
86.                      stack_ptr = stack_ptr - 1;! z4 i$ S4 u6 A3 z
    
87.                      m = stack(stack_ptr);
    # X\" y4 E2 ]- b4 D+ h
88.                      nodeinstack(m) = nodeinstack(m) + 1;- k& W0 d% R4 `! z; S
    
89.               end
    3 x8 k. @8 ~: Z$ |& C
90.        end

复制代码