二叉树代码
代码语言：javascript复制#include <stdio.h>
#include <malloc.h>
#include <iostream>
#define MaxSize 100
using namespace std;
typedef int ElemType;
typedef struct node
{
ElemType data; //数据元素
struct node* lchild; //指向左孩子节点
struct node* rchild; //指向右孩子节点
} BTNode;
//二叉树本身有节点，是无形的树（因为链表节点结构）
//，创建以及输出二叉树，则是为了视觉效果 ，但反过来没有了创建，也不行
void CreateBTree(BTNode*& b, char* str) //创建二叉树
{
BTNode* St[MaxSize], * p = NULL;
int top = -1, k, j = 0;
char ch;
b = NULL; //建立的二叉树初始时为空
ch = str[j];
while (ch != ' ') //str未扫描完时循环
{
switch (ch)
{
case '(':top ; St[top] = p; k = 1; break; //为左孩子节点
case ')':top--; break;
case ',':k = 2; break; //为孩子节点右节点
default:p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch; p->lchild = p->rchild = NULL;
if (b == NULL) //*p为二叉树的根节点
b = p;
else //已建立二叉树根节点
{
switch (k)
{
case 1:St[top]->lchild = p; break;
case 2:St[top]->rchild = p; break;
}
}
}
j ;
ch = str[j];
}
}
void DestroyBTree(BTNode*& b)
{
if (b != NULL)
{
DestroyBTree(b->lchild);
DestroyBTree(b->rchild);
free(b);
}
}
//查找某个节点
BTNode* FindNode(BTNode* b, ElemType x)
{
BTNode* p;
if (b == NULL)
return NULL;
else if (b->data == x)
return b;
else
{
p = FindNode(b->lchild, x);
if (p != NULL)
return p;
else
return FindNode(b->rchild, x);
}
}
//返回某个节点的左节点
BTNode* LchildNode(BTNode* p)
{
return p->lchild;
}
//返回某个节点的右节点
BTNode* RchildNode(BTNode* p)
{
return p->rchild;
}
//返回树的高度
int BTHeight(BTNode* b)
{
int lchildh, rchildh;
if (b == NULL) return(0); //空树的高度为0
else
{
lchildh = BTHeight(b->lchild); //求左子树的高度为lchildh
rchildh = BTHeight(b->rchild); //求右子树的高度为rchildh
return (lchildh > rchildh) ? (lchildh 1) : (rchildh 1);
}
}
void DispBTree(BTNode* b)
{
if (b != NULL)
{
/*printf("%c", b->data);*/
cout << b->data;
if (b->lchild != NULL || b->rchild != NULL)
{
printf("("); //有孩子节点时才输出(
DispBTree(b->lchild); //递归处理左子树
if (b->rchild != NULL) printf(","); //有右孩子节点时才输出,
DispBTree(b->rchild); //递归处理右子树
printf(")"); //有孩子节点时才输出)
}
}
}
void PreOrder(BTNode* b) //先序遍历的递归算法
{
if (b != NULL)
{
//printf("%c ", b->data); //访问根结点
cout << b->data << " ";
PreOrder(b->lchild); //先序遍历左子树
PreOrder(b->rchild); //先序遍历右子树
}
}
void InOrder(BTNode* b) //中序遍历的递归算法
{
if (b != NULL)
{
InOrder(b->lchild); //中序遍历左子树
//printf("%c ", b->data); //访问根结点
cout << b->data << " ";
InOrder(b->rchild); //中序遍历右子树
}
}
void PostOrder(BTNode* b) //后序遍历的递归算法
{
if (b != NULL)
{
PostOrder(b->lchild); //后序遍历左子树
PostOrder(b->rchild); //后序遍历右子树
//printf("%c ", b->data); //访问根结点
cout << b->data << " ";
}
}
//--------------------------------------------------------
//--循环队列基本运算算法----------------------------------
//--------------------------------------------------------
typedef struct
{
BTNode* data[MaxSize]; //存放队中元素
int front, rear; //队头和队尾指针
} SqQueue; //顺序队类型
void InitQueue(SqQueue*& q) //初始化队列
{
q = (SqQueue*)malloc(sizeof(SqQueue));
q->front = q->rear = 0;
}
void DestroyQueue(SqQueue*& q) //销毁队列
{
free(q);
}
bool QueueEmpty(SqQueue* q) //判断队列是否为空
{
return(q->front == q->rear);
}
bool enQueue(SqQueue*& q, BTNode* e) //进队列
{
if ((q->rear 1) % MaxSize == q->front) //队满上溢出
return false;
q->rear = (q->rear 1) % MaxSize;
q->data[q->rear] = e;
return true;
}
bool deQueue(SqQueue*& q, BTNode*& e) //出队列
{
if (q->front == q->rear) //队空下溢出
return false;
q->front = (q->front 1) % MaxSize;
e = q->data[q->front];
return true;
}
//--------------------------------------------------------
//层次遍历输出二叉树
void LevelOrder(BTNode* b)
{
BTNode* p;
SqQueue* qu;
InitQueue(qu); //初始化队列
enQueue(qu, b); //根结点指针进入队列
while (!QueueEmpty(qu)) //队不为空循环
{
deQueue(qu, p); //出队节点p
printf("%c ", p->data); //访问节点p
if (p->lchild != NULL) //有左孩子时将其进队
enQueue(qu, p->lchild);
if (p->rchild != NULL) //有右孩子时将其进队
enQueue(qu, p->rchild);
}
}
/**
根据先序遍历和中序遍历求出二叉树
扩展知识：这里理解一下指针就是数组的：
int a[3] ={1,2,3};
int *b =a;
int *c =a 2;
cout<<a<<endl;//0x6ffe00
cout<<*b<<endl;//1
cout<<*c<<endl; //3
//指向指针的指针，和链表那样，d指针和b指针指向同一个地址
int *d = b;
cout<<d<<endl;//0x6ffdf0
cout<<*d<<endl;//1
//指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数，
int count =c-b;
cout<<count<<endl;
*/
BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length);
BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder);
BTNode* ConstructByPreAndIn(ElemType* preorder, ElemType* inorder, int length)
{
if (preorder == NULL || inorder == NULL || length <= 0)
{
return NULL;
}
return ConstructCoreByPreAndIn(preorder, preorder length - 1, inorder, inorder length - 1);
}
//startPreOrder表示PreOrder的起始地址，endPreOrder表示PreOrder的结束地址
BTNode* ConstructCoreByPreAndIn(ElemType* startPreOrder, ElemType* endPreOrder, ElemType* startInOrder, ElemType* endInOrder)
{
//rootVal表示跟节点数据
ElemType rootVal = *startPreOrder;//{ 1, 2, 4, 7, 3, 5, 6, 8 };
// 前序遍历的第一个数字为根节点
BTNode* root = new BTNode();
root->data = rootVal;
root->lchild = NULL;
root->rchild = NULL;
// 如果输入的只有一个数字,这里是把地址作比较！
if (startPreOrder == endPreOrder)
{
// 如果中序遍历也只有一个数字并且这两个数字相等
if (startInOrder == endInOrder && *startPreOrder == *startInOrder)
{
return root;
}
else
{
//throw exception("Invalid input");
cout << "Invalid Input" << endl;
return NULL;
}
}
// 在中序遍历中找到根节点位置
ElemType* rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && *rootInOrder != rootVal)
{
rootInOrder ;
}
if (rootInOrder > endInOrder || *rootInOrder != rootVal)
{
//throw exception("Invalid Input");
cout << "Invalid Input" << endl;
return NULL;
}
//{ 1, 2, 4, 7, 3, 5, 6, 8 };
//{ 4, 7, 2, 1, 5, 3, 8, 6 };rootInOrder 1
//lefyLength = 3 - 0;
//leftPreOrderEnd = 0 3;
//在中序遍历中找到根节点，根据中序遍历计算左子树长度
//
int leftLength = rootInOrder - startInOrder;
int* leftPreOrderEnd = startPreOrder leftLength;
//从广度思考去想，root=1的左右子树就是这两个（247）（3568）
//那么直接root->lchild和root->rchild给他们和下面main中这句
//BTNode* root = Construct(preOrder, inOrder, 8);
//是一样的，这点理解后，就只有一个目的，找出（247）（3568）！
//这就很简单了，后序遍历大同小异
if (leftLength > 0)
{
//2,4,7 || 4,7,2
root->lchild = ConstructCoreByPreAndIn(startPreOrder 1, leftPreOrderEnd, startInOrder, rootInOrder - 1);
}
if (leftLength < endPreOrder - startPreOrder)
{
//3,5,6,8 || 5,3,8,6
root->rchild = ConstructCoreByPreAndIn(leftPreOrderEnd 1, endPreOrder, rootInOrder 1, endInOrder);
}
return root;
}
/**
根据中序遍历和后序遍历求出二叉树
*/
BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length);
BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder);
BTNode* ConstructByPostAndIn(ElemType* postorder, ElemType* inorder, int length)
{
if (postorder == NULL || inorder == NULL || length <= 0)
{
return NULL;
}
return ConstructCoreByPostAndIn(postorder, postorder length - 1 , inorder, inorder length - 1);
}
BTNode* ConstructCoreByPostAndIn(ElemType* startPostOrder, ElemType* endPostOrder, ElemType* startInOrder, ElemType* endInOrder)
{
//rootVal表示跟节点数据
ElemType rootVal = *endPostOrder;//1
// 调试： cout << "k: "<< rootVal << endl;
// 后序遍历的最后一个数字为根节点
BTNode* root = new BTNode();
root->data = rootVal;
root->lchild = NULL;
root->rchild = NULL;
// 如果输入的只有一个数字
if (startPostOrder == endPostOrder)
{
// 如果中序遍历也只有一个数字并且这两个数字相等
if (startInOrder == endInOrder && *startPostOrder == *startInOrder)
{
return root;
}
else
{
cout << "Invalid Input" << endl;
return NULL;
}
}
// 在中序遍历中找到根节点位置
ElemType* rootInOrder = startInOrder;
while (rootInOrder <= endInOrder && *rootInOrder != rootVal)
{
rootInOrder ;
}
if (rootInOrder > endInOrder || *rootInOrder != rootVal)
{
cout << "xxxInvalid Input" << endl;
return NULL;
}
/**
*
endPostOrder会每次-1，当兵临到全部递归完跟节点的左子树时，endPostOrder再减去1就会越界了，
leftLength就是左子树的长度，在前序和中序遍历时，当其大于0遍历左子树，当其，小于，。。。
对于前序和中序遍历，逼近根节点的左子树时候，是start在逼近，end不动，一步步逼近
对于后续和中序遍历，逼近根节点的左子树时候，是start不动，end在逼近，
这就会出现一个不同的判断现象，start逼近，不会越界，临界值是0；end逼近，会越界，临界值指向-4123123213xxx
*/
//leftLength左子树的长度,leftPostOrderEnd后序遍历中左子树结束的地址
int leftLength = rootInOrder - startInOrder;//3
//int* leftPreOrderEnd = startPreOrder leftLength;
int* leftPostOrderEnd = startPostOrder leftLength ;//0 3
if (leftLength > 0)
{
//传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址）
root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1);
}
//rigthLength = end - start -leftLength
//rightLength > 0 等价于
//leftLength <end - start
if (leftLength < endPostOrder - startPostOrder)
{
//cout << *leftPostOrderEnd << *endPostOrder << *rootInOrder << *endInOrder << endl;
root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder 1, endInOrder);
}
return root;
}
int main()
{
BTNode* b;
CreateBTree(b, "A(B(D(,G)),C(E,F))");
printf("b:"); DispBTree(b); printf("n");
printf("先序遍历序列:"); PreOrder(b); printf("n");
printf("中序遍历序列:"); InOrder(b); printf("n");
printf("后序遍历序列:"); PostOrder(b); printf("n");
printf("层次遍历序列:"); LevelOrder(b); printf("n");
DestroyBTree(b);
//
ElemType preOrder[8] = { 1, 2, 4, 7, 3, 5, 6, 8 };
ElemType inOrder[8] = { 4, 7, 2, 1, 5, 3, 8, 6 };
ElemType postOrder[8] = { 7, 4, 2, 5, 8, 6, 3, 1 };
BTNode* root = ConstructByPreAndIn(preOrder, inOrder, 8);
DispBTree(root); cout << endl;
BTNode* root2 = ConstructByPostAndIn(postOrder, inOrder, 8);
DispBTree(root); cout << endl;
return 0;
}代码讲解
存储结构
代码语言：javascript复制typedef struct node
{
ElemType data; //数据元素
struct node* lchild; //指向左孩子节点
struct node* rchild; //指向右孩子节点
} BTNode;
typedef struct linknode{
int data;
struct linknode *next;
}sqstack;采用指针 结点来存储二叉树，链表栈也是如此， BTNode本身也是一个指针节点，可以指向和其一样结构的地址，所以，struct结构体中的结点也是struct结构体类型
根据中后序遍历求树思路
代码语言：javascript复制ElemType preOrder[7] = { 'A','B','D','G','C','E','F' };
ElemType inOrder[7] = { 'D','G','B','A','E','C','F' };
ElemType postOrder[7] = { 'G','D','B','E','F','C','A' };先观察后序遍历和中序遍历的数组分析一下，可以发现，后序遍历的最后一个值就是根节点，又可以从中序遍历中找出根节点，中序遍历的根节点前面都是左子树，根节点的后面都是右子树；这里所说的左右子树是相对于根节点A的。那么，现在我们得到的数据有，根节点A，根节点A左边的所有左子树x，根节点A右边的所有右子树y。对于x，y两棵树，就是和总树一样。又可以使用同样的方法去求根节点和左右子树。这就是递归方法了。 如何把求出的根节点存到结点表示的树中？在使用函数求出根节点A后，在使用函数递归调用，求出的A的左边的左子树的根节点，不就是根结点A的左结点吗？
代码语言：javascript复制//传入后序遍历中，左子树起始地址，左子树结束地址，中序遍历中起始地址，中子树中根节点-1的地址（即根节点中左子树结束地址）
root->lchild = ConstructCoreByPostAndIn(startPostOrder , leftPostOrderEnd - 1, startInOrder, rootInOrder - 1);root->rchild = ConstructCoreByPostAndIn(leftPostOrderEnd , endPostOrder - 1, rootInOrder 1, endInOrder);这个问题也解决了，最终函数会返回一个头结点root给我们，并且已经帮我们拼接好了root结点下面的所有结点。
指针与数组知识
代码语言：javascript复制 int a[3] ={1,2,3};
int *b =a;
int *c =a 2;
cout<<a<<endl;//0x6ffe00
cout<<*b<<endl;//1
cout<<*c<<endl; //3
//指向指针的指针，和链表那样，d指针和b指针指向同一个地址
int *d = b;
cout<<d<<endl;//0x6ffdf0
cout<<*d<<endl;//1
//指针和指针相减：只有当两个指针指向同一数组，才有意义，相减等于其他元素个数，
int count =c-b;
cout<<count<<endl;
// 重合指针相减为0
cout<<"d-b: "<<d-b<<endl;
cout<<"------------------------"<<endl;
char p[4] = {'a','b','c','d'};
char *q = p;
cout<<q<<endl;//abcd
cout<<q 2<<endl;//cd运行结果： 0x6ffdd0 1 3 0x6ffdd0 1 2 d-b: 0 ———————— abcd cd
废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：二叉树四种遍历，根据前中，后中遍历序列求二叉树
