比较树代码,C代码库,德仔网

代码语言
代码分类
【C】比较树
作者:false / 发布于2012/3/6/ 720
#include <stdio.h></div>
#include <string.h></div>
#include <stdlib.h></div>
<div></div>
<div>define bool int</div>
<div>define true 1</div>
<div>define false 0</div>
<div></div>
<div>typedef struct Node *Tree;<span class="Apple-tab-span" style="white-space:pre">	</span>/*自定义树节点指针数据类型*/</div>
<div></div>
<div>Tree InsertX(int x,Tree T);</div>
<div>/*****************************</div>
<div>功能：用于向树中插入元素</div>
<div>输入：待插入元素，树所在地址</div>
<div>输出：插入后树的地址</div>
<div>*****************************/</div>
<div>bool Compare(Tree T, Tree X);</div>
<div>/*****************************</div>
<div>功能：比较两棵树是否完全相同</div>
<div>输入：待比较的两棵树的头地址</div>
<div>输出：不同时输出0，相同时输出1</div>
<div>*****************************/</div>
<div>Tree MakeEmpty(Tree T);</div>
<div>/*****************************</div>
<div>功能：清空树</div>
<div>输入：待清空树的头地址</div>
<div>输出：空树指针</div>
<div>*****************************/</div>
<div></div>
<div>/*树节点结构体声明*/</div>
<div>typedef struct Node</div>
<div>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>int element;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>Tree Left;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>Tree Right;</div>
<div>}TreeNode;</div>
<div></div>
<div>Tree InsertX(int x, Tree T)</div>
<div>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(T == NULL)<span class="Apple-tab-span" style="white-space:pre">					</span>/*开始构建树*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>T = (Tree)malloc(sizeof(TreeNode));</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>if(T == NULL)</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>printf("Out of space!");</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>exit(0);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>else<span class="Apple-tab-span" style="white-space:pre">						</span>/*插入元素*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>T->element = x;</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>T->Right = T->Left = NULL;</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>else if(x < T->element)<span class="Apple-tab-span" style="white-space:pre">			</span>/*判断插入位置为左*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>T->Left = InsertX(x, T->Left);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>else if(x > T->element)<span class="Apple-tab-span" style="white-space:pre">			</span>/*判断插入位置为右*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>T->Right = InsertX(x, T->Right);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>return T;<span class="Apple-tab-span" style="white-space:pre">						</span>/*返回树的头指针*/</div>
<div>}
<div></div>
<div>bool Compare(Tree T, Tree X)</div>
<div>{</div>
<div> if(T == NULL && X == NULL)<span class="Apple-tab-span" style="white-space:pre">		</span>/*两棵树都不存在或者迭代到对应树叶的位置*/</div>
<div> {</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>  return true;</div>
<div> }
<div> else if(T->element != X->element)/*两棵树相同位置元素不同*/</div>
<div> {</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>  return false;</div>
<div> }
<div> else<span class="Apple-tab-span" style="white-space:pre">	</span>if(Compare(T->Left, X->Left) && Compare(T->Right, X->Right)) /*迭代比较左子树，右子树*/</div>
<div> {</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>return true;</div>
<div> }
<div>}
<div></div>
<div>Tree MakeEmpty(Tree T)</div>
<div>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>if(T != NULL)</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>MakeEmpty(T->Left);<span class="Apple-tab-span" style="white-space:pre">			</span>/*迭代清空*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>MakeEmpty(T->Right);<span class="Apple-tab-span" style="white-space:pre">		</span>/*迭代清空*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>free(T);</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>return NULL;</div>
<div>}
<div></div>
<div>int main(void)</div>
<div>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>int n, a, i, j, x;</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>char* output[2]={"No","Yes"};<span class="Apple-tab-span" style="white-space:pre">	</span>/*输出结果*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>Tree X = NULL,</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span> T = NULL;<span class="Apple-tab-span" style="white-space:pre">					</span>/*设置初始值*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>while(1)<span class="Apple-tab-span" style="white-space:pre">						</span></div>
<div><span class="Apple-tab-span" style="white-space:pre">	</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>T = MakeEmpty(T);<span class="Apple-tab-span" style="white-space:pre">			</span>/*清空树释放内存*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>X = MakeEmpty(X);</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>scanf("%d", &n);<span class="Apple-tab-span" style="white-space:pre">			</span>/*输入n，n=0则退出*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>if(n == 0)</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>break;</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>scanf("%d", &a);<span class="Apple-tab-span" style="white-space:pre">			</span>/*输入比较次数*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>for(i = 0; i < n; i++)</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>scanf("%d", &x);<span class="Apple-tab-span" style="white-space:pre">		</span>/*输入待插入值*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>T = InsertX(x, T);<span class="Apple-tab-span" style="white-space:pre">		</span>/*向树中插入元素*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">		</span>for(j = 0; j < a; j++)</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>X = MakeEmpty(X);<span class="Apple-tab-span" style="white-space:pre">		</span>/*清空树进行新一次测试*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>for(i = 0; i < n; i++)</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>{</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>scanf("%d", &x);<span class="Apple-tab-span" style="white-space:pre">	</span>/*输入待插入值*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">				</span>X = InsertX(x, X);<span class="Apple-tab-span" style="white-space:pre">	</span>/*向树中插入元素*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">			</span>}
<div><span class="Apple-tab-span" style="white-space:pre">			</span>printf("%s\n", output[Compare(T, X)]);/*比较标本树和待比较树并输出结果*/</div>
<div><span class="Apple-tab-span" style="white-space:pre">		</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>}
<div><span class="Apple-tab-span" style="white-space:pre">	</span>return 0;</div>
<div>}
试试其它关键字
　比较树　
同语言下
可能有用的
false贡献的其它代码(2)