数据结构c二叉树的算法
发布网友
发布时间：2022-04-25 13:58
共2个回答
热心网友
时间：2022-04-26 18:54
额 我来讲讲吧：
第一个问题 你问应该用何种方式来存储，这个问题纠结了，什么叫应该用什么方式存储，当然是都可以啦两种方式~~不过你的意思可能是哪种方式最好，如果就是进行那两种操作的话，是顺序存储方式比较好（你应该知道顺序和链式两种吧）；其实二叉树是很少用顺序方式存储的。但是由于你已经说了你是完全二叉树，那么就可以考虑顺序方式存储了；书序二叉树每个节点你可以编号，直接运算序号就可以找到父节点和两个子节点了。
第二个问题 用C++写了 就采用链式结构吧 每个节点内有lchild rchild指针分别指向左右两孩子结点;结点类型就假定Node吧:
void exchange (Node * node){
exchange(node->lchild);
exchange(node->rchild)；
Node * n;
n=node->lchild;
node->lchild=node->rchild;
node->rchild=n;
}//递归方式实现的函数
exchange(bt);
非递归算法就需要借助队列了 代码较长 不想打了；队列就是实现按层次操作每个节点；操作玩的结点一次出队，出队的同时他们的孩子一次入队，最后没有结点入队出队就算法结束了；一般都是深度优先的递归算法来使用树形结构，很少有按层次结构非递归算法的，树形结构发明出来就是让你深度搜索用的
热心网友
时间：2022-04-26 20:12
我刚刚写的作业 呵呵
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#define OVERFLOW 0
//二叉树的二叉链表存储定义
struct Node
{
char data;
struct Node * lchild, * rchild;
};
typedef struct Node BiTNode;
typedef BiTNode * BiTree;
/*************************************************************************\
*
* 按先序次序输入二叉树中的结点的值（一个字符）构造二叉链表表示的二叉树，
* 字符'#'表示空树。
*
* 例如，一棵二叉树的三种遍历次序为：
* 先序：-+a*b-cd/ef 中序：a+b*c-d-e/f 后序：abcd-*+ef/
* 程序中应该输入：-+a##*b##-c##d##/e##f##
*
* 又如，一棵二叉树的三种遍历次序为：
* 先序：ABDFGCEH 中序：BFDGACHE 后序：FGDBHECA
* 程序中应该输入：AB#DF##G##C#EH###
*
\*************************************************************************/
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c", &ch); // * 按先序次序输入二叉树中的结点的值（一个字符）构造二叉链表表示的二叉树，
if (ch=='#') T=NULL; // * 字符'#'表示空树
else{
if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return;
}//CreateBiTree
void PreOrderTraverse(BiTree T)
{
//按先序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。
if (T)
{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return;
}//PreOrderTraverse
void InOrderTraverse(BiTree T)
{
//按中序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。
if (T)
{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
return;
}//InOrderTraverse
void PostOrderTraverse(BiTree T)
{
//按后序遍历次序输出二叉树T中的结点的值（一个字符），二叉树T用二叉链表存储。
if (T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
return;
}//PostOrderTraverse
void main()
{
BiTree T=NULL;
cout << "请按先序顺序输入二叉树中的结点（其中，'#'表示空树）：" <<endl;
CreateBiTree(T);
cout << endl;
cout << "先序遍历该二叉树得到的序列为：" <<endl;
PreOrderTraverse(T);
cout << endl <<endl;
cout << "中序遍历该二叉树得到的序列为：" <<endl;
InOrderTraverse(T);
cout << endl <<endl;
cout << "后序遍历该二叉树得到的序列为：" <<endl;
PostOrderTraverse(T);
cout << endl <<endl;
return;
}
