二叉树的创建用到了遍历算法，遍历有层次遍历和前中后序遍历，分别用到队列和栈工具。
1.二叉树定义：
#define _CRT_SECURE_NO_DEPRECATE//vs编译器
#include<stdio.h>
#include<stdlib.h>
#include<windows.h>
#define DataType char
#define BinType BinTree //栈和队列数据元素的类型,因为我们要将树结点的指针变量放入
const int MAXSIZE = 100;//栈和队列的最大容量
typedef struct BTNode{//二叉树结构体
DataType data;
struct BTNode *lchild, *rchild;
}BTNode, *BinTree;
void visit(BinTree p)//访问函数
{
printf("%c ",p->data);
}
2.栈的定义：
typedef struct//栈结构体
{
BinType elem[MAXSIZE];
int top;
}SqStack;
void InitStack(SqStack &s)//初始化栈
{
s.top = 0;
}
bool Push(SqStack &s, BinType x)//向栈中加入一个数据元素
{
if (s.top == MAXSIZE )//判满
return false;
else
{
s.elem[s.top++] = x;
return true;
}
}
bool Pop(SqStack &s, BinType &x)//从栈中输出一个数据元素（栈顶），并删除
{
if (s.top != 0)
{
x = s.elem[--s.top];
return true;
}
else //判空
{
printf("Underflow!\n");
return false;
}
}
bool StackEmpty(SqStack s)//判断是否为空栈
{
if (s.top == 0)
return true;
return false;
}
bool GetTop(SqStack s, BinType &x)//获取栈顶元素，不删除
{
if(s.top==0)
return false;x = s.elem[s.top - 1];
return true;
}
void OutStack(SqStack s)//输出栈中所有元素
{
int i;
if (s.top == 0)
printf("The stack is null");
for (i = s.top-1; i>=0; i--)
printf("%2d %6d\n", i, s.elem[i]);
}
3.队列的定义：
typedef struct//队列结构体
{
BinType elem[MAXSIZE];
int front, rear;
}SqQueue;
void InitQueue(SqQueue &q)//初始化循环队列
{
q.front = q.rear = 0;
}
bool Enqueue(SqQueue &q, BinType x)//队尾添加元素
{
if ((q.rear+1)%MAXSIZE == q.front)//满
return false;
q.elem[q.rear] = x;
q.rear = (q.rear + 1) % MAXSIZE;
return true;
}
bool Dequeue(SqQueue &q, BinType &x)//输出队头元素
{
if (q.front == q.rear)//空
return false;
x = q.elem[q.front];
q.front = (q.front + 1) % MAXSIZE;
return true;
}
bool QueueEmpty(SqQueue q)//判断是否为空队列
{
if (q.front == q.rear)
return true;
return false;
}
4.创建二叉树有层次、递归等创建方法(思想参照遍历方法)：
（1）如果二叉树是完全二叉树，则创建方法为：
void TreeCreat(BinTree &bt, int n)//层序方法建立完全二叉树，需要输入层序遍历序列
{
printf("请输入%d个数据\n", n);
int num = 0;//已经获取的数据数量
SqQueue Q;
bt = (BinTree)malloc(sizeof(BTNode));
bt->lchild = bt->rchild = NULL;
BinTree p;
InitQueue(Q);
Enqueue(Q, bt);
scanf("%c", &bt->data);
num++;
while (!QueueEmpty(Q))
{
Dequeue(Q, p);
if (num < n)
{
p->lchild = (BinTree)malloc(sizeof(BTNode));
p->lchild->lchild = p->lchild->rchild = NULL;
scanf("%c", &p->lchild->data);
num++;
Enqueue(Q, p->lchild);
}
if (num < n)
{
p->rchild = (BinTree)malloc(sizeof(BTNode));
p->rchild->lchild = p->rchild->rchild = NULL;
scanf("%c", &p->rchild->data);
num++;
Enqueue(Q, p->rchild);
}
}
}
（2）非完全二叉树层序遍历创建：
void TreeCreatLevel(BinTree &bt)//层序建立任意二叉树
{
DataType x;
scanf("%c", &x);
if (x == ' ')//空树
bt = NULL;
else
{
bt = (BinTree)malloc(sizeof(BTNode));
bt->data = x;
BinTree p;
SqQueue Q;
InitQueue(Q);
Enqueue(Q, bt);
while (!QueueEmpty(Q))
{
Dequeue(Q, p);
scanf("%c", &x);
if (x == ' ')
p->lchild = NULL;
else
{
p->lchild = (BinTree)malloc(sizeof(BTNode));
p->lchild->data = x;
Enqueue(Q, p->lchild);
}
scanf("%c", &x);
if (x == ' ')
p->rchild = NULL;
else
{
p->rchild = (BinTree)malloc(sizeof(BTNode));
p->rchild->data = x;
Enqueue(Q, p->rchild);
}
}
}
}
/* A
B E
C D F
*/
//这样一棵树输入序列为ABECD空F空空空空空空(空代表空格字符)
（3）非完全二叉树先序递归创建：
void CreatePre(BinTree &bt)//先序建立二叉树
{
char c;
scanf("%c", &c);
if (' ' == c)//空格字符代表NULL
{
bt = NULL;
}
else//不空则创建结点
{
bt = (BinTree)malloc(sizeof(BTNode));
bt->data = c;
CreatePre(bt->lchild);//递归左孩子
CreatePre(bt->rchild);//递归右孩子
}
}
/* A
B E
C D F
*/
//这样一棵树输入序列为ABC空空D空空E空F空空
5.二叉树遍历方法包括层序遍历、先序中序后序遍历，其中层序遍历用到队列工具，后三者分为递归和非递归，非递归用到栈工具。
（1）层序遍历：
void Levelorder(BinTree bt)//层次遍历
{
SqQueue Q;
BinTree p;
InitQueue(Q);
Enqueue(Q, bt);
while (!QueueEmpty(Q))
{
Dequeue(Q, p);
visit(p);
if (p->lchild)
Enqueue(Q,p->lchild);
if (p->rchild)
Enqueue(Q, p->rchild);
}
}
void Levelorder1(BinTree bt)//层次遍历如果未定义队列类型直接用队列
{
BinTree Q[MAXSIZE];
BinTree p;
int front =0,rear = 0;
Q[rear] = bt;
rear = (rear + 1) % MAXSIZE;
while (rear!=front)
{
p=Q[front];
front = (front + 1) % MAXSIZE;
visit(p);
if (p->lchild)
{
Q[rear] = p->lchild;
rear = (rear + 1) % MAXSIZE;
}
if (p->rchild)
{
Q[rear] = p->rchild;
rear = (rear + 1) % MAXSIZE;
}
}
}
（2）先序遍历
void Preorder(BinTree bt)//先序递归，然后可以递归输出时设置level层次，比如preorder （bt，level）
{
if (bt)
{
visit(bt);
Preorder(bt->lchild);
Preorder(bt->rchild);
}
}
void PreorderStack(BinTree bt)//先序非递归
{
SqStack S;//栈定义
InitStack(S);//栈初始化
BinTree p=bt;
while (p||!StackEmpty(S))//如果栈不空或者指针变量不空则循环
//因为p在下面的if语句中可能会找到当前根节点的最左后代的左孩子，也就是p可能会为空,而此时还没有遍历完；而当左半部分遍历完栈为空，但是还有右半部分，此时p不为空，所以两个条件都要有，只有p为空且栈空才是遍历完
{
if (p)//如果此结点不空，访问它并将其压栈，找到其左孩子
{
visit(p);
Push(S, p);//压栈
p = p->lchild;
}
else//如果此结点为空，那么一定是其祖先访问过了，则弹出其祖先，对这个已经访问过的祖先而言，其左边后代访问完了，找到右孩子进行访问
{
Pop(S, p);//弹栈
p = p->rchild;
}
}
}
void PreorderStack2(BinTree bt)//先序非递归，访问过的节点可以不用压栈，根据栈的规律，右孩子先进栈保证总是先访问左边的后代
{
SqStack S;
BinTree p;
InitStack(S);
Push(S,bt);
while (!StackEmpty(S))
{
Pop(S, p);
if (p)
{
visit(p);
Push(S, p->rchild);
Push(S, p->lchild);
}
}
}
（3）中序遍历：
void Inorder(BinTree bt)//中序递归
{
if (bt)
{
Inorder(bt->lchild);
visit(bt);
Inorder(bt->rchild);
}
}
void InorderStack(BinTree bt)//中序非递归
{
SqStack S;
InitStack(S);
BinTree p = bt;
while (p || !StackEmpty(S))
{
if (p)//遍历指针变量非空则压栈找到其左孩子，回来再访问
{
Push(S, p);
p = p->lchild;
}
else//此结点空，则弹栈访问
{
Pop(S, p);
visit(p);
p = p->rchild;
}
}
}
（4）后序遍历：
void Postorder(BinTree bt)//后序递归
{
if (bt)
{
Postorder(bt->lchild);
Postorder(bt->rchild);
visit(bt);
}
}
void PostorderStack(BinTree bt)//后序非递归
{
SqStack S;
InitStack(S);
BinTree p,pre;
p = bt;
pre = NULL;//设置变量记录上一个访问的结点指针
while (p || !StackEmpty(S))
{
if (p)//与中序遍历一样，根结点先压栈回来再访问
{
Push(S, p);
p = p->lchild;
}
else//只有栈顶的结点的右孩子为空或者右孩子已经访问过了，才会弹出此结点并访问
{
GetTop(S, p);//获取栈顶结点不弹出
if (p->rchild&&p->rchild != pre)//如果栈顶的右孩子存在且右孩子还没访问，别着急，往右分支走
p = p->rchild;
else//栈顶的结点的右孩子为空或者右孩子已经访问过了，才会弹出此结点并访问,终于到你啦
{
Pop(S, p);
visit(p);
pre = p;//别忘了记录访问的结点
p = NULL;//为的是让程序走while中第一层的else分支，因为现在左边的“撇”上的结点（根节点左孩子、左左孩子...）都处理了并且在栈中，应该来看右边或者弹栈了
}
}
}
}
void PostorderStack2(BinTree bt)//后序非递归双栈
{
BinTree S[MAXSIZE];
int tag[MAXSIZE] = {0};//用一个数栈（1或者2）来表示此结点是从左孩子还是从右孩子回来的，也就是右孩子是否访问过
int S_top = 0, t_top = 0;
BinTree p = bt;
while (p || (S_top!=0))
{
if (p)
{
S[S_top++]=p;
tag[t_top++] = 1;//设置表示右孩子未访问
p = p->lchild;
}
else
{
if (tag[t_top-1] == 1)//注意取值，top总是指向栈顶元素上一个位置
{
tag[t_top-1] = 2;//表示转到右孩子
p = S[S_top - 1]->rchild;
}
else//此结点的右孩子已经访问过，应该访问此结点了
{
p = S[--S_top]; //弹栈
t_top--; //弹栈
visit(p);
p = NULL;//使得程序while走else分支与第一种后序遍历一样
}
}
}
}
6.用先序+中序或者后序+中序序列来得到二叉树，每一个树段先序的开始和后序的结尾为根结点，根结点在中序位置将树分为左右两部分。
BinTree PreInCreat(DataType A[], DataType B[], int l1, int h1, int l2, int h2)//先序和中序建立树
{
BinTree root=(BinTree)malloc(sizeof(BTNode));
int i;
root->data = A[l1];
for (i = l2; B[i] != A[l1]; i++);//找到根节点在中序位置此时为i
int llen = i - l2;//关键就是确定左右分段树的长度
int rlen = h2 - i;
if (llen)
root->lchild = PreInCreat(A, B, l1 + 1, l1 + llen, l2, l2 + llen - 1);
else
root->lchild = NULL;
if (rlen)
root->rchild = PreInCreat(A, B, h1-rlen+1, h1,h2-rlen+1, h2);
else
root->rchild = NULL;
return root;
}
BinTree InPostCreat(DataType A[], DataType B[], int l1, int h1, int l2, int h2)//中序和后序建立树
{
BinTree root=(BinTree)malloc(sizeof(BTNode));
root->data = B[h2];
int i, llen, rlen;
for (i = 0; A[i] != B[h2]; i++);
llen = i - l1;
rlen = h1 - i;
if (llen)
root->lchild = InPostCreat(A, B, l1, l1 + llen - 1, l2, l2 + llen - 1);
else
root->lchild = NULL;
if (rlen)
root->rchild = InPostCreat(A, B, h1 - rlen + 1, h1, h2 - rlen, h2 - 1);
else
root->rchild = NULL;
return root;
}
7.计算树高度：
int TreeDeep(BinTree bt)
{
if (!bt)
return 0;
else
{
int ld = TreeDeep(bt->lchild);
int rd = TreeDeep(bt->rchild);
return 1+(ld>rd?ld:rd);//注意准确适用
}
}
int TreeDeepLevel(BinTree bt)
//非递归用层序遍历思想计算高度,一层刚刚处理完的同时，下一层放好了，当队首编号front与已经放好的那层最后结点编号一致则是遍历了一层
{
if (!bt)
return 0;
BinTree Q[MAXSIZE],p;
int front = 0, rear = 0,last=1,level=0;
Q[rear] = bt;
rear = (rear + 1) % MAXSIZE;
while (front != rear)//队列不空
{
p = Q[front++];//弹出队首元素
front = front%MAXSIZE;
if (p->lchild)
{
Q[rear++] = p->lchild;
rear = rear%MAXSIZE;
}
if (p->rchild)
{
Q[rear++] = p->rchild;
rear = rear%MAXSIZE;
}
if (front == last)
{
level++;
last = rear;//新一层的最后结点在队列中位置的后一个位置编号，因为rear存的是即将要放数据的位置编号
}
}
return level;
}
8.统计某类结点的数量(常用递归，这也是二叉树递归定义的特性)：
int TreeNodenum(BinTree bt)//递归统计所有结点数量
{
if (!bt)//结束条件
return 0;
else
return (TreeNodenum(bt->lchild) + TreeNodenum(bt->rchild)+1);//加的“1”是指本根结点
}
int TreeLeafnum(BinTree bt)//统计叶子结点数量
{
if (!bt)
return 0;
else if (!bt->lchild&&!bt->rchild)
return 1;
else
return(TreeLeafnum(bt->lchild) + TreeLeafnum(bt->rchild));
}
int TreeDoublenum(BinTree bt)//统计双分支节点数量
{
if (!bt)
return 0;
if (bt->lchild&&bt->rchild)
return 1 + TreeDoublenum(bt->lchild) + TreeDoublenum(bt->rchild);
else
return TreeDoublenum(bt->lchild) + TreeDoublenum(bt->rchild);
}
9.树的其他的一些应用函数，很多都用到了之前的算法思想。
bool TreeISComplete(BinTree bt)//判断是否为完全二叉树，用层序遍历思想，当遇到一个空的结点，看此结点后面是否有结点
{
if (!bt)
return true;
SqQueue Q;
BinTree p;
InitQueue(Q);
Enqueue(Q, bt);
while (!QueueEmpty(Q))//类似层序遍历
{
Dequeue(Q, p);
if (p)
{
Enqueue(Q, p->lchild);//不管p的左右孩子是否为空都加入，出队列再看是否为空
Enqueue(Q, p->rchild);
}
else
{
while (!QueueEmpty(Q))//检查此结点后面是否有结点
{
Dequeue(Q, p);
if (!p&&!QueueEmpty(Q))
return false;
}
}
}
return true;
}
bool TreeSearch(BinTree bt, DataType x, BinTree &p)//查找数据元素x，返回地址为p
{
if (bt)
{
if (bt->data == x)
{
p = bt;
return true;
}
else
{
if (TreeSearch(bt->lchild, x, p))//左边找到了
return true;
else//左边没找到找右边返回结果
return TreeSearch(bt->rchild,x, p);
}
}
return false;
}
BTNode * TreeCopy(BinTree bt)//复制二叉树，先序思想
{
BTNode* Newbt;
if (!bt)
return NULL;
Newbt = (BinTree)malloc(sizeof(BTNode));
Newbt->data = bt->data;
Newbt->lchild = TreeCopy(bt->lchild);
Newbt->rchild = TreeCopy(bt->rchild);
return Newbt;
}
void TreeDispNode(BinTree bt)//括号表示法
{
if (bt != NULL)
{
printf("%c", bt->data);
if (bt->lchild != NULL || bt->rchild != NULL)
{
printf("(");
TreeDispNode(bt->lchild);
if (bt->rchild != NULL)printf(",");
TreeDispNode(bt->rchild);
printf(")");
}
}
}
void TreeExchangeLR(BinTree bt)//交换左右树分支递归
{
if (!bt)
return;
BinTree p;
TreeExchangeLR(bt->lchild);
TreeExchangeLR(bt->rchild);
p = bt->lchild;
bt->lchild = bt->rchild;
bt->rchild = p;
}
void TreeSuojinPrint(BinTree bt,int indent)//二叉树缩进表示
{
if (!bt)
return;
for (int i = 0; i < indent; i++)
printf(" ");
printf("%c\n", bt->data);
TreeSuojinPrint(bt->lchild, indent + 3);
TreeSuojinPrint(bt->rchild, indent + 3);
}
void TreeVertPrint(BinTree bt, int indent)//二叉树旋转90度打印
{
if (!bt)
return;
TreeVertPrint(bt->rchild, indent + 3);
for (int i = 0; i < indent; i++)
printf(" ");
printf("%c\n", bt->data);
TreeVertPrint(bt->lchild, indent + 3);
}
void TreeSearchAncestors(BinTree bt, BinTree ptr)//利用后序遍历，找到ptr时栈中剩下的都是祖先
{
if (!bt || !ptr)
return;
BinTree p=bt, pre;
pre = NULL;
SqStack S;
InitStack(S);
Push(S, p);
p = p->lchild;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
p = p->lchild;
}
else
{
GetTop(S, p);
if (p->rchild&&p->rchild != pre)
p = p->rchild;
else
{
Pop(S, p);
pre = p;
if (p == ptr)
break;
p = NULL;//别忘了
}
}
}
while (!StackEmpty(S))
{
Pop(S, p);
printf("%c ", p->data);
}
}
bool IsOperator(char c)
{
if (c == '+' || c == '-' || c == '*' || c == '/')
return true;
return false;//return c == '+' || c == '-' || c == '*' || c == '/';
}
int CompareOperator(char a, char b)
{
return (a == '*' || a == '/' || b == '+' || b == '-') ? 1 : -1;
}
void PrintExpression(BinTree bt)//输出二叉树表示的表达式
{
if (!bt)
return;
if (!bt->lchild&&!bt->rchild)
printf("%c", bt->data);
else
{
bool ir = bt->lchild&&IsOperator(bt->lchild->data) && CompareOperator(bt->data, bt->lchild->data) > 0;
if (ir)
printf("(");
PrintExpression(bt->lchild);
if (ir)
printf(")");
printf("%c", bt->data);
ir = bt->rchild&&IsOperator(bt->rchild->data) && CompareOperator(bt->data, bt->rchild->data) > 0;
if (ir)
printf("(");
PrintExpression(bt->rchild);
if (ir)
printf(")");
}
}
void LeafALLpath(BinTree T, DataType s[], int pathlength)//输出所有叶子到根节点的路径以及路径长度
{
if (T)
{
if (!T->lchild&&!T->rchild)
{
printf("%c到根节点的路径长度为%d:\n%3c", T->data, pathlength + 1, T->data);
for (int i = pathlength - 1; i >= 0; i--)
printf("%3c", s[i]);
printf("\n");
}
else
{
s[pathlength++] = T->data;
LeafALLpath(T->lchild, s, pathlength);
LeafALLpath(T->rchild, s, pathlength);
}
}
}
10.测试代码：
int main()
{
BinTree mytree,P,myPandItree,myIandPtree;//直接树、自定义树、前中序树、中后树
DataType ElemArray[20];
DataType Elem;/*
char Prearray[] = "ABDEGCF", Inarray[] = "DBGEACF", Postarray[] = "DGEBFCA";//分别为前序和中序序列，用于构造树
char express[] = "-*/+cdeab";
printf("数组建立树\n");
printf("非完全二叉树建立树\n");
TreeCreatLevel(mytree);
/*TreeCreat(mytree,10);*///创建完全二叉树/*CreatPre(mytree);*/
printf("层次遍历队列\n");
Levelorder(mytree);
printf("\n层次遍历直接队列\n");
Levelorder1(mytree);
printf("\n前序递归\n");
Preorder(mytree);
printf("\n前序非递归1\n");
PreorderStack(mytree);
printf("\n前序非递归2\n");
PreorderStack2(mytree);
printf("\n中序递归\n");
Inorder(mytree);
printf("\n中序非递归\n");
InorderStack(mytree);
printf("\n后序递归\n");
Postorder(mytree);
printf("\n后序非递归\n");
PostorderStack(mytree);
printf("\n后序非递归双栈\n");
PostorderStack2(mytree);
printf("\n");
printf("树深度递归%d\n",TreeDeep(mytree));
printf("树深度非递归%d\n", TreeDeepLevel(mytree));
printf("树结点数%d\n", TreeNodenum(mytree));
printf("叶子结点数%d\n", TreeLeafnum(mytree));
printf("双分支结点数%d\n", TreeDoublenum(mytree));
printf("查找结果\n");
Elem = 'D';
if (TreeSearch(mytree,Elem,P))
printf("找到了%c,值为%c,输出指针值为%x\n",Elem,P->data,P);
else
printf("没有找到%c\n", Elem);
printf("复制树层次遍历结果\n");
P = TreeCopy(mytree);
Levelorder(P);
//Sleep(2000);
//system("cls");
printf("\n表达式建立并且中序遍历结果\n");
TreeCreat2(P, express, sizeof(express)-1);//由于字符串还有一个‘\0’
Inorder(P);
printf("\n输出表达式\n");
PrintExpression(P);
printf("\n括号表示法输出\n");
TreeDispNode(mytree);
printf("\n前序中序序列建立树层次遍历\n");
myPandItree = PreInCreat(Prearray,Inarray,0,sizeof(Prearray)-2,0,sizeof(Inarray)-2);
Levelorder1(myPandItree);
printf("\n判断是否为完全二叉树\n");
if (TreeISComplete(mytree))
printf("确实为完全二叉树\n");
else
printf("不是完全二叉树\n");
printf("\n中序后序序列建立树层次遍历\n");
myIandPtree = InPostCreat(Inarray, Postarray, 0, sizeof(Inarray)-2, 0, sizeof(Postarray)-2);
Levelorder1(myIandPtree);
printf("\n缩进打印\n");
TreeSuojinPrint(mytree,1);
printf("\n旋转90度打印\n");
TreeVertPrint(mytree, 1);
Elem = 'F';
printf("\n寻找%c的祖先\n",Elem);
TreeSearch(mytree, Elem, P);
TreeSearchAncestors(mytree,P);
printf("\n所有叶子到根节点的路径及长度\n", Elem);
LeafALLpath(mytree, ElemArray, 0);
/*printf("交换所有左右子树\n");
TreeExchangeLR(mytree);
printf("层次遍历队列\n");
Levelorder(mytree);
printf("\n前序递归\n");
Preorder(mytree);
printf("\n中序递归\n");
Inorder(mytree);*/
printf("\n");
system("pause");
return 0;
}