数学建模社区-数学中国

标题: 求树的节点个数求法，求助啊！！！ [打印本页]
作者: qiandongdong    时间: 2014-8-20 23:31
标题: 求树的节点个数求法，求助啊！！！
求树的节点个数的求法啊或matlab代码，我是新手，真心编了好久没结果。请前辈们帮帮忙啊~
作者: madio    时间: 2014-8-21 00:16
就是一个遍历树的所有节点的算法，我帮你找到一个
  1. 首先需要定义树的存储。如果是C实现，应该是链表实现，每个节点用四个属性标志：2 ?3 n# b+ n; {# s
  2.        tree_nodename：节点名字或序号; n  y4 d1 q# ?! ?! _
  3.        tree_nodevalue：节点对应的值
      I$ k" q% J' U; u* p
  4.        tree_nodefather：节点父亲，如果没有父亲，值为空
    / d7 s3 B0 h9 G
  5.        tree_nodeson：节点的第一个儿子（最左边），如果没有儿子，值为空
    & w+ Y( A3 Q8 |4 }
  6.        tree_nodeneighbor：节点的右边兄弟，如果右边没有兄弟，值为空
    + I- o5 s; k3 P) X" s/ [
  7.        树的搜索，因为不限制搜索顺序，这里使用深度优先。不用递归，可以用栈实现。$ s& w3 Y0 E4 o* D7 V1 Q

  8. . j* r/ r, V. O) r9 P
  9.        刚学了点matlab，就使用matlab实现。Matlab中没有链表的概念，用数组实现。
    ( `" y/ c8 o5 f, y; T3 K7 m% R" D

  10. ' n# T( T# H; G+ v8 N0 g" z% t
  11.        %matlab源程序
    6 \' e3 d+ w7 w
  12.        %输入：树的深度、树的广度、搜索的值/ d3 Z* D7 j' [4 V% U! \: [  f" y
  13.        %返回：树中接近的值、节点名字，如果没有接近的值，节点名字为空6 u5 J6 @0 }5 P* O6 F
  14.        function[valueintree, nodeintree] = tree(tree_depth, tree_width, seek_value)
    8 q; X" F9 U/ o8 p. b8 @
  15.        %根据树的深度、节点的儿子数量计算树总的节点个数
    + @. v* G3 Y" T! i6 v
  16.        node_num = 0;
    6 E# T. S; u9 ~' l
  17.        for n= 0 : (tree_depth-1)7 M- [$ \- `0 a+ w' a
  18.               node_num = node_num + tree_width ^ n;
    % L3 @1 D/ P# p& Z2 H% T
  19.        end
    8 ^4 x3 B- V7 A  o  Y# j6 Z
  20. 4 a" m) w- G( r9 M! v# n
  21.        %为树的存储空间赋值& J) f7 }/ v8 ^& m. ~
  22.        %node name，按照广度优先为节点排号
    ) O) \+ d. ?% a/ U9 E: Z( Q$ o
  23.        tree_nodename = (1 : node_num);
    ; T. W5 H1 H, Z' E
  24.        %node value$ D; c* l" ~/ w: p1 x2 w* \
  25.        tree_nodevalue = rand(1 : node_num);- r- l7 X2 ~! S! J
  26.        %node father and son/ O" E; ?: Q8 c4 |; Y1 l
  27.        tree_nodefather(1) = 0;
    0 `- \' t0 R$ n; _" G
  28.        tree_nodeson = zeros(1, node_num);
    0 K$ R+ }/ R) v% Z3 `
  29.        n = 2;  s2 y1 J& M* \" S3 }8 v  I2 J
  30.        k = 1;1 c+ @  z5 r; w; C! \4 A% M& s
  31.        while n <= node_num
    7 P2 \7 V0 S4 D4 Y; W
  32.               for m = 1 : tree_width
    . f. I! h# I7 j( @3 p# ^. c
  33.                      tree_nodefather(n) = k;2 H4 d3 _- v6 E$ f8 J3 `: f* z% H
  34.                      if m==1
    & Q1 f' f+ F) M; E
  35.                             tree_nodeson(k) = n;0 W+ ~. i/ k; D; c4 g
  36.                      end% x7 I4 d# B: _7 m$ W9 i) P
  37.                      n = n + 1;
    6 C. \4 X+ r5 i/ c# G9 k
  38.               end
    # b0 M4 d  f0 r* w+ s
  39.               k = k + 1;5 z' J( |# ^  D0 r. `- a
  40.        end) m8 [, U  q8 |3 C* s! k4 B6 W0 V
  41.        %node neighbor
      g0 g* k: `/ E. |% I
  42.        tree_nodeneighbor(1) = 0;8 N( S" s6 E1 ^9 D
  43.        n = 2;$ Z  s/ A; z9 {$ R5 L
  44.        while n <= node_num& i3 M( B# I1 A  m: t
  45.               for m = 1 : tree_width
    " ?6 m, j; _; o
  46.                      if m ==tree_width+ ^) h. E% m  s2 m% }8 [4 Y) B
  47.                             tree_nodeneighbor(n) = 0;
    8 b: Q4 i' u; s2 _+ A! @1 j
  48.                      else9 \6 h( h  Q) b1 N3 x
  49.                             tree_nodeneighbor(n) = n + 1;) T3 Q7 T0 `5 _; y4 b
  50.                      end
    . J4 P- q% `. C' \7 e. O0 p
  51.                      n = n + 1;
    4 o6 ]7 a% z% P$ @
  52.               end( \! c* y" x) [' d( o2 u$ [* h( o- V
  53.        end
    + ^  B* w4 ^( z0 H3 A

  54. 8 ~3 Y, w$ k- {3 ?+ ]! ?" z3 d
  55.        %下面是有效程序段，用栈实现+ P4 U6 k4 X; r2 |9 ~
  56.        stack = zeros(1, tree_depth);
    + }' B3 ^$ I* r" W/ e
  57.        nodeinstack = zeros(1, node_num);% f, a' S  c' U$ \
  58.        stack_ptr = 1;( ?, O  \' k3 ~
  59.        stack(1) = 1;; V8 ~$ Y9 @9 F
  60.        nodeinstack(1) = 1;
    % D1 w  U$ N# L! @1 O7 y% j8 l
  61.        valueintree = seek_value;
    2 P! ~! z5 w6 L1 y4 `
  62.        nodeintree = 0;& V% m) E0 v0 Y8 a# ^8 a
  63. , c: S. \' R' ^- F9 n& L
  64.        while stack_ptr > 0
    6 y: V! P, R6 o3 |* o8 u1 n: J
  65.               n = stack(stack_ptr);
    ; S" N3 z5 O8 _& a+ ~& F8 X" h
  66.               if abs(tree_nodevalue(n) – seek_value) < 1e-39 p8 d4 c6 v) R
  67.               %如果搜索到值，返回
    , b" E: S# j. J. n* o! d5 N  ~
  68.                      valueintree = tree_nodevalue(n);
    ( N6 H0 X; i: U- l
  69.                      nodeintree = tree_nodename(n);2 w4 m" Y, r; X  s. c0 |! j* ?3 H
  70.                      break;
    ' E3 V- t3 @( r- Y2 S
  71.               end
    9 M) G5 Q. A% K! @- B6 E5 ?, k

  72. 2 s; F6 }2 y+ f* ]' O
  73.               if tree_nodeson(n) ~= 0 & nodeinstack(n) == 1
    - A( A# p" m' m: ~/ n- r# ^
  74.               %如果节点有儿子，并且第一次入栈，将儿子节点入栈
    $ c5 A1 H, ^* E  L0 r" i
  75.                      stack_ptr = stack_ptr + 1;$ A, F" u$ h8 Z6 f
  76.                      m = tree_nodeson(n);% |7 r; o9 v8 v+ ]9 [
  77.                      stack(stack_ptr) = m;; M2 |0 P+ Y+ Z* {2 R# H% `- W  M" c
  78.                      nodeinstack(m) = nodeinstack(m) + 1;
    4 J  u9 y. n9 G5 ]6 L- W/ G
  79.               elseif tree_nodeneighbor(n) ~= 0; w( `  A( u& G/ w
  80.               %否则，如果节点右边有兄弟，节点出栈，然后将右边兄弟入栈. Y/ L- z8 b7 [7 p
  81.                      m = tree_nodeneighbor(n);
    + Q$ i+ y5 `0 P$ x+ K8 H
  82.                      stack(stack_ptr) = m;* c/ N3 a8 Z1 N9 r2 L, x$ |$ J
  83.                      nodeinstack(m) = nodeinstack(m) + 1;3 \* g4 \( S0 q2 N: l3 A; e" ?
  84.               else
    5 v/ c0 O* b4 ~& X
  85.               %再否则，出栈，然后将父亲节点的入栈次数加一, E3 @* k& [( s! ]
  86.                      stack_ptr = stack_ptr - 1;1 }: m! E  C" n8 b
  87.                      m = stack(stack_ptr);
    . e& Z$ ?  t( H  }
  88.                      nodeinstack(m) = nodeinstack(m) + 1;
    * |1 U2 Y6 g& _
  89.               end
    9 {- m; G: [8 N# o* s2 M/ H8 W
  90.        end
复制代码




欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5