本文目录一览：
- 1、C语言二叉树的二叉链表
- 2、算法 二叉树 单向链表\双向链表\循环链表
- 3、二叉树的基本操作 C语言版的
- 4、二叉链表表示二叉树，复制一颗二叉树，如何用C语言算法设计，希望答案正确且完整
- 5、设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换
- 6、将二叉树转换为双向链表
C语言二叉树的二叉链表
#include stdio.h
#include stdlib.h
#includemalloc.h
typedef struct node
{
char data;
struct node *lchild;
struct node *rchild;
}tnode;
tnode *createtree()
{
tnode *t;
char ch;
ch=getchar();
if(ch=='0')
t=NULL;
else
{
t=(tnode *)malloc(sizeof(tnode));
t-data=ch;
t-lchild=createtree();
t-rchild=createtree();
}
return t;
}
void listtree(tnode *t)
{
if (t!=NULL)
{
printf("%c",t-data);
if(t-lchild!=NULL||t-rchild!=NULL)
{
printf("(");
listtree(t-lchild);
if(t-rchild!=NULL)
printf(",");
listtree(t-rchild);
printf(")");
}
}
}
void inorder(tnode *t)
{
if(t!=NULL)
{
inorder(t-lchild);
printf("%c\t",t-data);
inorder(t-rchild);
}
}
void leve(tnode *t)
{
tnode *quee[100];
int front,rear;
front=-1;
rear=0;
quee[rear]=t;
while(front!=rear)
{
front++;
printf("%c\t",quee[front]-data);
if(quee[front]-lchild!=NULL)
{
rear++;
quee[rear]=quee[front]-lchild;
}
if(quee[front]-rchild!=NULL)
{
rear++;
quee[rear]=quee[front]-rchild;
}
}
}
main()
{
tnode *t=NULL;
printf("请输入二叉树元素：");
t=createtree();
printf("广义表的输出：");
listtree(t);
printf("\n");
printf("二叉树的中序遍历：");
inorder(t);
printf("\n");
printf("二叉树的层次遍历：");
leve(t);
printf("\n");
system("pause");
}
/*
输入：AB00CD00E00F000
输出：A(B,C((D,E))
中序遍历： B A D C E
层次遍历：A B C D E
*/
算法 二叉树 单向链表\双向链表\循环链表
数据结构的存储
数据结构的存储一般常
用的有两种 顺序存储结构 和 链式存储结构
2.1 顺序存储结构
发挥想象力啊。 举个列子。数组。1-2-3-4-5-6-7-8-9-10。这个就是一个顺序存储结构 ，存储是按顺序的 举 例说明啊。 栈。做开发的都熟悉。栈是先进后出 ，后进先出的形式 对不对 ?!他的你可以这样理解
hello world 在栈里面从栈底到栈顶的逻辑依次为 h-e-l-l-o-w-o-r-l-d 这就是顺序存储 再比如 队列 ，队列 是先进先出的对吧，从头到尾 h-e-l-l-o-w-o-r-l-d 就是这样排对的
2.2 链式存储结构
再次发挥想象力 这个稍微复杂一点 这个图片我一直弄好 ，回头找美工问问，再贴上 例如 还是一个数组
1-2-3-4-5-6-7-8-9-10 链式存储就不一样了 1(地址)-2(地址)-7(地址)-4(地址)-5(地址)-9(地址)-8(地址)-3(地 址)-6(地址)-10(地址)。每个数字后面跟着一个地址 而且存储形式不再是顺序 ，也就说顺序乱了，1(地址) 1 后面跟着的这个地址指向的是 2，2 后面的地址指向的是 3，3 后面的地址指向是谁你应该清楚了吧。他 执行的时候是 1(地址)-2(地址)-3(地址)-4(地址)-5(地址)-6(地址)-7(地址)-8(地址)-9(地址)-10(地址)，但是存储 的时候就是完全随机的。明白了?!
单向链表\双向链表\循环链表
还是举例子。理解最重要。不要去死记硬背 哪些什么。定义啊。逻辑啊。理解才是最重要滴
3.1 单向链表
A-B-C-D-E-F-G-H. 这就是单向链表 H 是头 A 是尾 像一个只有一个头的火车一样 只能一个头拉
着跑
3.2 双向链表
数组和链表区别:
数组:数组元素在内存上连续存放，可以通过下标查找元素;插入、删除需要移动大量元素，比较适用元
素很少变化的情况
链表:链表中的元素在内存中不是顺序存储的，查找慢，插入、删除只需要对元素指针重新赋值，效率高
3.3 循环链表
循环链表是与单向链表一样，是一种链式的存储结构，所不同的是，循环链表的最后一个结点的指针是指 向该循环链表的第一个结点或者表头结点，从而构成一个环形的链。发挥想象力 A-B-C-D-E-F-G-H-A. 绕成一个圈。就像蛇吃自己的这就是循环 不需要去死记硬背哪些理论知识。
4.1 什么是二叉树
树形结构下,两个节点以内 都称之为二叉树 不存在大于 2 的节点 分为左子树 右子树 有顺序 不能颠 倒 ，懵逼了吧，你肯定会想这是什么玩意，什么左子树右子树 ，都什么跟什么鬼? 现在我以普通话再讲 一遍，你把二叉树看成一个人 ，人的头呢就是树的根 ，左子树就是左手，右子树就是右手，左右手可以 都没有(残疾嘛，声明一下，绝非歧视残疾朋友，勿怪，勿怪就是举个例子，i am very sorry) , 左右 手呢可以有一个，就是不能颠倒。这样讲应该明白了吧
二叉树有五种表现形式
1.空的树(没有节点)可以理解为什么都没 像空气一样
2.只有根节点。 (理解一个人只有一个头 其他的什么都没，说的有点恐怖) 3.只有左子树 (一个头 一个左手 感觉越来越写不下去了)
4.只有右子树
5.左右子树都有
二叉树可以转换成森林 树也可以转换成二叉树。这里就不介绍了 你做项目绝对用不到 数据结构大致介绍这么多吧。理解为主, 别死记，死记没什么用
1、不用中间变量,用两种方法交换 A 和 B 的值
2、求最大公约数
3、模拟栈操作
栈是一种数据结构，特点:先进后出 -
练习:使用全局变量模拟栈的操作
//保护全局变量:在全局变量前加 static 后，这个全局变量就只能在本文件中使用 static int data[1024];//栈最多能保存 1024 个数据
static int count = 0;//目前已经放了多少个数(相当于栈顶位置)
4、排序算法
选择排序、冒泡排序、插入排序三种排序算法可以总结为如下:
都将数组分为已排序部分和未排序部分。
1.选择排序将已排序部分定义在左端，然后选择未排序部分的最小元素和未排序部分的第一个元素交换。 2.冒泡排序将已排序部分定义在右端，在遍历未排序部分的过程执行交换，将最大元素交换到最右端。 3.插入排序将已排序部分定义在左端，将未排序部分元的第一个元素插入到已排序部分合适的位置。 4.1、选择排序
【选择排序】:最值出现在起始端
第1趟:在n个数中找到最小(大)数与第一个数交换位置
第2趟:在剩下n-1个数中找到最小(大)数与第二个数交换位置 重复这样的操作...依次与第三个、第四个...数交换位置
第n-1趟，最终可实现数据的升序(降序)排列。
4.2、冒泡排序
【冒泡排序】:相邻元素两两比较，比较完一趟，最值出现在末尾
第1趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第n
个元素位置
第2趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第n-1
个元素位置
............
第n-1趟:依次比较相邻的两个数，不断交换(小数放前，大数放后)逐个推进，最值最后出现在第
2 个元素位置
5、折半查找(二分查找)
折半查找:优化查找时间(不用遍历全部数据)
折半查找的原理:
1 数组必须是有序的
2 必须已知 min 和 max(知道范围)
3 动态计算 mid 的值，取出 mid 对应的值进行比较
4 如果 mid 对应的值大于要查找的值，那么 max 要变小为 mid-1
5 如果 mid 对应的值小于要查找的值，那么 min 要变大为 mid+1
// 已知一个有序数组, 和一个 key, 要求从数组中找到 key 对应的索引位置
字符串反正
给定字符串 "hello,world",实现将其反转。输出结果:dlrow,olleh
序数组合并
将有序数组 {1,4,6,7,9} 和 {2,3,5,6,8,9,10,11,12} 合并为 {1,2,3,4,5,6,6,7,8,9,9,10,11,12}
HASH 算法
哈希表
例:给定值是字母 a，对应 ASCII 码值是 97，数组索引下标为 97。
这里的 ASCII 码，就算是一种哈希函数，存储和查找都通过该函数，有效地提高查找效率。
在一个字符串中找到第一个只出现一次的字符。如输入"abaccdeff"，输出'b'字符(char)是一个长度为8 的数据类型，因此总共有 256 种可能。每个字母根据其 ASCII 码值作为数组下标对应数组种的一个数 字。数组中存储的是每个字符出现的次数。
查找两个子视图的共同父视图 思路:分别记录两个子视图的所有父视图并保存到数组中，然后倒序寻找,直至找到第一个不一样的父视图。
定义一个链表
二叉树的基本操作 C语言版的
#include iostream.h
typedef struct BiTNode
{
char data;
int bit;
struct BiTNode *lchild,*rchild,*parent;
}BiTNode;
void InitBT(BiTNode *t)//1、初始化，不带头结点
{
t=NULL;
}
/*void InitBT(BiTNode *t)//初始化，带头结点
{
t=new BiTNode;
t-lchild=t-rchild=t-parent=NULL;
}*/
int EmptyBT(BiTNode *t)//判断队空
{
if(t==0)
return 1;
else
return 0;
}
BiTNode *creatBT(BiTNode *t,int b)//2、创建二叉树
{
BiTNode *p;
char ch;
cinch;
if(ch=='#')return 0;
else
{
p=new BiTNode;
p-data=ch;
p-parent=t;
p-bit=b;
t=p;
t-lchild=creatBT(t,0);
t-rchild=creatBT(t,1);
}
return t;
}
void preorder(BiTNode *t)//3、先序遍历
{
if(!EmptyBT(t))
{
coutt-data;
preorder(t-lchild);
preorder(t-rchild);
}
}
void inorder(BiTNode *t)//中序遍历
{
if(!EmptyBT(t))
{
inorder(t-lchild);
coutt-data;
inorder(t-rchild);
}
}
void postorder(BiTNode *t)//后序遍历
{
if(!EmptyBT(t))
{
postorder(t-lchild);
postorder(t-rchild);
coutt-data;
}
}
void coutBT(BiTNode *t,int m,int n,int i)//4、计算二叉树中叶子结点、度为2的结点和度为1的结点的个数
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
m++;//叶子结点
else if((t-lchild!=0) (t-rchild!=0))
i++;//度为2的结点
else
n++;//度为1的结点
coutBT(t-lchild,m,n,i);
coutBT(t-rchild,m,n,i);
}
}
void coutNode(BiTNode *t,int k)//5、求二叉树中结点个数
{
if(!EmptyBT(t))
{
k++;
coutNode(t-lchild,k);
coutNode(t-rchild,k);
}
}
int BTdepth(BiTNode *t)//6、求二叉树的深度
{
int i,j;
if(EmptyBT(t))
return 0;
else
{
i=BTdepth(t-lchild);
j=BTdepth(t-rchild);
return (ij?i:j)+1;
}
}
int Xdepth(BiTNode *t,char x)//7、查找x的层数
{
int num1,num2,n;
if(t==NULL)
return 0;
else{
if(t-data==x)
return 1;
num1=Xdepth(t-lchild,x);
num2=Xdepth(t-rchild,x);
n=num1+num2;
if(num1!=0||num2!=0)
n++;
return n;
}
}
static int flag;
void SearchChild(BiTNode *t,int k)//8、查找第k个结点的左右孩子
{
if(!EmptyBT(t))
{
if(k==0)
{
cout"位置不能为0!"endl;
return;
}
else
{
flag++;
if(flag==k)
{
if(t-lchild==0)
cout"无左孩子! ";
else
cout"左孩子为："(t-lchild-data)" ";
if(t-rchild==0)
cout"无右孩子!"endl;
else
cout"右孩子为："(t-rchild-data)endl;
}
else
{
SearchChild(t-lchild,k);
SearchChild(t-rchild,k);
}
}
}
}
int Xancestor(BiTNode *t,char x)//9、查找x结点祖先
{
int n,num1,num2;
if(t==NULL)
return 0;
else
{
if(t-data==x)
return 1;
num1=Xancestor(t-lchild,x);
num2=Xancestor(t-rchild,x);
n=num1+num2;
if(n!=0)
{
n++;
coutt-data" "endl;
}
}
}
void BTNodePath(BiTNode *t)//10、输出所有叶子结点路径
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
{
coutt-data"的路径为：";
for(BiTNode *p=t;p!=0;p=p-parent)
coutp-data;
coutendl;
}
else
{
BTNodePath(t-lchild);
BTNodePath(t-rchild);
}
}
}
void BTNodebit(BiTNode *t)//11、输出所有叶子结点编码
{
if(!EmptyBT(t))
{
if((t-lchild==0) (t-rchild==0))
{
coutt-data"的编码为：";
for(BiTNode *p=t;p-parent!=0;p=p-parent)
coutp-bit;
coutendl;
}
else
{
BTNodebit(t-lchild);
BTNodebit(t-rchild);
}
}
}
void main()
{
BiTNode *t;
int m,n,i,d,q,k;
char x;
cout"1、初始化..."endl;
InitBT(t);
cout"2、创建二叉树..."endl;
t=creatBT(t,0);
cout"3.1、先序遍历..."endl;
preorder(t);
coutendl;
cout"3.2、中序遍历..."endl;
inorder(t);
coutendl;
cout"3.3、后序遍历..."endl;
postorder(t);
coutendl;
m=n=i=0;
cout"4、计算叶子结点，度为1的结点和度为2的结点的个数..."endl;
coutBT(t,m,n,i);
cout"叶子结点个数为："mendl;
cout"度为1的结点个数为："nendl;
cout"度为2的结点个数为："iendl;
q=0;
cout"5、计算结点个数..."endl;
coutNode(t,q);
cout"结点个数为："qendl;
d=0;
cout"6、计算深度..."endl;
d=BTdepth(t);
cout"深度为："dendl;
cout"7、求x的层数..."endl;
cout"输入x：";
cinx;
if(Xdepth(t,x)==0)
cout"x不存在！"endl;
else
coutXdepth(t,x)endl;
cout"8、输入要查找孩子的结点在先序遍历中的位置k（不等于0）：";
cink;
SearchChild(t,k);
if(kflag)
cout"位置超出长度!"endl;
cout"9、查询结点的所有祖先，请输入结点x：";
cinx;
int num;
num=Xancestor(t,x);
if(num==0)
cout"结点不存在！"endl;
if(num==1)
cout"根结点无祖先！"endl;
cout"10、输出所有叶子结点路径（叶→根）："endl;
BTNodePath(t);
cout"11、输出所有叶子结点编码（叶→根）："endl;
BTNodebit(t);
}
二叉链表表示二叉树，复制一颗二叉树，如何用C语言算法设计，希望答案正确且完整
生成一个二叉树的结点
(其数据域为item,左指针域为lptr,右指针域为rptr)BiTNode *GetTreeNode(TElemType item,
BiTNode *lptr , BiTNode *rptr ){
if (!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(1);
T- data = item;
T- lchild = lptr; T- rchild = rptr;
return T;
}
BiTNode *CopyTree(BiTNode *T) {
if (!T ) return NULL;
if (T-lchild )
newlptr = CopyTree(T-lchild);//复制左子树
else newlptr = NULL;
if (T-rchild )
newrptr = CopyTree(T-rchild);//复制右子树
else newrptr = NULL;
newT = GetTreeNode(T-data, newlptr, newrptr);
return newT;
} // CopyTree
希望对你有所帮助，因为我也是这半学期刚学的，嘿嘿
设二叉树的存储结构为二叉链表，试写出算法（C函数）：将所有结点的左右子树互换
1、以二叉链表作存储结构，试编写前序、中序、后序及层次顺序遍历二叉树的算法。
#define M 10
typedef int DataType;/*元素的数据类型*/
typedef struct node
{ DataType data;
struct node *lchild,*rchild;
}BitTNode,*BiTree;
int front=0,rear=0;
BitTNode *que[10];
BitTNode *creat()
{BitTNode *t;
DataType x;
scanf("%d",x);
if(x==0) t=NULL;
else{ t=(BitTNode *)malloc(sizeof(BitTNode));
t-data=x;
t-lchild=creat();
t-rchild=creat();
}
return(t);
}/*creat*/
/* 前序遍历二叉树t */
void preorder(BiTree t)
{ if(t!=NULL)
{ printf("%4d",t-data);
preorder(t-lchild);
preorder(t-rchild);
}
}
/* 中序遍历二叉树t */
void inorder(BiTree t)
{ if(t!=NULL)
{ inorder(t-lchild);
printf("%4d",t-data);
inorder(t-rchild);
}
}
/* 后序遍历二叉树t */
void postorder(BiTree t)
{ if(t!=NULL)
{ postorder(t-lchild);
postorder(t-rchild);
printf("%4d",t-data);
}
}
void enqueue(BitTNode *t)
{if (front!=(rear+1)%M)
{ rear=(rear+1)%M;
que[rear]=t;
}
}/*enqueue*/
BitTNode * delqueue()
{ if(front==rear)return NULL;
{ front=(front+1)%M;
return (que[front]);
}
}/*delqueue*/
/* 按层次遍历二叉树t */
void levorder(BiTree t)
{ BitTNode *p;
if(t!=NULL)
{ enqueue(t);
while (front!=rear)
{ p=delqueue();
printf("%4d",p-data);
if(p-lchild!=NULL) enqueue(p-lchild);
if(p-rchild!=NULL) enqueue(p-rchild);
}
}
}/* levorder */
main()
{BitTNode *root;
root=creat();
printf("\n按先序遍历次序生成的二叉树");
printf("\n前序遍历二叉树");
preorder(root);
printf("\n中序遍历二叉树");
inorder(root);
printf("\n后序遍历二叉树");
postorder(root);
printf("\n层次顺序遍历二叉树");
levorder(root);
}
2、以二叉链表作存储结构，试编写计算二叉树深度、所有结点总数、叶子结点数、双孩子结点个数、单孩子结点个数的算法
#include stdio.h
#define MaxSize 100
typedef char ElemType;
typedef struct node
{
ElemType data;
struct node *left,*right;
} BTree;
BTree * createbt( )
{ BTree *q;
struct node1 *s[30];
int j,i,x;
printf("建立二叉树，输入结点对应的编号和值,编号和值之间用逗号隔开\n\n");
printf("i,x = ");
scanf("%d,%c",i,x);
while(i != 0 x != '$')
{ q = (BTree*)malloc(sizeof(BTree)); /*建立一个新结点q*/
q-data = x; q-left = NULL; q-right = NULL;
s[i] = q; /*q新结点地址存入s指针数组中*/
if(i != 1) /*i = 1，对应的结点是根结点*/
{ j = i / 2; /*求双亲结点的编号j*/
if(i % 2 == 0)
s[j]-left = q; /*q结点编号为偶数则挂在双亲结点j的左边*/
else
s[j]-right = q; /*q结点编号为奇数则挂在双亲结点j的右边*/
}
printf("i,x = ");
scanf("%d,%c",i,x);
}
return s[1]; /*返回根结点地址*/
}
void preorder(BTree *BT)
/* 前序遍历二叉树t */
{ if(BT!=NULL)
{ printf("%4c", BT -data);
preorder(BT -left);
preorder(BT -right);
}
}
int BTreeDepth(BTree *BT)
{
int leftdep,rightdep;
if (BT==NULL)
return(0);
else
{
leftdep=BTreeDepth(BT-left);
rightdep=BTreeDepth(BT-right);
if (leftdeprightdep)
return(leftdep+1);
else
return(rightdep+1);
}
}
int nodecount(BTree *BT)
{
if (BT==NULL)
return(0);
else
return(nodecount(BT-left)+nodecount(BT-right)+1);
}
int leafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-left==NULL BT-right==NULL)
return(1);
else
return(leafcount(BT-left)+leafcount(BT-right));
}
int notleafcount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-left==NULL BT-right==NULL)
return(0);
else
return(notleafcount(BT-left)+notleafcount(BT-right)+1);
}
int onesoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if ((BT-left==NULL BT-right!=NULL) ||
(BT-left!=NULL BT-right==NULL))
return(onesoncount(BT-left)+onesoncount(BT-right)+1);
else
return(onesoncount(BT-left)+onesoncount(BT-right));
}
int twosoncount(BTree *BT)
{
if (BT==NULL)
return(0);
else if (BT-left==NULL || BT-right==NULL)
return(twosoncount(BT-left)+twosoncount(BT-right));
else if (BT-left!=NULL BT-right!=NULL)
return(twosoncount(BT-left)+twosoncount(BT-right)+1);
}
main()
{
BTree *B;
B=creatree();
printf("\n按先序遍历次序生成的二叉树");
preorder(B);
printf("\n二叉树深度:%d\n",BTreeDepth(B));
printf("总结点个数:%d\n",nodecount(B));
printf("叶子结点个数:%d\n",leafcount(B));
printf("非叶子结点个数:%d\n",notleafcount(B));
printf("具有双孩子结点个数:%d\n",twosoncount(B));
printf("具有单孩子结点个数:%d\n",onesoncount(B));
}
如果还没解决你的问题，可以加我百度HI账号。
将二叉树转换为双向链表
创建一个二叉树，对这棵动态二叉树进行分析，将其用静态二叉链表表示。二叉树的动态二叉链表结构中的每个结点有三个字段：data，lchild，rchild。静态二叉链表是用数组作为存储空间，每个数组元素存储二叉树的一个结点，也有三个字段：data，lchild，rchild。lchild和rdhild分别用于存储左右孩子的下标。
