二叉树的基本操作

二叉树
先序和中序确定二叉树

后序以及中序确定二叉树

// 指针版本
struct node{
	typename data;
	node* lchild;
	node* rchild;
}
// 二叉树建树前根节点不存在，一般设为NULL
node* root = NULL;

// 生成一个新节点， v为结点权值
node* newNode(int v) {
	node* Node = new node;
	Node->data = v;
	Node->lchild = Node->rchild = NULL;
	return Node;
}

//二叉树的查找修改
void search(node* root, int x, int newdata) {
	if (root == NULL) return ;
	if (root->val == x) root->val = newdata;
	search(root->lchild, x, newdata);
	search(root->rchild, x, newdata);
}

//二叉树结点的插入位置就是数据域在二叉树中查找失败的位置
// 这里使用&, 在函数中直接修改root原变量
void insert(node* &root, int x) {
	if (root == NULL) {
		root = newNode(x);
		return ;
	}
	if (由二叉树的性质, x应插入在左子树) {
		insert(root->lchild, x);
	} else {
		insert(root->rchild, x);
	}
}

// 二叉树的创建
node* Create(int data[], int n) {
	node* root = NULL;
	for (int i = 0; i < n; i ++) {
		insert(root, data[i]);
	}
	return root;
}

// 二叉树的遍历

// 先序遍历
void preorder(node* root) {
	void preorder(node* root) {
		
	}
}
// 中序遍历（先遍历根在遍历左右子树，因此可以通过根节点在中序遍历的位置区分出左子树和右子树）
void inorder(node* root) {
	if (root == NULL) return ;
	inorder(root->lchild);
	printf("%d\n", root->val);
	inorder(root->rchild);

}
// 后序遍历（序列最后一个元素为根节点）
void postorder(node* root) {
	if (root == NULL) return ;
	postorder(root->lchild);
	postorder(root->rchild);
	printf("%d\n", root->val);
}
// 层序遍历
// 1.将根节点root入队
// 2.取出队首元素， 访问它。
// 如果该结点有左孩子， 将左孩子入队
// 如果该结点有右孩子， 将右孩子入队
// 返回2，直至队列为空
void LayerOrder(node* root) {
	queue<node*> q;
	q.push(root);
	while (!q.empty()) {
		node* now = q.front();
		q.pop();
		printf("%d ", now->val);
		if (now->lchild != NULL) q.push(now->lchild);
		if (now->rchild != NULL) q.push(now->rchild);
	}
}

// 根据先序和中序构建一个二叉树
node* createPreIn(int preL, int preR, int inL, int inR) {
	if (preL > preR) return NULL;
	node* root = new node;
	root->val = pre[preL];
	int k;
	for (k = inL; k <= inR; k ++) // 找到根节点在中序遍历的位置
		if (in[k] == pre[preL]) break;
	
	int numLeft = k - inL; // 左子树结点
	// 左子树的区间在先序遍历序列为[preLeft+1, preLeft+numLeft], 中序区间为[inL, k - 1]
	root->lchild = createPreIn(preL + 1, preL + numLeft, inL, k - 1);
	// 右子树的区间在先序遍历序列为[preL + numLeft + 1, preR], 中序区间为[k + 1, inR]
	root->rchild = createPreIn(preL + numLeft + 1, preL, k + 1, inR);

	return root;
}

// 根据后序和中序构建一个二叉树
node* createPostIn(int PostL, int PostR, int inL, int inR) {
	if (PostL > PostR) return NULL;
	node* root = new node;
	root->val = post[PostR];
	int k;
	for (k = inL; k <= inR; k ++)
		if (in[k] == posst[PostR]) break;
	int numLeft = k - inL;

	root->lchild = createPostIn(PostL, PostL + numLeft - 1, inL, k - 1);
	root->rchild = createPostIn(PostL + numLeft, PostR - 1, k + 1, inR);
}
// 数组版本
struct node {
	typename data;
	int lchild;
	int rchild;
} Node[N];

int index = 0;
int newNode(int v) {
	Node[index].data = v;
	Node[index].lchild = -1;
	Node[index].rchild = -1;
	return index ++;
}

void search(int root, int x, int newdata) {
	if (root = -1) return;
	if (Node[root].data == x) Node[root].data = newdata;
	search(Node[root].lchild, x, newdata);
	search(Node[root].rchild, x, newdata);
}

void insert(int &root, int x) {
	if (root == -1) {
		root = newNode(x);
		return ;
	}
	if (由于二叉树的性质x应该插在左子树)
		insert(Node[root].lchild, x);
	else
		insert(Node[root].rchild, x);
}

int Create(int data[], int n) {
	int root = 1;
	for (int i = 0;i < n; i ++)
		insert(root, data[i]);
	return root;
}

void preorder(int root) {
	if (root == -1) return ;
	printf("%d ", Node[root].data);
	preorder(Node[root].lchild);
	preorder(Node[root].rchild);
}

void inorder(int root) {
	if (root == -1) return ;
	inorder(Node[root].lchild);
	printf("%d ", Node[root].data);
	inorder(Node[root].rchild);
}

void postorder(int root) {
	if (root == -1) return ;
	
	preorder(Node[root].lchild);
	preorder(Node[root].rchild);
	printf("%d ", Node[root].data);
}

void LayerOrder(int root) {
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		printf("%d ", Node[now].data);
		if (Node[now].lchild != -1) q.push(Node[now].lchild);
		if (Node[now].rchild != -1) q.push(Node[now].rchild);
	}
}