14、数据结构

1）二叉树

1.常用操作

struct TreeNode{int data;TreeNode *leftChild;TreeNode *rightChild;
}; 
//前序遍历
void PreOrder(TreeNode *root){if(root == NULL) return;visit(root->data);PreOrder(root->leftChild);PreOrder(root->rightChild);return;
} 
//层序遍历 
void levelOrder(TreeNode *root){queue<TreeNode*> myQueue;if(root != NULL) myQueue.push(root);while(!myQueue.empty()){TreeNode *current = myQueue.front();myQueue.pop();visit(current->data);if(current->leftChild != NULL)myQueue.push(current->leftChild);if(current->rightChild != NULL)myQueue.push(current->rightChild);}
}

2.二叉树遍历（清华大学复试上机题）

题目描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一棵二叉树（以指针方式存储）。例如，先序遍历字符串 ABC##DE#G##F###，其中“#”表示空格，空格字符代表空树。建立这棵二叉树后，再对二叉树进行中序遍历，输出遍历结果。

#include <bits/stdc++.h>
using namespace std;struct TreeNode{char data;TreeNode *leftChild;TreeNode *rightChild;TreeNode(char c): data(c), leftChild(NULL), rightChild(NULL){}
}; TreeNode *Build(int &position, string str){char c = str[position++];if(c == '#') return NULL;TreeNode *root = new TreeNode(c);root->leftChild = Build(position,str);root->rightChild = Build(position, str);return root;
}void InOrder(TreeNode *root){if(root == NULL) return;InOrder(root->leftChild);cout<<root->data<<" ";InOrder(root->rightChild);return;
}int main(){string str;while(cin>>str){int position = 0;TreeNode *root = Build(position, str);InOrder(root);}cout<<endl;return 0; 
}

2）二叉排序树

1.二叉排序树（华中科技大学复试上机题）

题目描述：

二叉排序树也称二叉查找树。它可以是一棵空树，也可以是一棵具有如下特性的非空二叉树：1. 若左子树非空，则左子树上所有结点的关键字值均不大于根结点的关键字值。2. 若右子树非空，则右子树上所有结点的关键字值均不小于根结点的关键字值。3. 左、右子树本身也是一棵二叉排序树。 现在给你 N 个关键字值各不相同的结点，要求你按顺序将它们插入一个初始为空树的二叉排序树，每次插入成功后，求相应父结点的关键字值，若没有父结点，则输出-1。

#include <bits/stdc++.h>
using namespace std;struct TreeNode{int data;TreeNode *leftChild;TreeNode *rightChild;TreeNode(int x): data(x),leftChild(NULL),rightChild(NULL){}
};TreeNode *insert(TreeNode *root,int x,int father){if(root == NULL){root = new TreeNode(x);cout<<father<<endl;}else if(x < root->data){root->leftChild = insert(root->leftChild,x,root->data);}else{root->rightChild = insert(root->rightChild,x,root->data);}return root;
}int main(){int n;while(cin>>n){TreeNode *root = NULL;for(int i = 0;i < n;i++){int x;cin>>x;root = insert(root,x,-1);}}return 0; 
}

3）优先队列

1.常用操作

#include <bits/stdc++.h>
using namespace std;int main(){priority_queue<int> queue;cout<<queue.size()<<endl;queue.push(20);queue.push(100);queue.push(30);queue.push(50);cout&