二叉の木の幅と高さ
2036 ワード
策を練る 1.二叉樹の高さ 2.二叉木の幅 3.二つの二叉の木が等しいかどうかを比較する.
データ構造の定義
まず簡単な二叉樹を定義します.プレゼンテーションだけなので、簡単に定義されています.
データ構造の定義
まず簡単な二叉樹を定義します.プレゼンテーションだけなので、簡単に定義されています.
<span style="font-size:14px;"> #include <stdio.h>
#define MAX(x,y) ((x)>(y)?(x):(y))
//define a binary search tree
typedef struct BNode
{
int val;
struct BNode *left, *right;
}BNode,*BTree;</span>
val, MAX.
// insert a node to binary tree
// we assume that no duplicated elements
void BTreeInsert(BTree *bt, int val)
{
BNode *p = *bt,*cur = *bt;//p is a parent node of cur
while (cur != NULL)
{//find the position to insert node val
p = cur;</span>
if ( val < cur->val )</span>
cur = cur->left;
else
cur = cur->right;
}
BNode *n = malloc(sizeof(BNode));
n->val = val;
n->left = n->right = NULL;
if (p == NULL)
*bt = n;// the tree is empty
else
{
if (val < p->val)
p->left = n;
else
p->right = n;
}
}//BTreeInsert
BTreeInsert .</span>
二叉の木の高さの基本的な方法:二叉の木は、それぞれ左右のサブの高さを求めて、左右のツリーの高さの最大値を取って、もう1を加えると、二叉の木の高さです.この問題はまた二つの性質の同じサブ問題に分類されているので、再帰を招きやすいです. //get the depth of a BST 40 要点 BTree Depth(BTree bt)41 {42} if (bt!= NULL)43 {44 要点 dep left=BTreeDepth(bt->left);45 要点 depuright=BTreeDepth(bt->right);46 return MAX(depuleft,depuright)+1;47 } 48 return 0;49 }//BTreeDepth二叉の木の幅の基本的な方法:左右のツリーの幅を加算すると、二叉の木の幅が得られます. //get the width of a BST 67. 要点 BTree Width(BTree bt)68 {69} if (bt!= NULL)70 {71} if ((bt->left==bt->right)&((bt->left== NULL)72 return 1;//bt is a leaf 73. else 74 return BTree Width(bt->left)+BTree Width(bt->Right);75 } 76 else 77 return 0;78 }//BTree Width 79