二叉木-経典問題復習
12814 ワード
ノード定義
typedef struct Btree {
int v;
struct Btree *left;
struct Btree *right;
}*Btree;ノードの挿入
Btree insertNode(Btree root, int value) {
Btree ptr=root;
Btree tmpNode;
Btree newNode = malloc(sizeof(Btree));
newNode->v = value;
newNode->left = NULL;
newNode->right = NULL;
if (ptr == NULL)
return newNode;
while (ptr != NULL) {
tmpNode = ptr;
if (ptr->v < value)
ptr = ptr->right;
else
ptr = ptr->left;
}
if (tmpNode->v < value)
tmpNode->right = newNode;
else
tmpNode->left = newNode;
return root;
}
ツリーの作成
Btree BtreeCreate(){
Btree root = NULL;
int value;
printf("Please insert nodes(end with zero) %d:
",&value);
while (value != 0){
root = insertNode(root,value);
scanf("%d",&value);
}
return root;
}ツリーのノードの数を求めます
再帰解法:(1)ツリーが空の場合、ノード数が0(2)ツリーが空でない場合、ツリーノード数=左サブツリーノード数+右サブツリーノード数+1
int getNodeNum(Btree root){
if (root == NULL)
return 0;
return getNodeNum(root->left)+getNodeNum(root->right)+1;
}ツリーの深さを求めます
再帰解法:(1)ツリーが空の場合、ツリーの深さが0(2)ツリーが空でない場合、ツリーの深さ=max(左サブツリーの深さ、右サブツリーの深さ)+1
int getDepth(Btree root){
if (root ==NULL)
return0;
int maxLeft = getDepth(root->left);
int maxRight = getDepth(root->right);
return maxLeft前シーケンス中シーケンス後シーケンス遍歴
ぜんじゅんかんかいほう
(1)ツリーが空の場合、空の操作(2)ツリーが空でない場合は、ルートノードにアクセスし、左サブツリーを先頭に、右サブツリーを先頭に移動
void preOrderTranverse(Btree root){
if (root == NULL)
return ;
visit(root);
preOrderTranverse(root->left);
preOrderTranverse(root->right);
}ちゅうかんじゅんかんかいほう
(1)二叉木が空の場合、空操作.(2)ツリーが空でない場合は、左サブツリーを中順に、ルートノードにアクセスし、右サブツリーを中順に
void inOrderTranverse(Btree root){
if (root == NULL)
return;
inOrderTranverse(root->left);
visit(root);
inOrderTranverse(root->right);
}アフタループ再帰解法
(1)ツリーが空の場合、空の操作(2)ツリーが空でない場合、左サブツリーを後に、右サブツリーを後に、ルートノードにアクセス
void postOrderTranverse(Btree root){
if (root == NULL)
return;
postOrderTranverse(root->left);
postOrderTranverse(root->right);
visit(root);
}階層はツリーを巡回します(階層によって左から上から下へ)
広さ優先探索に相当し,キューを用いて実現する.キューを初期化し、ルートノードをキューに押し込みます.キューが空でない場合は、ノードをポップアップし、アクセスし、左サブノードまたは右サブノードが空でない場合は、キューに押し込みます.
void levelTranverse(Btree root){
if (root == NULL)
return;
queue treeQueue;
treeQueue.push(root);
while(treeQueue.empty()!=0){
Btree tmp = treeQueue.front();
treeQueue.pop();
visit(tmp);
if (tmp->left!=NULL)
treeQueue.push(tmp->left);
if (tmp->right!=NULL)
treeQueue.push(tmp->right);
}
}
ツリーが整列した双方向チェーンテーブルになる
新しいノードを作成できず、ポインタのみを調整する必要があります.再帰解法:(1)ツリー検索ツリーが空の場合、変換する必要はありません.対応する双方向チェーンテーブルの最初のノードはNULLで、最後のノードはNULL(2)ツリー検索ツリーが空でない場合:
左サブツリーが空の場合、対応する双方向秩序チェーンテーブルの最初のノードはルートノードであり、左側には他の操作は必要ありません.
左サブツリーが空でない場合、左サブツリーを変換します.二叉ルックアップツリーに対応する双方向秩序チェーンテーブルの最初のノードは、左サブツリー変換後の双方向秩序チェーンテーブルの最初のノードです.ルートノードと左サブツリー変換後の双方向秩序チェーン
テーブルの最後のノード接続;
右サブツリーが空の場合、対応する双方向秩序チェーンテーブルの最後のノードがルートノードであり、右側には他の操作は必要ありません.
右サブツリーが空でない場合、対応する双方向秩序チェーンテーブルの最後のノードは、ルートノードと右サブツリー変換後の双方向秩序チェーンテーブルの最初のノードを接続しながら、右サブツリー変換後の双方向秩序チェーンテーブルの最後のノードです.
Btree BtreeToList(Btree root){
Btree head,tail;
BtreeToListRwcusion(root,head,tail);
return head;
}
void BtreeToListRecusion(Btree root, Btree head, Btree tail) {
if (root == NULL){
head = NULL;
tail = NULL;
return;
}
Btree lt,rt;
BtreeToList(root->left,head,lt);
BtreeToList(root->right,rt,tail);
if (root->left != NULL){
root->ledt = lt;
lt->right = root;
}
else
head = root;
if (root->right != NULL){
rt->left = root;
root->right = rt;
}
else
root = tail;
}ツリーの第K層のノードの数を求めます
再帰解法:(1)二叉木が空である場合またはk<1が0を返す(2)二叉木が空でなくk=1である場合、1を返す(3)二叉木が空でなくk>1である場合、左サブツリーにおけるk-1層のノード個数と右サブツリーk-1層のノード個数の和を返す
int getNodeNumKthLevel(Btree root, int k){
if (root == NULL)
return 0;
if (k == 1)
return 1;
int leftNum = getNodeNumKthLevel(root->left,k-1);
int rightNum = getNodeNumKthLevel(root->right,k-1);
return leftNum + rightNum;
}二叉木の葉の節点の個数を求めます
再帰解法:(1)二叉木が空であれば0を返す(2)二叉木が空でなく左右の子木が空であれば1を返す(3)二叉木が空でなく左右の子木が同時に空でなければ、左の子木に戻る葉ノードの数に右の子木における葉ノードの数を加える
int getAllLeafNodes(Btree root){
if (root == NULL)
return;
if (root->left == NULL && root->right == NULL){
return 1;
}
int leftNum = getAllLeafNodes(root->left);
int rightNum = getAllLeafNodes(root->right);
return leftNum + rightNum;
}
2本の二叉木が同じ構造かどうかを判断する
データの内容を考慮しない.同じ構造は、対応する左サブツリーと対応する右サブツリーが同じ構造であることを意味します.再帰解法:(1)2本の二叉木が空の場合、真に戻る(2)2本の二叉木が1本空の場合、もう1本が空でない場合、偽に戻る(3)2本の二叉木が空でない場合、対応する左の木と右の木が同じ構造で真に戻る場合、その他の偽に戻る
注意:Unixユーザーは以下のプログラムをコンパイルするにはヘッダファイルstdboolを追加する必要がある.h(C 99規格)
bool structIosmor(Btree rootFirst, Btree rootSecond){
if (rootFirst == NULL && rootSecond == NULL)
return true;
if (rootFirst == NULL || rootSecond == NULL)
return false;
bool first = structIosmor(rootFirst->left,rootSecond->left);
bool second = structIosmor(rootFirst->right,rootSecond->right);
return first&&second;
}ツリーがバランスツリーかどうかを判断する
再帰解法:(1)二叉木が空の場合、真を返す(2)二叉木が空でない場合、左サブツリーと右サブツリーがAVLツリーで、左サブツリーと右サブツリーの高さの差が1以下の場合、真を返す、その他の偽を返す
bool isAVL(Btree root, int height){
if (root == NULL){
height = 0;
return true;
}
int heightLeft;
bool resultLeft = isAVL(root->left,heightLeft);
int heightRight;
bool resultRight = isAVL(root->right,heightRight);
if (resultLeft && resultRight && abs(heightLeft-heightRight)<=1){
height = max(heightLeft,heightRight)+1;
return true;
}
else{
height = max(heightLeft,heightRight)+1;
return false;
}
}ツリーのミラーリング
再帰解法:(1)ツリーが空の場合は、空に戻ります(2)ツリーが空でない場合は、左サブツリーと右サブツリーのミラーを求め、左サブツリーと右サブツリーを交換します.
Btree treeImage(Btree root){
if (root == NULL)
return NULL;
Btree leftImage = treeImage(root->left);
Btree rightImage = treeImage(root->right);
root->left = rightImage;
root->right = leftImage;
return root;
}二叉木の中で2つのノードの最も低い共通の祖先のノードを求めます
再帰解法(効率が低すぎる):(1)2つのノードがそれぞれルートノードの左サブツリーと右サブツリーにある場合、ルートノードに戻る(2)2つのノードが左サブツリーにある場合、再帰は左サブツリーを処理する.両方のノードが右サブツリーにある場合は、右サブツリーを再帰的に処理します.
bool findNode(Btree root, Btree node){
if (root == NULL || node == NULL)
return false;
if (root == node)
return true;
bool found = findNode(root->left,node);
if(!found){
found = findNode(root->right,node);
}
return found;
}
Btree findLastParent(Btree root, Btree node1, Btree node2){
if (root == NULL || node1 == NULL || node2 == NULL){
return NULL;
}
if (findNode(root->left,node1)){
if (findNode(root->right,node2)){
return root;
}
else{
return findLastParent(root->left,node1,node2);
}
}
else{
if (findNode(root->left,node2))
return root;
else
return findLastParent(root->right,node1,node2);
}
}
非再帰解法:ルートノードから2つのノードへのパスを求めてから、対応するパスのノードを比較すればいいです.最後の同じノード、すなわち、ツリー内の最も低い共通の祖先ノードです.
bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode,
list & path)
{
if(pRoot == pNode)
{
path.push_back(pRoot);
return true;
}
if(pRoot == NULL)
return false;
path.push_back(pRoot);
bool found = false;
found = GetNodePath(pRoot->m_pLeft, pNode, path);
if(!found)
found = GetNodePath(pRoot->m_pRight, pNode, path);
if(!found)
path.pop_back();
return found;
}
BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)
{
if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
return NULL;
list path1;
bool bResult1 = GetNodePath(pRoot, pNode1, path1);
list path2;
bool bResult2 = GetNodePath(pRoot, pNode2, path2);
if(!bResult1 || !bResult2)
return NULL;
BinaryTreeNode * pLast = NULL;
list::const_iterator iter1 = path1.begin();
list::const_iterator iter2 = path2.begin();
while(iter1 != path1.end() && iter2 != path2.end())
{
if(*iter1 == *iter2)
pLast = *iter1;
else
break;
iter1++;
iter2++;
}
return pLast;
} ツリーノードの最大距離を求める
すなわち、ツリーの中で最も遠い2つのノード間の距離です.再帰解法:最も遠い2点は必ずあるノードAをルートとするサブツリー上にあり、それらの間の経路は必ずそのサブツリーのルートノードAを通過する.したがって、いずれかのノードBをルートとするサブツリーは、そのサブツリールートノードBを通過する最大距離を算出すると、全ての最大距離の最大値が所望の二叉木の最大距離、すなわち「ツリーの直径」となる.一方、ツリーを通るルートノードの最大距離は、左サブツリーの高さ+右サブツリーの高さ+2(空のノードの高さを-1と仮定)であるため、元の問題は「各ノードの左サブツリーと右サブツリーの高さの和を計算し、最大値をとる」ことに等しい.C言語では参照はサポートされていません.C++をサポートするコンパイラが必要です.
int treeDepth(Btree root,int& maxDistance){
if (root == NULL)
return -1;
int leftDepth = treeDepth(root->left,maxDistance) + 1;
int rightDepth = treeDepth(root->right,maxDistance) + 1;
int distance = leftDepth + rightDepth;
if (maxDistance < distance)
maxDistance = distance;
return max(leftDepth,rightDepth);
}
int findTreeDiameter(Btree root){
if (root == NULL)
return 0;
int maxDistance = 0;
treeDepth(root,maxDistance);
return maxDistance;
}前シーケンスループと中シーケンスループからツリーを再構築するには
ツリーの前順序ループシーケンスでは、最初の要素は常にツリーのルートノードの値です.中順遍歴シーケンスでは、左サブツリーのノードの値はルートノードの値の左側にあり、右サブツリーのノードの値はルートノードの値の右側にあります.再帰解法:(1)前シーケンスが空または中シーケンスで空またはノードの個数が0以下である場合、NULLを返します.(2)ルートノードを作成する.前順遍歴の最初のデータはルートノードのデータであり、中順遍歴でルートノードの位置を見つけ、左サブツリーと右サブツリーの前順と中順遍歴シーケンスをそれぞれ知り、左右のサブツリーを再構築することができる.
BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{
if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
return NULL;
BinaryTreeNode * pRoot = new BinaryTreeNode;
//
pRoot->m_nValue = pPreOrder[0];
pRoot->m_pLeft = NULL;
pRoot->m_pRight = NULL;
// ， ， ，
int rootPositionInOrder = -1;
for(int i = 0; i < nodeNum; i++)
if(pInOrder[i] == pRoot->m_nValue)
{
rootPositionInOrder = i;
break;
}
if(rootPositionInOrder == -1)
{
throw std::exception("Invalid input.");
}
//
int nodeNumLeft = rootPositionInOrder;
int * pPreOrderLeft = pPreOrder + 1;
int * pInOrderLeft = pInOrder;
pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
//
int nodeNumRight = nodeNum - nodeNumLeft - 1;
int * pPreOrderRight = pPreOrder + 1 + nodeNumLeft;
int * pInOrderRight = pInOrder + nodeNumLeft + 1;
pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
return pRoot;
}二叉木が完全に二叉木かどうかを判断する
二叉木の深さをhとすると、第h層を除いて、他の各層(1〜h−1)の結点数が最大個数に達し、第h層のすべての結点が連続して最左に集中し、これが完全二叉木である.階層(上から下、左から右)でツリーを巡り、ノードに遭遇した左サブツリーが空の場合、ノードの右サブツリーが空でなければなりません.また、後ろを通るノードの左右のサブツリーが空でなければなりません.そうしないと、完全なツリーではありません.
bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)
{
if(pRoot == NULL)
return false;
queue q;
q.push(pRoot);
bool mustHaveNoChild = false;
bool result = true;
while(!q.empty())
{
BinaryTreeNode * pNode = q.front();
q.pop();
if(mustHaveNoChild) // ， （ ）
{
if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)
{
result = false;
break;
}
}
else
{
if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)
{
q.push(pNode->m_pLeft);
q.push(pNode->m_pRight);
}
else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)
{
mustHaveNoChild = true;
q.push(pNode->m_pLeft);
}
else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)
{
result = false;
break;
}
else
{
mustHaveNoChild = true;
}
}
}
return result;
}