データ構造アルゴリズム面接問題の精選と整理-二叉木

データ構造アルゴリズム面接問題の精選と整理
                                                                                                            by: Ju136
アルゴリズムとデータ構造も学んだことが多いかもしれませんが、ここでは主に古典的なコードとアルゴリズムを議論します.構想とコードを与えます.主にネット上や面接中によく聞かれる質問を集めて整理しています.能力が限られているので、指摘を歓迎します.
Note
本稿では、コードスタイルは「高品質C/C++プログラミング」で述べたコードスタイルとは異なるかもしれませんが、私の原則を話してもいいです.
一言一語の状況の処理.できるだけコードの量を小さくして、意味をもっと集中します.例:

node<T> *t = new node<T>(); t->data = value; t->left = t->right = NULL;

ここでは,変数を申請して初期化操作を行うことが明らかになった.次のように書くと

node<T> *t = new node<T>(); 
t->data = value; 
t->left =NULL;
t->right = NULL;

コード量が上がったような気がして、意味が集中しません.
一言で言えば,本稿のコードの目的は,意味を集中的に記述し,コード量を減らすことである.
木は最もよく聞かれる質問かもしれませんが、ここではまず最も基本的な知識を充復習します.
プログラムを作成する前に、以下のヘッダファイルを含めてください.G++を使ってC++の勉強をすることをお勧めします.もちろんVSもデバグをちゃんと手伝ってくれます.

#include<iostream>
#include<stack>
#include<queue>
#include<stdlib.h>
#include<string>
#include<string.h>
#include<stdio.h>
using namespace std;

ツリー接点
ここでは最も簡単なstructを採用し,データ構造を議論するだけでstructは十分であり,もちろんclassの形式に書くこともできるが,多くのコードを追加しなければならない.構造処理はもっと考えられているが,ここではこれ以上言わない.

template<typename T>
struct node
{
	T data;
	node *left;
	node *right;
};

ツリーの作成
まず、自分でコードを書くときは、テストのためにツリーを作成する必要があります.一般的には、手動でツリーを追加します.次に、二叉木を自動的に生成する方法を提供する.もちろん,主にランダム生成に基づく方法である.手動でツリーを生成する手間を軽減します.
次のコードでlevelは、作成したツリーのレイヤ数を表します.
生成された乱数に基づいてどのサブツリーが次にツリーを生成するかを決定する.このコードは、生成されたツリーがlevelレイヤを有することを保証します.

template<typename T>
node<T> *create(int level)
{
	if (!level) return NULL;

	node<T> *t = new node<T>();
	t->data = rand() % 10;   //        ，   rand  ，                  。
        t->left = t->right = NULL;
	if (1 == level) return t;

	int v = rand() % 3;
	switch(v)
	{
		case 0:
			t->left = create<T>(level - 1);
			t->right = create<T>(level - 1);
			break;
		case 1:
			t->left = create<T>(level - 1);
			break;
		case 2:
			t->right = create<T>(level - 1);
			break;
		default: break;
	}
	return t;
}

ここでも、ツリーの破棄が示されている.

template<typename T>
void free_tree(node<T> *t)
{
	if (!t) return;
	free_tree(t->left);
	free_tree(t->right);
	delete t;
}

実際には後順に破棄されています.
前序と中序を用いて二叉木を生成する方法を議論する前に,いくつかの基本的な遍歴を振り返ってみよう.
再帰遍歴
再帰的な遍歴は比較的簡単だと信じています.ここでは3つの遍歴の再帰方式を書きます.

template<typename T>
void front_order(const node<T> *t)
{
	if (!t) return;
	cout << t->data;
	front_order(t->left);
	front_order(t->right);
}

template<typename T>
void mid_order(node<T> *t)
{
	if (!t) return;
	mid_order(t->left);
	cout << t->data;
	mid_order(t->right);
}

template<typename T>
void back_order(node<T> *t)
{
	if (!t) return;
	back_order(t->left);
	back_order(t->right);
	cout << t->data;
}

非再帰的実装
では、どのように非再帰で実現しますか?
コードは次のとおりです.

template<typename T>
void front(node<T> *t)
{
	if (!t) return;
	stack<node<T> *> s;
	while (t || !s.empty())
	{
		while (t) { cout << t->data; s.push(t); t = t->left;}
		t = s.top(); s.pop(); t = t->right;
	}
}

template<typename T>
void mid(node<T> *t)
{
	if (!t) return;
	stack<node<T> *> s;
	while (t || !s.empty())
	{
		while (t) { s.push(t); t = t->left;}
		t = s.top(); s.pop(); 
		cout << t->data;
		t = t->right;
	}
}

template<typename T>
void back(node<T> *t)
{
	if (!t) return;
	stack<node<T> *> s;
	node<T> *pre = NULL;
	while (t || !s.empty())
	{
		while (t) { s.push(t); t = t->left;}
		t = s.top();
		if (t->right == NULL || pre == t->right)
		{
			cout << t->data;
			s.pop(); pre = t; t = NULL;
		}
		else t = t->right;
	}
}

言叶が多くて失败があって、できるだけこれらのコードをよく体得します.