二叉树的存储和操作代码,C代码库,德仔网

代码语言
代码分类
【C】二叉树的存储和操作
作者:Dezai.CN / 发布于2011/8/1/ 721
(1)建立二叉树的二叉链表存储，并对它进行中序遍历(2)求二叉树的结点数(3)求高度
<div><span style="color: rgb(0,0,0)">#include</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">iostream.h</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">
typedef </span><span style="color: rgb(0,0,255)">char</span><span style="color: rgb(0,0,0)"> TElemType;
typedef </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> BiTNode
{
 TElemType data;
 </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> BiTNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">lchild;
 </span><span style="color: rgb(0,0,255)">struct</span><span style="color: rgb(0,0,0)"> BiTNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">rchild;
}BiTNode;
typedef BiTNode </span><span style="color: rgb(0,0,0)">*</span><span style="color: rgb(0,0,0)">BiTree;
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==============================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> CreateBiTree_Rec(BiTree </span><span style="color: rgb(0,0,0)">&</span><span style="color: rgb(0,0,0)">T)
{
 TElemType ch;
 cin</span><span style="color: rgb(0,0,0)">>></span><span style="color: rgb(0,0,0)">ch;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(ch</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(128,0,0)">#</span><span style="color: rgb(128,0,0)">'</span><span style="color: rgb(0,0,0)">)
 T</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">NULL;
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 T</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,255)">new</span><span style="color: rgb(0,0,0)"> BiTNode; 
 T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">data</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">ch;
 CreateBiTree_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild);
 CreateBiTree_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild);
 }
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=============================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> InOrder_Rec(BiTree T)
{
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(T)
 {
 
 InOrder_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild); cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">data;
 InOrder_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild);
 }
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==========================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> Leafs_Rec(BiTree T)
{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> l_Leafs,r_Leafs;
 </span><span style="color: rgb(0,0,255)">static</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> i</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(T</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">NULL)
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 i</span><span style="color: rgb(0,0,0)">++</span><span style="color: rgb(0,0,0)">;
 l_Leafs</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Leafs_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild);
 r_Leafs</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Leafs_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild);
 }
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> i;
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">=========================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> Leafs_Rec1(BiTree T)
{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> l_Leafs,r_Leafs;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(T</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">NULL)
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">((T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">NULL)</span><span style="color: rgb(0,0,0)">&&</span><span style="color: rgb(0,0,0)">(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild</span><span style="color: rgb(0,0,0)">==</span><span style="color: rgb(0,0,0)">NULL))
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 l_Leafs</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Leafs_Rec1(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild);
 r_Leafs</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">Leafs_Rec1(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild);
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> (l_Leafs</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(0,0,0)">r_Leafs);
 }
 
 }
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">============================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> BiTreeDepth_Rec(BiTree T)
{
 </span><span style="color: rgb(0,0,255)">int</span><span style="color: rgb(0,0,0)"> depth_l,depth_r;
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(</span><span style="color: rgb(0,0,0)">!</span><span style="color: rgb(0,0,0)">T)
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> </span><span style="color: rgb(128,0,128)">0</span><span style="color: rgb(0,0,0)">;
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 {
 depth_l</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">BiTreeDepth_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">lchild);
 depth_r</span><span style="color: rgb(0,0,0)">=</span><span style="color: rgb(0,0,0)">BiTreeDepth_Rec(T</span><span style="color: rgb(0,0,0)">-></span><span style="color: rgb(0,0,0)">rchild); 
 </span><span style="color: rgb(0,0,255)">if</span><span style="color: rgb(0,0,0)">(depth_l</span><span style="color: rgb(0,0,0)">>=</span><span style="color: rgb(0,0,0)">depth_r)
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> (depth_l</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">);
 </span><span style="color: rgb(0,0,255)">else</span><span style="color: rgb(0,0,0)">
 </span><span style="color: rgb(0,0,255)">return</span><span style="color: rgb(0,0,0)"> (depth_r</span><span style="color: rgb(0,0,0)">+</span><span style="color: rgb(128,0,128)">1</span><span style="color: rgb(0,0,0)">);
 }
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">==========================================================================</span><span style="color: rgb(0,128,0)">
</span><span style="color: rgb(0,0,255)">void</span><span style="color: rgb(0,0,0)"> main()
{
 BiTree T;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">请按要求(前序序列建立)输入您所要输入的字符串：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 CreateBiTree_Rec(T);
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">中序递归遍历输出为：\n</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)">;
 InOrder_Rec(T);
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">该二叉树的结点数目为：</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">Leafs_Rec(T)</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">该二叉树的叶子结点数目为：</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">Leafs_Rec1(T)</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
 cout</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(128,0,0)">该二叉树的深度为：</span><span style="color: rgb(128,0,0)">"</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">BiTreeDepth_Rec(T)</span><span style="color: rgb(0,0,0)"><<</span><span style="color: rgb(0,0,0)">endl;
}
</span><span style="color: rgb(0,128,0)">//</span><span style="color: rgb(0,128,0)">============================================================================</span></div>
试试其它关键字
　二叉树　
同语言下
可能有用的
Dezai.CN贡献的其它代码(4037)