Tag Archives: 二叉树

求二叉树的镜像

就是对二叉树及其子树,交换左右子树。

这种就是先序遍历的变种。

递归版本:

所以非递归可以用栈轻松模拟:

 [……]

继续阅读

在二叉树中找出和为某一值的所有路径

题目:输入一个整数和一棵二元树。
从树的根结点开始往下访问一直到叶结点所经过的所有结点形成一条路径。
打印出和与输入整数相等的所有路径。

例如:

10
/     \
5       12
/ \
4   7

输入整数22,输出如下路径:

10  12
10  5  7

解:就是最简单的先序遍历,只不过要记录路径,可以使用数组,我这里用的stl::vector。

注意left和right遍历后,要回退当前结点在path中状态。

算法:
[[……]

继续阅读

数据结构重读 – 二叉树

1、二叉树(Binary Tree)是一种特殊的树形结构:每个结点至多有两棵子树,即二叉树中不存在度大于2的结点。

2、二叉树的子树有左右之分,次序不能任意颠倒。

3、性质1:二叉树的第i层上至多有2^(i-1)个结点,i从1下标开始。所有

4、性质2:深度为k的二叉树至多有2^k -1个结点,k也是从1下标开始。

5、性质3:对于任何一棵二叉树,如果终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。这个很简单:

(1)设度为1的结点数为n1,则总结点数[……]

继续阅读

《数据结构》读书笔记 第六章 二叉树的三叉链表存储

今天好像大脑有点疲劳了,或者是今天写得太多了,接近400行啊~
犯了两个有意思的错误,分享一下:
(1)写查双亲节点成员函数的时候 对数据2测试怎么怎么也过不去。把parent用2种方法分别写了2次 崩溃了。然后骤然发现在之前调用了一次assign 把根结点 1–>2…….
(2)还是写这个parent的时候 居然开了个队列开始准备塞东西 然后想起来这是三叉 好像有parent指针哦……
是该歇歇了,假期《数据结构》已经啃了大半本了,修养下该开学了。这[……]

继续阅读

《数据结构》读书笔记 第六章 二叉树的二叉链表实现

没想到真的能写出来,因为这是第一次用类的方式封装描述。真的是第一次写类。而且加上二叉树这个比较难描述的东东,确实费了不少劲。发现面向对象确实是很好的。真的是让用户无需关心数据细节。当然可能是还没习惯,写得有点慢。
期间,递归的不熟练导致犯下了几次严重错误,好在自己都纠正了。
但是还有以下没有解决:
1、如何在类中调用函数指针?
2、Parent函数能不能用递归描述?

若有高手看到指点一二,不胜感激~ 微笑 
BiTree.h:定义了二叉类 BiTree以及基本操作
#in[……]

继续阅读