树

标签： val nums mid left root first

二叉树

遍历
根据先序中序创建二叉树
根据中序后序创建二叉树
计算二叉树的深度

线索二叉树

遍历线索二叉树

赫夫曼树

二叉排序树

平衡二叉排序树

C++代码

#include<iostream>
using namespace std;
struct BiTree
{
	int val=0;
	BiTree* left;
	BiTree* right;
};

// 二叉树的先序遍历 先输出自己 再输出左孩子 再输出右孩子
void first_iter(BiTree* root) {
	if (root->val == 0)return;
	if( root->val!=0)
		cout << root->val << " ";
	if(root->left && root->left->val != 0)
		first_iter(root->left);
	if (root->right && root->right->val != 0)
		first_iter(root->right);

}
// 中序遍历 左 自己 右
void mid_iter(BiTree* root) {
	if (root->val == 0)return;
	if (root->left && root->left->val != 0)
		mid_iter(root->left);
	if(root->val)
		cout << root->val<<" ";
	if (root->right && root->right->val != 0)
		mid_iter(root->right);
}

void last_iter(BiTree* root) {
	if (root->val == 0)return;

	if (root->left && root->left->val!=0)
		last_iter(root->left);
	if (root->right && root->right->val != 0)
		last_iter(root->right);
	if (root->val)
		cout << root->val<<" ";
}

// 根据先序遍历和中序遍历结果获得一颗二叉树
BiTree* create_bitree_frome_first_mid( int first_nums[],int first_nums_start,int first_nums_end, int mid_nums[],int mid_nums_start,int mid_nums_end) {
	BiTree* temp=new BiTree();
	if (mid_nums_start == mid_nums_end) {
		temp->val = mid_nums[mid_nums_start];
		return temp;
	}
	else {
		for (int i = mid_nums_start; i <= mid_nums_end; i++) {
			if (mid_nums[i] == first_nums[first_nums_start]) {
				temp->val = mid_nums[i];
				// [mid_nums_start,i-1]左子树
				BiTree* left = create_bitree_frome_first_mid(first_nums, first_nums_start+1, first_nums_end - mid_nums_end-i, mid_nums, mid_nums_start, i-1);
				// [i+1,mid_nums_end]右子树
				BiTree* right = create_bitree_frome_first_mid(first_nums, first_nums_start + 1 + i- mid_nums_start, first_nums_end, mid_nums, i + 1, mid_nums_end);
				temp->left = left;
				temp->right = right;
				return temp;
			}
		}
	}
	return temp;
}

int main() {
	/*int first_nums[] = { 3,2,6,5,1,4 };
	int mid_nums[] = { 6,2,5,3,4,1 };*/
	//BiTree* root=create_bitree_frome_first_mid(first_nums,0,5,mid_nums,0,5);
	int first_nums[] = { 3,2,5,1,4,6,7 };
	int mid_nums[] = { 2,5,3,4,1,7,6 };
	BiTree* root = create_bitree_frome_first_mid(first_nums, 0, 6, mid_nums, 0, 6);
	cout << "----------first_iter----------" << endl;
	first_iter(root);
	cout << endl;


	cout << "----------mid_iter----------" << endl;
	mid_iter(root);
	cout << endl;

	cout << "----------last_iter----------" << endl;
	last_iter(root);
	cout << endl;


	cout << "finish" << endl;
}

标签：,val,nums,mid,left,root,first
From： https://www.cnblogs.com/code-fun/p/18144682