855学习记录数据结构树(1)二叉树基础——炎泽汐$de$ Blog

文章目录[隐藏]

• 树
• 二叉树

引入

---

      树中的元素之间并不像顺序表和链表一样，存在天然的直接后继或直接前驱关系。不过只要附加某种约束（比如遍历），也可以在树中的元素之间确定某种线性次序，因此树属于半线性结构（semi-linear structure）。以下是一些易混淆的概念：

      分支结点：除叶结点外的其他结点，又称为非终端结点。

      树的度：树中结点的度的最大值。

      有序树：树中结点的各棵子树是有次序的

      无序树：树中结点的各棵子树之间的次序是不重要的,可以互相交换位置。

存储表示

---

      树的顺序存储是通过一维数组实现的，通过索引关系来确定子树，对于索引为$i$的节点来说，其关系可以表述为：如果$i=1$则结点$i$是二叉树的根，无双亲；其他情况下，其父节点为$i/2$，左子树为$2*i$,右子树为$2*i+1$，如果存在的话。树的顺序存储实现简单，操作方便，但是如果不是存储完全二叉树可能造成较大的空间浪费且树高受限。

      树的链式存储主要通过结构题来实现，以下是一个常用的结构：

struct TreeNode {
	int val;
	TreeNode *left;
	TreeNode *right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 	TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

      树的静态链表结合考虑了顺序存储和链式存储，能够充分利用数组的空间。

遍历

---

      前序的递归实现，其他两种改变输出位置即可：

void Front(TreeNode* root){
	if(root == nullptr){
		return;
	}
	if(!root -> left && !root -> right){
		cout << root -> val;
		return;
	}
	cout << root -> val;
	Front(root -> left);
	Front(root -> right);
}

      层序遍历通过队列来实现：

void Layer(TreeNode* root){
	queue<TreeNode*> q;
	q.push(root);
	while(!q.empty()){
		TreeNode* now = q.front();
		q.pop();
		cout << now -> val << '\t';
		if(!now -> left){
			q.push(now -> left);
		}
		if(!now -> right){
			q.push(now -> right);
		}
	}
}

前序和中序还原二叉树

---

map<int, int> idx;//建立先序数字到位置的映射 
TreeNode* build(vector<int>& p, int pl,int pr,int il,int ir){
    if(pl > pr){
        return NULL;
    }
    TreeNode* ans = new TreeNode(p[pl]);
    if(pl == pr){
        return ans;
    }
    int i = idx[p[pl]];
    ans -> left = build(p, pl + 1, pl + i - il, il, i - 1);
    ans -> right = build(p, i - il + pl + 1, pr, i + 1, ir);
    return ans;
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    int n = inorder.size();
    for(int i = 0; i < n;i++){
        idx[inorder[i]] = i;
    }
    return build(preorder, 0, n - 1, 0, n - 1);
}