关于树的常见操作-C++面试

时间:2021-07-27 08:57:43
 #include <iostream>
using namespace std; //树的存储结构与设计
struct BitNode
{
int data;
BitNode* leftChild;
BitNode* rightChild;
BitNode()
{
leftChild = NULL;
rightChild = NULL;
}
BitNode(int x) :data(x), leftChild(NULL), rightChild(NULL)
{ }
};
//树的先序遍历
void PreOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
cout << T->data;
PreOrder(T->leftChild);
PreOrder(T->rightChild);
return; }
//树的中序遍历
void InOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
InOrder(T->leftChild);
cout << T->data;
InOrder(T->rightChild);
return;
}
//树的后序遍历
void PostOrder(BitNode* T)
{
if (T == NULL)
{
return;
}
PostOrder(T->leftChild);
PostOrder(T->rightChild);
cout << T->data;
}
//求树的叶子结点个数
int sum = ;
int CountLeafNum(BitNode* T)
{ if (T == NULL)
{
return ;
}
if (T->leftChild == NULL && T->rightChild == NULL)
{
sum++;
}
CountLeafNum(T->leftChild);
CountLeafNum(T->rightChild);
return sum;
}
//求树的叶子结点个数-两个参数
void CountLeafNum(BitNode* T, int* sum)
{
if (T == NULL)
{
return;
}
if (T->leftChild == NULL && T->rightChild == NULL)
{
*sum = *sum + ; //等价于(*sum)++
}
CountLeafNum(T->leftChild, sum);
CountLeafNum(T->rightChild, sum);
}
//求树的深度
int DepthOfTree(BitNode* T)
{
int depthLeft = ;
int depthRight = ;
int depth = ;
if (T == NULL)
return ;
depthLeft = DepthOfTree(T->leftChild);
depthRight = DepthOfTree(T->rightChild);
depth = + ((depthLeft >depthRight)? depthLeft : depthRight);
return depth;
}
//复制二叉树--用递归的思想,必须先根据返回值,定义新的变量类型用于递归的返回值赋值
BitNode* Copy(BitNode* T)
{
if (T == NULL)
{
return NULL;
}
//用的前序遍历思想
BitNode* newTreeLeft = Copy(T->leftChild);
BitNode* newTreeRight = Copy(T->rightChild); //建立一个结点
BitNode* newNode = new BitNode();
if (newNode == NULL)
{
return NULL;
}
newNode->data = T->data;
newNode->leftChild = newTreeLeft;
newNode->rightChild = newTreeRight;
return newNode;
}
int main()
{
BitNode nodeA();
BitNode nodeB();
BitNode nodeC();
BitNode nodeD();
BitNode nodeE();
BitNode nodeF(); nodeA.leftChild = &nodeB;
nodeA.rightChild = &nodeC;
nodeB.leftChild = &nodeD;
nodeB.rightChild = &nodeE;
nodeC.leftChild = &nodeF; //前序遍历二叉树
cout << "前序遍历二叉树 " << ":";
PreOrder(&nodeA);
cout << endl;
//中序遍历二叉树
cout << "中序遍历二叉树 " << ":";
InOrder(&nodeA);
cout << endl;
//后序遍历二叉树
cout << "后序遍历二叉树 " << ":";
PostOrder(&nodeA);
cout << endl; //树的结点个数
int leafCount = CountLeafNum(&nodeA);
cout << "树的结点个数:" << leafCount << endl; //树的深度
int depth = DepthOfTree(&nodeA);
cout << "树的深度:" << depth << endl; //赋值一棵树
BitNode* newNode = Copy(&nodeA);
//后序遍历二叉树
cout << "后序遍历二叉树 " << ":";
PostOrder(newNode);
cout << endl; system("pause");
return ;
}

