QQ登录

只需一步,快速开始

搜索
【活动】边做笔记边学习,还能赢取奖学金!
查看: 77|回复: 0

[学习笔记] 《数据结构与算法》——二叉树

[复制链接]
累计签到:17 天
连续签到:3 天
最佳答案
0 
发表于 2017-8-5 09:23:38 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1.视频一共介绍了三种储存方式,父母,孩子,以及父母和孩子。利用父母储存法,在每一个节点都保存了父母的地址,所以根据儿子节点我们可以快速地找到它的父母;同理,孩子储存法和父母孩子储存法则能快速地找到该节点的孩子,或者孩子和父母。
2.满二叉树:节点个数n和深度k满足n=2^k-1,即除了叶子其他节点都有两个子节点。
  完全二叉树:根据层编号后,编号与满二叉树一致。
——>满二叉树是一种特殊的完全二叉树
——>完全二叉树的度为0的节点个数n0,度为2的节点个数n2,满足n0=n2+1。
3.完全二叉树根据层编号后,满足
——>[i/2]是i父母节点,若i*2>n,则该节点没有左节点;若i*2+1>n,则该节点没有子节点
4.二叉树的遍历
1)前序遍历:若二叉树为空,则返回;否则,先访问根节点,然后前序遍历左子树,再前序遍历右子树
2)后序遍历:从左到右先子叶后节点的方式遍历访问左右子树,最后访问根节点。
3)中序遍历:从根节点开始,先中序遍历左子树,然后访问根节点,最后再中序遍历右子树。
4)层序遍历:从根节点开始,从上往下,从左往右逐层遍历

5.二叉树的建立和遍历
1)建立:定义一个有着两个指针的结构体,利用递归的方法,将数据不断地从上到下,从左到右地储存在二叉树中完成建立
2)遍历:根据根节点,我们可以利用四种遍历方式,用递归的方式实现遍历
  1. #include<cstdlib>
  2. #include<cstdio>
  3. #include<iostream>
  4. using namespace std;

  5. class bitree
  6. {
  7. public:
  8.         char data;
  9.         bitree *l, *r;
  10. };

  11. void Create(bitree *&p)
  12. {
  13.         char c;
  14.         scanf_s("%c", &c);
  15.         if (' ' == c)
  16.         {
  17.                 p = NULL;
  18.                 return;
  19.         }
  20.         else
  21.         {
  22.                 p = new bitree;
  23.                 p->data = c;
  24.                 Create(p->r);
  25.                 Create(p->l);
  26.         }
  27. }

  28. void TreeTravel(bitree *p,int level)
  29. {
  30.         if (p != NULL)
  31.         {
  32.                 printf("%c is in the level %d\n", p->data, level);
  33.                 TreeTravel(p->l, level + 1);
  34.                 TreeTravel(p->r, level + 1);
  35.         }
  36.        
  37. }

  38. int main()
  39. {
  40.         bitree *root=NULL;
  41.         Create(root);
  42.         TreeTravel(root, 1);

  43.         system("PAUSE");
  44. }
复制代码

本帖被以下淘专辑推荐:

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-8-20 04:38 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表