随机排号算法_二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上的基本操作（c++）

Ⅰ 二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上的基本操作。（c++）

浅谈数据结构-二叉树

二叉树是树的特殊一种，具有如下特点：1、每个结点最多有两颗子树，结点的度最大为2。2、左子树和右子树是有顺序的，次序不能颠倒。3、即使某结点只有一个子树，也要区分左右子树。

一、特殊的二叉树及特点

1、斜树

所有的结点都只有左子树（左斜树），或者只有右子树（右斜树）。这就是斜树，应用较少

基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问根结点即左—右—根。

图中后序遍历结果是：4，8，7，5，2，6，3，1。

后序递归遍历代码实现，如下所示。

//后序递归遍历void PostOrderTraverse(BiTree t)

{ if(t != NULL)

{

PostOrderTraverse(t->lchild);

PostOrderTraverse(t->rchild);

printf("%c ", t->data);

}

后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中，要保证左孩子和右孩子都已被访问，并且左孩子在右孩子之前访问才能访问根结点，这就为流程控制带来了难题。下面介绍一种思路。

要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点p，先将其入栈。若p不存在左孩子和右孩子，则可以直接访问它，或者p存在左孩子或右孩子，但是其左孩子和右孩子都已经被访问过了，则同样可以直接访问该结点。若非上述两种情况，则将p的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩子之前别访问，左孩子和右孩子都在根结点前面被访问。

//后序非递归遍历二叉树int NoPostOrderTraverse(BiTree t)

{

SqStack s;

InitStack(&s);

BiTree cur; //当前结点

BiTree pre = NULL; //前一次访问的结点 BiTree tmp;

if(t == NULL)

{

fprintf(stderr, "the tree is null. "); return ERROR;

}

Push(&s, t); while(IsEmpty(&s) != 1)

{

GetTop(&s, &cur);// if((cur->lchild == NULL && cur->rchild == NULL) || (pre != NULL && (pre == cur->lchild || pre == cur->rchild)))

{

printf("%c ", cur->data); //如果当前结点没有孩子结点或者孩子结点都已被访问过

Pop(&s, &tmp);

pre = cur;

} else

{ if(cur->rchild != NULL)

{

Push(&s, cur->rchild);

} if(cur->lchild != NULL)

{

Push(&s, cur->lchild);

}

} return OK;

}

五、二叉树的建立

其实而二叉树的建立就是二叉树的遍历，只不过将输入内容改为建立结点而已，比如，利用前序遍历建立二叉树

//创建树//按先后次序输入二叉树中结点的值(一个字符),#表示空树//构造二叉链表表示的二叉树BiTree CreateTree(BiTree t)

{ char ch;

scanf("%c", &ch);

if(ch == '#')

{

t = NULL;

} else

{

t = (BitNode *)malloc(sizeof(BitNode)); if(t == NULL)

{

fprintf(stderr, "malloc() error in CreateTree. "); return;

}

t->data = ch; //生成根结点

t->lchild = CreateTree(t->lchild); //构造左子树

t->rchild = CreateTree(t->rchild); //构造右子树 } return t;

}

热点内容

电脑编辑图片的app哪个好用发布：2025-04-02 18:26:17 浏览：768

下载东西解压包不见了发布：2025-04-02 18:10:33 浏览：27

excel表格怎么加密与只读发布：2025-04-02 18:04:41 浏览：160

空调压缩机与冷气泵发布：2025-04-02 18:03:11 浏览：738

对于程序员项目管理的分析发布：2025-04-02 17:58:09 浏览：705

80d说明书pdf 发布：2025-04-02 17:33:55 浏览：935

通信加密机制合同是发布：2025-04-02 17:28:18 浏览：490

先行服务器是什么鬼发布：2025-04-02 17:26:17 浏览：249

刷安卓系统需要什么手机发布：2025-04-02 17:25:55 浏览：274

数据图像加密发布：2025-04-02 17:23:17 浏览：924

Python写一个类实现栈发布：2025-04-02 17:20:14 浏览：102

ipad阅读器pdf 发布：2025-04-02 17:13:19 浏览：881

电钢琴pdf 发布：2025-04-02 16:57:59 浏览：592

安卓如何调和平画质发布：2025-04-02 16:53:50 浏览：222

为什么程序员不注意自己外在发布：2025-04-02 16:48:34 浏览：571

程序员那么可爱陆漓在哪里可以看发布：2025-04-02 16:35:39 浏览：703

移动数据加密如何解决发布：2025-04-02 16:35:34 浏览：98

tinyxml源码解析发布：2025-04-02 16:34:49 浏览：962

cad中如何加密发布：2025-04-02 16:34:47 浏览：345

linux终端光标移动发布：2025-04-02 16:28:12 浏览：88

导航:首页 > 源码编译 > 随机排号算法

随机排号算法

与随机排号算法相关的资料