自学到二叉树的时候,有一段关于遍历二叉树的代码看不懂.....
2024-05-19 02:46
1. 自学到二叉树的时候,有一段关于遍历二叉树的代码看不懂.....
这是中序遍历二叉树。
按左子结点，父结点，右子结点顺序输出。
函数分为三个部分。
第一个部分if（pNode->pLeft）
{.....；}
这个意思是说，如果头结点的左子不为空，也就是说如果父结点有左子结点的话。
进入递归。函数的实参是父结点的左子结点。
再看这个结点有没有左子结点。如果有，继续递归，实参是这个结点的左子结点。
一直到某个结点的左子为空了，也就是没有左子了，这个时候当前执行的函数就进入下一个部分了。
下一个部分是输出这个结点的数据。
然后就是最后一个部分，递归父节点的右子。（如果有右子的话）
不过还是得先看当前结点有没有左子，如果有，递归，如果没有，输出结点数据。然后判断右子。
看图，输出的是应该是cbdafeg。
第一次①a结点，进入函数判断有没有左子，有，递归到b，②判断有没有左子，有，递归到c，③判断有没有左子，没有，输出c。判断有没有右子，没有。这个函数结束。返回到调用它的函数②里，这时候第一部分已经执行完毕（即使③），执行输出b，然后判断有没有右子，有，递归到d。④判断有没有左子，没有，输出d，判断有没有右子，没有，返回函数②，这时候函数②三个部分执行完毕，返回到函数①，这时候函数①也只是执行完第一部分，然后输出a。然后判断有没有右子，有。然后不就不往下说了。
2. c语言二叉树问题，勿写代码，求详细思考过程
后序遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。（先左后右） 中序遍历：若树不空，则先访问左子树，再访问根，再访问右子树。 从后序遍历：CDABE得出E是最顶根节点。 然后中序遍历：CADEB得出CAD是E的左子树中的，B是E的右子树中的。 再分析后序遍历CDA可以知道A是CD的根， 而中序是CAD得到C是A的左子树，D是A的右子树。（如下图） 最后，先序遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。 于是得到结束： 先序遍历是 EACDB
3. 二叉树遍历演示
四、 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施 操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就 是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比 较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按 层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列
（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。 由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild);
}（2）中序遍历递归算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}（3）后序遍历递归算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 2 、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
void LevelOreder(QBTree BT) {
for (i=1;i<=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);
}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作； 而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(BTree *BT) {
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //访问根结点，并将根结点入队
while (!QueueEmpty(Q)) { //当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //处理左孩子 if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //处理右孩子 }
}
五、典型二叉树的操作算法 1、 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉 树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判 断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结 点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针 参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //构造左子树
BT->rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
} 2、 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否 为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count); //计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
Leaf(BT->rchild,&count); //计算右子树的叶子结点个数
}
} 3、 交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一 些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchildBT->rchild;
}
} 4 、求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) { //h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
} 六、树、森林与二叉树的转换 1、 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根 结点看作兄弟关系，并对其中的每棵树依依地进行转换。 2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用 1、哈夫曼树的定义及特点
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着 程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为 这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad");
else if (socre<70) printf("pass");
else if (score<80) printf("general");
else if (score<90) printf("good");
esle printf("very good"); 在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
（1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；
（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。
最后得出每个字符的编码为：比如，发送一段编码：0000011011010010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
4. 程序二叉树的问题
log2 N +1=log2(2011) +1=12
5. 线索二叉树的完整代码是怎么样的?
线索二叉树：二叉树的结点上加上线索的二叉树
6. 线段树为什么是二叉搜索树
根据我学习到的知识，线段树不是二叉搜索树。
线段树是二叉树
线段树的下标是递增的。
碰巧的是二叉搜索树也满足这个性质。
但是明显的区别是：二叉搜索树是可以添加和删除节点的，而线段树应该是不可以实现这个过程的。因为线段树是根据原本就有的大小关系建立的树，而二叉搜索树可以每次找到一个满足条件的位置插入。
然后我查了一下百度百科：
线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
百度百科是矛盾的，yeah !
啊，那就重新定义二叉搜索树吧。
广义的二叉搜索树： 既是二叉树，又可以支持一些搜索操作...
哇，线段树都满足诶。
【......】
7. 树 - 二叉树 - 二叉树的定义
二叉树是树形结构的一个重要类型 许多实际问题抽象出来的数据结构往往是二叉树的形式 即使是一般的树也能简单地转换为二
叉树 而且二叉树的存储结构及其算法都较为简单 因此二叉树显得特别重要
二叉树的定义
二叉树的递归定义
二叉树(BinaryTree)是n(n≥ )个结点的有限集 它或者是空集(n= ) 或者由一个根结点及两棵互不相交的 分别称作这个根
的 左子树 和 右子树 的二叉树组成
二叉树的五种基本形态
二叉树可以是空集;根可以有空的左子树或右子树;或者左 右子树皆为空
二叉树的五种基本形态如下图所示
二叉树不是树的特例
( )二叉树与无序树不同
二叉树中 每个结点最多只能有两棵子树 并且有左右之分
二叉树并非是树的特殊情形 它们是两种不同的数据结构
( )二叉树与度数为 的有序树不同
在有序树中 虽然一个结点的孩子之间是有左右次序的 但是若该结点只有一个孩子 就无须区分其左右次序 而在二叉树中 即使
是一个孩子也有左右之分
【例】下图中(a)和(b)是两棵不同的二叉树 它们同右图中的普通树(作为有序树或无序树)很相似 但却不等同于这棵普通树 若
将这三棵树均看做普通树 则它们就是相同的了
二叉树并非是树的特殊情形 它们是两种不同的数据结构
lishixinzhi/Article/program/sjjg/201311/23890
8. 二叉树-完全二叉树
假设完全二叉树的高度为h(h≥1),那么 有2 h-1 个结点（最后一层至少有一个）， 有2 h -1个结点（满二叉树）。
如果高度h，总的结点树为n
一棵树有n(n>0)个结点的完全二叉树，从上到下，从左到右从1开始进行编号，对于任意第i个结点
思考
假设：叶子结点树为n0,度为1的节点数为n1， 度为2的结点树为n2
总结点树 n = n0 + n1 + n2，且n0 = n2 + 1 ，推出 n = 2n0 + n1 - 1 由于完全二叉树n1 要么为0，要么为1
在计算机语言中，除法一般默认为向下取整 所以 n0 = floor((n + 1) / 2) 结果为 (768 + 1) / 2 = 384.5 = 384个叶子结点
最新文章
热门文章
推荐阅读