C++面接準備の二叉木操作
11205 ワード
C++面接準備の二叉木操作
ツリーノード定義
ツリーの作成
ぜんじゅんかんループ
ちゅうかんじゅんかんループ
アフタループ
ぜんじゅんかんループ
ちゅうかんじゅんかんループ
後続ループ(再帰的ではなく、2つのスタックで)
アフタループ
ツリーノードの合計数
ツリーの深さ
ツリーの葉数
ツリーの幅
ツリーノード定義
struct BNode{
int data;
BNode* left;
BNode* right;
};
ツリーの作成
BNode* createNode() {
BNode* t;
int c;
cin >> c;
if(c == 0) {
t = NULL;
}else{
t = (BNode*)malloc(sizeof(BNode));
t->data = c;
t->left = createNode();
t->right = createNode();
}
return t;
}
ぜんじゅんかんループ
void preorder(BNode* root) {
if(root) {
cout << root->data << " ";
preorder(root->left);
preorder(root->right);
}
}
ちゅうかんじゅんかんループ
void inorder(BNode* root) {
if(root) {
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}
}
アフタループ
void postorder(BNode* root) {
if(root) {
postorder(root->left);
postorder(root->right);
cout << root->data << " ";
}
}
ぜんじゅんかんループ
void preorder2(BNode* root) {
stack s;
s.push(root);
while(!s.empty()){
BNode* cur = s.top();
s.pop();
if(cur) {
cout << cur->data << " ";
s.push(cur->right);
s.push(cur->left);
}
}
}
ちゅうかんじゅんかんループ
void inorder(BNode* root) {
stack s;
BNode* p = root;
while(!s.empty() || p != NULL) {
if(p == NULL) {
BNode* cur = s.top();
s.pop();
cout << cur->data << " ";
p = cur->right;
}else{
s.push(p);
p = p->left;
}
}
}
後続ループ(再帰的ではなく、2つのスタックで)
void postorder2(BNode* root) {
stack sta1;
stack sta2;
sta1.push(root);
while(!sta1.empty()) {
BNode* cur = sta1.top();
sta1.pop();
sta2.push(cur);
if(cur->left) sta1.push(cur->left);
if(cur->right) sta1.push(cur->right);
}
while(!sta2.empty()) {
BNode* tmp = sta2.top();
sta2.pop();
cout << tmp->data << " ";
}
}
アフタループ
void postorder2_1(BNode* root) {
stack<BNode*> s;
BNode* c = root;
s.push(root);
while(!s.empty()) {
BNode* cur = s.top();
if( (cur->left == NULL && cur->right == NULL) ||
(c != NULL && (c == cur->left || c == cur->right)) )
{
cout << cur->data << " ";
s.pop();
c = cur;
}
else{
if( cur->right != NULL )
s.push(cur->right);
if( cur->left != NULL)
s.push(cur->left);
}
}
}
ツリーノードの合計数
int NodeNum(BNode* root) {
if(root == NULL) {
return 0;
}else{
return 1 + NodeNum(root->left) + NodeNum(root->right);
}
}
ツリーの深さ
int depthTree(BNode* root) {
if(root == NULL) {
return 0;
}else{
return depthTree(root->left) > depthTree(root->right)?1+depthTree(root->left) : 1+depthTree(root->right);
}
}
ツリーの葉数
int leafNum(BNode* root) {
if(root == NULL) {
return 0;
}
else if(root->left == NULL && root->right == NULL) {
return 1;
}
else {
return (leafNum(root->left) + leafNum(root->right));
}
}
ツリーの幅
int treeWidth(BNode* root) {
if(root == NULL) return 0;
int nLastLevelWidth = 0;
int nCurLevelWidth = 0;
queue q;
q.push(root);
int nWidth = 1;
nLastLevelWidth = 1;
BNode* cur = NULL;
while(!q.empty()) {
while(nLastLevelWidth != 0) {
cur = q.front();
q.pop();
if(cur->left != NULL)
q.push(cur->left);
if(cur->right != NULL)
q.push(cur->right);
nLastLevelWidth--;
}
nCurLevelWidth = q.size();
nWidth = nCurLevelWidth > nWidth ? nCurLevelWidth : nWidth;
nLastLevelWidth = nCurLevelWidth;
}
return nWidth;
}