关于树的常见操作-C++面试的更多相关文章

  1. C&num;路径&sol;文件&sol;目录&sol;I&sol;O常见操作汇总

    文件操作是程序中非常基础和重要的内容,而路径.文件.目录以及I/O都是在进行文件操作时的常见主题,这里想把这些常见的问题作个总结,对于每个问题,尽量提供一些解决方案,即使没有你想要的答案,也希望能提供 ...

  2. C&num;路径&sol;文件&sol;目录&sol;I&sol;O常见操作汇总&lt&semi;转载&gt&semi;

    文件操作是程序中非常基础和重要的内容,而路径.文件.目录以及I/O都是在进行文件操作时的常见主题,这里想把这些常见的问题作个总结,对于每个问题,尽量提供一些解决方案,即使没有你想要的答案,也希望能提供 ...

  3. 【转】C&num;路径&sol;文件&sol;目录&sol;I&sol;O常见操作汇总

    文件操作是程序中非常基础和重要的内容,而路径.文件.目录以及I/O都是在进行文件操作时的常见主题,这里想把这些常见的问题作个总结,对于每个问题,尽量提供一些解决方案,即使没有你想要的答案,也希望能提供 ...

  4. C&num;路径&comma;文件&comma;目录&comma;I&sol;O常见操作

         C#路径,文件,目录,I/O常见操作 文件操作是程序中非常基础和重要的内容,而路径.文件.目录以及I/O都是在进行文件操作时的常见主题,这里想把这些常见的问题作个总结,对于每个问题,尽量提供 ...

  5. JS 数组常见操作汇总,数组去重、降维、排序、多数组合并实现思路整理

    壹 ❀ 引 JavaScript开发中数组加工极为常见,其次在面试中被问及的概率也特别高,一直想整理一篇关于数组常见操作的文章,本文也算了却心愿了. 说在前面,文中的实现并非最佳,实现虽然有很多种,但 ...

  6. 动态单链表的传统存储方式和10种常见操作-C语言实现

    顺序线性表的优点:方便存取(随机的),特点是物理位置和逻辑为主都是连续的(相邻).但是也有不足,比如:前面的插入和删除算法,需要移动大量元素,浪费时间,那么链式线性表 (简称链表) 就能解决这个问题. ...

  7. X-Cart 学习笔记(四)常见操作

    目录 X-Cart 学习笔记(一)了解和安装X-Cart X-Cart 学习笔记(二)X-Cart框架1 X-Cart 学习笔记(三)X-Cart框架2 X-Cart 学习笔记(四)常见操作 五.常见 ...

  8. 转:jQuery 常见操作实现方式

    http://www.cnblogs.com/guomingfeng/articles/2038707.html 一个优秀的 JavaScript 框架,一篇 jQuery 常用方法及函数的文章留存备 ...

  9. jQuery 常见操作实现方式

    一个优秀的 JavaScript 框架,一篇 jQuery 常用方法及函数的文章留存备忘. jQuery 常见操作实现方式 $("标签名") //取html元素 document. ...

随机推荐

  1. &lbrack;Android&rsqb;使用自定义JUnit Rules、annotations和Resources进行单元测试(翻译)

    以下内容为原创,欢迎转载,转载请注明 来自天天博客:http://www.cnblogs.com/tiantianbyconan/p/5795091.html 使用自定义JUnit Rules.ann ...

  2. Node&period;js 学习资源

    这篇文章编译整理自Stack Overflow的一个如何开始学习Node.js的Wiki帖,这份资源列表在SO上面浏览接近60万次,数千个收藏和顶.特意整理发布到这里,其中添加了部分中文参考资料. 学 ...

  3. starUML 建模

    1. starUML 序列图建模 参考: [1]. starUML 序列图建模.  http://blog.csdn.net/u013474104/article/details/43818691

  4. 问题解决——在STL的queue中使用自定义类

    本文原创,转载请保证文章的完整性,并显要的注明出处. 本文链接:http://blog.csdn.net/wlsgzl/article/details/38843513 平时很少用STL,就算用,也基 ...

  5. Android&colon;Touch和Click的区别

    http://blog.csdn.net/hufeng882412/article/details/7310142 针对屏幕上的一个View控件,Android如何区分应当触发onTouchEvent ...

  6. python初准备:安装easy&lowbar;install和pip

    安装easy_install wget http://peak.telecommunity.com/dist/ez_setup.py python ez_setup.py 安装pip wget htt ...

  7. linux下emacs安装

    1.下载地址:http://ftp.gnu.org/pub/gnu/emacs/ 下载文件:emacs-24.2.tar.gz 步骤: 一.安装依赖文件:  (先进入root:终端中输入 su -) ...

  8. POJ2125 Destroying The Graph 二分图 &plus; 最小点权覆盖 &plus; 最小割

    思路来源:http://blog.csdn.net/lenleaves/article/details/7873441 求最小点权覆盖,同样求一个最小割,但是要求出割去了那些边, 只要用最终的剩余网络 ...

  9. spriteJS

    https://blog.csdn.net/qq_37261367/article/details/84662028

  10. Linux 任务管理 &amp&semi;&amp&semi; 常用指令

    A.linux死机 转自:https://www.deleak.com/blog/2010/10/20/sysrq/ linux死机了怎么办? 曾经啊,对着键盘上 Print Screen/SysRq ...