이진 연결 목록은 이진 트리의 저장 구조입니까?

이진 연결 리스트는 이진 트리의 저장 구조입니다. 이진 연결 목록은 이진 연결 목록을 트리의 저장 구조로 사용하는 트리(자식 형제 표현)의 이진 연결 목록 구현입니다. 연결된 목록에 있는 노드의 두 링크 필드는 각각 노드의 첫 번째 자식 노드와 두 번째 자식 노드를 가리킵니다.

구조적 설명 (추천 학습: 웹 프론트엔드 동영상 튜토리얼)

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!