随机排号算法_二叉树相关算法的实验验证 [ 实验目的] 验证二叉树的链接存储结构及其上的基本操作（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;

}

热点内容

没有考研的程序员发布：2025-04-08 20:19:27 浏览：822

程序员软考真题发布：2025-04-08 20:09:40 浏览：368

python用什么软件开发发布：2025-04-08 20:07:55 浏览：608

电脑文件夹封面怎么做发布：2025-04-08 20:01:00 浏览：208

谷轮压缩机8p 发布：2025-04-08 19:42:17 浏览：494

d7000pdf 发布：2025-04-08 19:35:36 浏览：926

scratch30编程真好玩发布：2025-04-08 19:26:07 浏览：874

android相机图标发布：2025-04-08 19:09:34 浏览：452

creative是相册什么文件夹发布：2025-04-08 19:08:03 浏览：214

韶关数据加密电话发布：2025-04-08 18:57:57 浏览：275

android应用开发范例精解pdf 发布：2025-04-08 18:56:58 浏览：317

can总线和单片机发布：2025-04-08 18:54:57 浏览：621

java随机一个数组发布：2025-04-08 18:54:50 浏览：609

如何把机器设置成服务器发布：2025-04-08 18:49:09 浏览：1000

编程与灵性冲突吗发布：2025-04-08 18:49:08 浏览：749

app上哪里可以找到身份证图发布：2025-04-08 18:48:06 浏览：874

进服务器需要什么发布：2025-04-08 18:47:27 浏览：672

苹果手机记事本加密发布：2025-04-08 18:47:16 浏览：565

什么叫t4服务器发布：2025-04-08 18:29:06 浏览：630

气胸压缩程度发布：2025-04-08 18:27:46 浏览：451

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

随机排号算法

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