私の連絡先情報
郵便メール:
2024-07-12
한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina
木は非線形データ構造。n (n>=0) 個の限定されたノードで構成される階層関係のセットです。バンドル根が上を向き、葉が下を向いている、逆さまの木に見えることからツリーと呼ばれています。
- ルート ノード: ルート ノードには先行ノードがありません。
- ルート ノードを除いた残りのノードは、ツリーと同様の構造を持つサブツリーに分割されます。各サブツリーのルート ノードには 1 つのみの先行ノードがあり、0 個以上の後続ノードを持つことができます。
- したがって、その木は、再帰的定義の。
木構造は線形テーブルよりも複雑であり、それを保存したり表現したりするのが面倒です。値の範囲とノードとノード間の関係の両方を保存する必要があります。実際、木を表す方法は次のようにたくさんあります。親表記、子表記、子親表記、子兄弟表記待って。
次のストレージ構造を導入するプロセスでは、次のツリーを例として取り上げます。
ツリーのノードは一連の連続した空間に格納されていると仮定します。各ノードには、リンク リスト内の親ノードの位置を示すインジケーターが付けられます。 。言い換えれば、各ノードは、自分が誰であるかを知ることに加えて、その親がどこにいるかも知っています。
このうちデータは、ノードのデータ情報を格納するデータフィールドです。そして、parent は、配列内のノードの親の添字を格納するポインター フィールドです。
以下は、親表現のノード構造定義コードです。
/*树的双亲表示法结点结构定义*/
#define MAX_TREE_SIZE 100
typedef int TElemType; //树结点的数据类型，目前暂定为整型
/*结点结构*/
typedef struct TreeNode
{
TElemType data; //结点数据
int parent; //双亲位置
}TreeNode;
/*树结构*/
typedef struct
{
TreeNode nodes[MAX_TREE_SIZE]; //结点数组
int r, n; //根的位置和结点数
}PTree;
このようなストレージ構造を使用すると、使用されるノードの親ポインターに従って、その親ノードを簡単に見つけることができます。時間計算量は 0(1) です 、親が -1 (ツリー ノードのルートが見つかったことを示す) になるまで。ただし、ノードの子が何であるかを知りたい場合は、申し訳ありませんが、構造全体を調べてください。
先ほど、ツリーのストレージ構造を親の観点と子の観点から調べました。もちろん、ツリーのような階層構造の場合は、ツリー ノードの兄弟に着目するとどうなるでしょうか。観察した結果、どのツリーでも、そのノードの最初の子が存在する場合は一意であり、その右の兄弟も存在する場合は一意であることがわかりました。 したがって、ノードの最初の子とノードの右の兄弟を指す 2 つのポインターを設定します。
/*树的孩子兄弟表示法结构定义*/
typedef struct TreeNode
{
TElemtype data;
struct TreeNode *firstchild, *rightsib;
} TreeNode,* pTreeNode;
バイナリ ツリーは、次のような有限のノードのセットです。
- または空の
- これは、ルート ノードと 2 つのバイナリ ツリー (左サブツリーおよび右サブツリーとも呼ばれます) で構成されます。
上の写真からわかるように:
- 二分木には次数が 2 より大きいノードはありません
- 二分木の部分木は左と右の部分木に分割でき、順序を逆にすることはできないので、二分木は次のようになります。順序付けられた木
注: バイナリ ツリーは次の状況で構成されます。
バイナリ ツリーは通常、次の 2 つの構造を使用して保存できます。シーケンシャル構造、チェーン構造。
2. チェーンストレージ
通常のバイナリ ツリーは、無駄な領域が多くなる可能性があるため、配列での保存には適していません。そして完全なバイナリ ツリーは、シーケンシャル構造のストレージに適しています。 。実際、私たちは普段、ヒープ (バイナリ ツリー) は、連続した構造の配列を使用して格納します。ここでのヒープとオペレーティング システムの仮想プロセス アドレス空間のヒープは 2 つの異なるものであることに注意してください。1 つはデータ構造であり、もう 1 つはオペレーティング システムのメモリを管理する領域の分割です。
具体的な実装と応用については、以下を参照してください。[データ構造] 08. ヒープとヒープアプリケーション
バイナリ ツリー構造を学習する最も簡単な方法は、バイナリ ツリー構造をトラバースすることです。いわゆる二分木走査（Traversal）とは、二分木のノードに対して一定の規則に従って対応する操作を順番に実行することであり、各ノードの操作は一度だけ行われます。 。ノードにアクセスすることによって実行される操作は、特定のアプリケーションの問題によって異なります。 トラバーサルはバイナリ ツリー上で最も重要な操作の 1 つであり、バイナリ ツリー上の他の操作の基礎でもあります。
//根 左子树 右子树
void PrevOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
printf("%d ", root->val);
PrevOrder(root->left);
PrevOrder(root->right);
}
以下の図は再帰的なプロセスを示しています。
//左子树 根 右子树
void InOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
InOrder(root->left);
printf("%d ", root->val);
InOrder(root->right);
}
再帰的なプロセスは次のとおりです。
//左子树 右子树 根
void PostOrder(pTreeNode root)
{
if (root == NULL)
{
printf("NULL ");
return;
}
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->val);
}
再帰的なプロセスは次のとおりです。
レベル順序トラバーサル: 事前順序トラバーサル、順序内トラバーサル、および事後順序トラバーサルに加えて、レベル順序トラバーサルもバイナリ ツリーで実行できます。バイナリ ツリーのルート ノードのレベル番号が 1 であるとします。レベル順序のトラバーサルは、バイナリ ツリーのルート ノードから始まり、最初に最初のレベルのルート ノードを訪問し、次に 2 番目のレベルのノードを訪問します。左から右にレベル、次にレイヤーのノード、というように続きます。ツリーのノードを上から下、左から右にレイヤーごとに訪問するプロセスは、レイヤー順序のトラバーサルです。。
図：
ここでは、キューに介入してバイナリ ツリーの事前順序トラバーサルを実行します。
// 层序遍历
void LevelOrder(pTreeNode root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
printf("NULL ");
}
else
{
printf("%d ", front->val);
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
QueueDestory(&q);
}
バイナリ ツリーを作成および破棄するには、次を使用します。バイナリツリートラバーサル例えば。
//二叉树的创建
struct TreeNode* Creat(char* arr,int n,int* i)
{
if(*i<n&&arr[*i]=='#')
{
(*i)++;
return NULL;
}
TreeNode* newnode=(TreeNode*)malloc(sizeof(TreeNode));
newnode->left=NULL;
newnode->right=NULL;
newnode->val=arr[(*i)++];
newnode->left=Creat(arr,n,i);
newnode->right=Creat(arr,n,i);
return newnode;
}
//二叉树的销毁
void TreeDestroy(struct TreeNode* root)
{
if(root==NULL)
{
return;
}
TreeDestroy(root->left);
TreeDestroy(root->right);
free(root);
}
以下の操作はすべてトラバーサルの考え方に沿って実行されます。
// 二叉树节点个数
int TreeSize(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
return TreeSize(root->left) + TreeSize(root->right) + 1;
}
// 二叉树叶子节点个数
int TreeLeafSize(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
if (root->left == NULL && root->right == NULL)
{
return 1;
}
return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int TreeLevelKSize(pTreeNode root, int k)
{
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
pTreeNode TreeFind(pTreeNode root, TreeDataType x)
{
if (root == NULL)
{
return NULL;
}
//相等就返回
if (root->val == x)
return root;
//找左子树
pTreeNode left=TreeFind(root->left, x);
if (left)
{
return left;
}
//找右子树
pTreeNode right = TreeFind(root->right, x);
if (right)
{
return right;
}
//都没找到
return NULL;
}
//二叉树的高度
int TreeHeight(pTreeNode root)
{
if (root == NULL)
{
return 0;
}
int max_left = TreeHeight(root->left) ;
int max_right = TreeHeight(root->right);
return max_left > max_right ? max_left + 1 : max_right + 1;
}
//判断是否是完全二叉树
bool TreeComplete(pTreeNode root)
{
Queue q;
QueueInit(&q);
if (root)
{
QueuePush(&q, root);
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front == NULL)
{
break;
}
else
{
QueuePush(&q, front->left);
QueuePush(&q, front->right);
}
}
while (!QueueEmpty(&q))
{
pTreeNode front = QueueFront(&q);
QueuePop(&q);
if (front)
{
QueueDestory(&q);
return false;
}
}
QueueDestory(&q);
return true;
}
彼は 30 年以上テクノロジーの研究に専念しており、Java、linux、javascript、php、css などのさまざまな言語に堪能であり、オープンソース分野で多くの貢献を行っています。将来の参考のために技術開発におけるいくつかの問題を共有する開発者ドキュメント ステーション。
郵便メール: