バイナリ リンク リストはバイナリ ツリーの記憶構造ですか?

バイナリ リンク リストはバイナリ ツリーの記憶構造です。バイナリ リンク リストは、ツリーのバイナリ リンク リストの実装 (子兄弟表現) であり、ツリーの記憶構造としてバイナリ リンク リストを使用します。リンクされたリスト内のノードの 2 つのリンク フィールドは、それぞれ、ノードの最初の子ノードと 2 番目の子ノードを指します。

構造の説明 (推奨学習: Web フロントエンド ビデオ チュートリアル)

typedef　struct CSNode{
ElemType data；
struct CSNode *firstchild ， *netsibling；
} CSNode，* CSTree；

バイナリ ツリーのため ストレージ構造は比較的単純で処理が容易であるため、場合によっては、処理前に複雑なツリーを単純なバイナリ ツリーに変換する必要があります。

バイナリリンクリストの関数定義

bitree.h

//二叉链表定义
#include <iostream>
using namespace std;
typedef char TElemType;
struct BiTNode{
TElemType data;
BiTNode *lchild,*rchild;
};
typedef BiTNode *BiTree;
void initBiTree(BiTree &T);
void createBiTree(BiTree &T);
void preOrderTraverse(BiTree T,void (*visit)(TElemType)); //递归前序遍历
void preOrderTraverse1(BiTree T,void (*visit)(TElemType)); //非递归前序遍历
void inOrderTraverse(BiTree T,void (*visit)(TElemType)); //递归中序遍历
void postOrderTraverse(BiTree T,void (*visit)(TElemType)); //递归后序遍历
void levelOrderTraverse(BiTree T,void (*visit)(TElemType)); //层序遍历
bitree.cpp
#include "bitree.h"
void initBiTree(BiTree &T){ //构造空二叉树T
T=NULL;
}
void createBiTree(BiTree &T){
//按先序次序输入二叉树中结点的值（&#39;#&#39;表示空格），构造二叉链表表示的二叉树T。
TElemType ch;
cin>>ch;
if(ch==&#39;#&#39;) // 空
T=NULL;
else{
T=new BiTNode;
if(!T)
exit(1);
T->data=ch; // 生成根结点
createBiTree(T->lchild); // 构造左子树
createBiTree(T->rchild); // 构造右子树
}
}
void preOrderTraverse(BiTree T,void (*visit)(TElemType)){
// 先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T){ // T不空
visit(T->data); // 先访问根结点
preOrderTraverse(T->lchild,visit); // 再先序遍历左子树
preOrderTraverse(T->rchild,visit); // 最后先序遍历右子树
}
}
void preOrderTraverse1(BiTree T,void (*visit)(TElemType)){
//前序遍历二叉树T的非递归算法(利用栈)，对每个数据元素调用函数Visit
BiTree s[100];
int top=0; //top为栈顶指针
while((T!=NULL)||(top>0)){
while(T!=NULL){
visit(T->data);
s[top++]=T;
T=T->lchild;
}
T=s[--top];
T=T->rchild;
}
}
void inOrderTraverse(BiTree T,void (*visit)(TElemType)){
//中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T){
inOrderTraverse(T->lchild,visit); // 先中序遍历左子树
visit(T->data); // 再访问根结点
inOrderTraverse(T->rchild,visit); // 最后中序遍历右子树
}
}
void postOrderTraverse(BiTree T,void (*visit)(TElemType)){
//后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T){
inOrderTraverse(T->lchild,visit); // 后序遍历左子树
inOrderTraverse(T->rchild,visit); // 再后序遍历右子树
visit(T->data); // 最后访问根结点
}
}
void levelOrderTraverse(BiTree T,void (*visit)(TElemType)){
//层序遍历T(利用队列),对每个结点调用函数Visit一次且仅一次
BiTree q[100],p;
int f,r; // f,r类似于头尾指针
q[0]=T;
f=0;
r=1;
while(f<r){
p=q[f++]; //出队
visit(p->data);
if(p->lchild!=NULL)
q[r++]=p->lchild; //入队
if(p->rchild!=NULL)
q[r++]=p->rchild; //入队
}
}

以上がバイナリ リンク リストはバイナリ ツリーの記憶構造ですか?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。