数据结构---二叉树

最近在学二叉树，在这里整理一些相关的程序

前置定义

#define L -1
#define R 1
#define Size sizeof(TreeNode)
typedef struct TreeNode* ptr;
struct TreeNode {//树节点
	char data;
	TreeNode * lchild, *rchild;
};
ptr root;//根节点

首先是二叉树的建立

1.给出先序遍历遍历序列，建立二叉树并按照一定顺序遍历输出

Description

按先序遍历顺序输入二叉树的各个结点值，采用二叉链表的存储结构存储该二叉树，并按先序遍历输出二叉树的各结点的值及深度。

Input

按先序遍历顺序输入二叉树的各个结点值，#表示空节点。

Output

该二叉树的先序遍历序列,在每个节点后输出它在树中的深度。

Sample Input

ABD##E##C##

Sample Output

A(1)B(2)D(3)E(3)C(2)

这种二叉树已经按照先序遍历建立好了，只需要按照先序遍历的规则再去建立就好，遇到节点创建并纳入二叉树，再递归建立子树，

void createTree(ptr &p) {
	char ch;
	scanf("%c", &ch);
	if (ch == '#') {
		p = NULL;
		return;
	}
	p = (ptr)malloc(Size);//根左右的根
	p->data = ch;
	createTree(p->lchild);//建立左子树，对应根左右的左
	createTree(p->rchild);//建立右子树，对应根左右的右
}

对于遍历来说，按照根的位置可以分为三类，由于遍历规则是按照递归定义的，遍历实际上也可以按照递归来输出

void print(ptr p) {
	if (p==NULL)return;
	printf("%c(%d)", p->data);
	print(p->lchild);
	print(p->rchild);
}

全部代码

#include
#include
#include
#define L -1
#define R 1
#define Size sizeof(TreeNode)
typedef struct TreeNode* ptr;
int count = 0;
struct TreeNode {//树节点
	char data;
	TreeNode * lchild, *rchild,*parent;
};
TreeNode* root;
void createTree(ptr &p) {
	char ch;
	scanf("%c", &ch);
	if (ch == '#') {
		p = NULL;
		return;
	}
	p = (ptr)malloc(Size);//根左右的根
	p->data = ch;
	createTree(p->lchild);//建立左子树，对应根左右的左
	createTree(p->rchild);//建立右子树，对应根左右的右
}
void print(ptr p) {
	if (p==NULL)return;
	printf("%c(%d)", p->data);
	print(p->lchild);
	print(p->rchild);
}
int main()
{
	root = (ptr)malloc(Size);
	createTree(root);
	//先序遍历
	print(root);
	return 0;
}

2.输入已知遍历序列的两个序列（一般是中序和后序或先序，先序和后序似乎不能唯一确定），建立二叉树并遍历

Description

按先序顺序和中序顺序输入二叉树的2个遍历序列，采用二叉链表建立该二叉树并用后序遍历顺序输出该二叉树的后序遍历序列。

Input

输入数据有多组，对于每组测试数据
第一行输入二叉树的先序序列，第二行为中序序列。

Output

对于每组测试数据输出该二叉树的后序序列

Sample Input

abdcef dbaecf

Hint

dbefca

这里就以先序和中序为例，根左右和左根右的左右对应的子树中的序列顺序可能不一样，但是其数量是一样的，先序序列的第一个一定是根，那么我只要找到了根，再去中序中找到对应的相同的字母，那么根据左根右的原则，这时候就可以把中序的左右子树分出来，再根据中序找出来的位置mid计算出左右子树数量，根据根左右计算先序的左右子树位置，由于分出的子树继续建立其实跟原来的问题性质相同，所以是一个子问题，那么就可以采用递归继续向下计算

void createTree(char a[], int la, int ra, char b[], int lb, int rb, ptr &p) {
    //a为先序序列，b为中序,la,ra代表先序序列的的开始和结束位置,lb,rb代表中序的
	char ch = a[la];//根节点
	int mid = -1;
	for (int i = lb; i <= rb; i++){
		if (b[i] == ch) {
			mid = i;
			break;//找到中序的根节点退出
		}
	}
    //根的位置对应于中序是mid，左子树到mid-1,右子树开始于mid+1
    //这里如果可以找到那么可以计算出左子树的数量是mid-1-lb+1
    //可以据此推算先序的左子树结束位置右子树开始位置
	p = (ptr)malloc(Size);
	p->ch = a[la];//建立根节点
	if (mid > lb) //代表还有左子树
		createTree(a, la + 1, la+mid-lb, b, lb, mid - 1, p->lchild);//建立左子树
	else p->lchild = NULL;
	if (mid < rb)
		createTree(a, la + mid-lb+1, ra, b, mid + 1, rb, p->rchild);//建立右子树
	else p->rchild = NULL;
}

完整代码

#include
#include
#include
#include
using namespace std;
typedef struct TreeNode* ptr;
#define Size sizeof(TreeNode)
#define Max 10000
struct TreeNode {
	char ch;
	ptr lchild, rchild;
};

void createTree(char a[], int la, int ra, char b[], int lb, int rb, ptr &p) {
	//a为先序序列，b为中序, la, ra代表先序序列的的开始和结束位置, lb, rb代表中序的
	char ch = a[la];//根节点
	int mid = -1;
	for (int i = lb; i <= rb; i++) {
		if (b[i] == ch) {
			mid = i;
			break;//找到中序的根节点退出
		}
	}
	//根的位置对应于中序是mid，左子树到mid - 1, 右子树开始于mid + 1
	//这里如果可以找到那么可以计算出左子树的数量是mid - 1 - lb + 1
	//可以据此推算先序的左子树结束位置右子树开始位置
		p = (ptr)malloc(Size);
	p->ch = a[la];//建立根节点
	if (mid > lb) //代表还有左子树
		createTree(a, la + 1, la + mid - lb, b, lb, mid - 1, p->lchild);//建立左子树
	else p->lchild = NULL;
	if (mid < rb)
		createTree(a, la + mid - lb + 1, ra, b, mid + 1, rb, p->rchild);//建立右子树
	else p->rchild = NULL;
}

void print(ptr p) {
	if (!p)return;
	print(p->lchild);
	print(p->rchild);
	printf("%c", p->ch);
}


int main()
{
	char a[Max], b[Max];
	ptr root;//根节点
	while (~scanf("%s%s", a, b)) {
		int l = strlen(a);
		createTree(a, 0, l - 1, b, 0, l - 1, root);//建立二叉树
		print(root);
	}
	return 0;
}

3.一些其他的功能

计算叶子结点

下面的很多计算其实也是这样，根据二叉树的子树还是二叉树的原则，很多问题就转化为处理左子树再处理右子树，最后就完成了计算

就以计算叶子节点为例，只要计算出左子树的叶子，再计算出右子树的叶子，那么加起来就是整棵树的叶子数量

int countLeaf(ptr p) {
	if (!p)return 0;//啥也没有
	if (!p->lchild && !p->rchild)return 1;//代表叶子节点
	return countLeaf(p->lchild) + countLeaf(p->rchild);
}

计算节点数

int countNode(ptr p) {
	if (!p)return 0;
	return countNode(p->lchild) + countNode(p->rchild) + 1;
}

计算深度

不同的是深度要看最深的子树的深度

int calDeep(ptr p) {
	if (!p)return 0;//为空是0深度
	return max(calDeep(p->lchild), calDeep(p->rchild)) + 1;
}