두 갈래 나무의 순서 저장과 기본 조작

1, 두 갈래 나무의 정의:
두 갈래 나무는 n개의 결점의 유한한 집합으로 n=0일 때 빈 나무라고 부른다. 그렇지 않으면 (1) 나무라고 불리는 특수한 뿌리 결점이 있다.(2) n>1시 나머지 결점은 서로 교차하지 않는 두 개의 자집으로 나뉘어 좌우자수라고 하고 좌우자수는 모두 두 갈래나무이다.두 갈래 나무의 정의가 귀속되어 있음을 알 수 있다.
2. 두 갈래 나무의 성질:
(1) 비공 두 갈래 나무에 i층에서 많게는 2^(i-1)개의 결점이 있다.
(2) 깊이가 k인 두 갈래 나무는 최대 2^k-1개의 결점이 있다.
(3) 어떤 두 갈래 나무에 대해서도 잎결점수가 n0이고 도가 2인 노드수가 n2이면 n0=02+1;
만 두 갈래 나무: 1과 깊이가 k이고 2^k-1개의 결점이 있는 두 갈래 나무.
완전 두 갈래 나무: 만약에 깊이가 k라면 n개의 결점이 있는 두 갈래 나무, 그리고 그 모든 결점이 깊이가 k인 만 두 갈래 나무의 번호가 1부터 n까지의 결점과 일일이 대응하면 이 두 갈래 나무를 완전 두 갈래 나무라고 부른다.2^(k-1)<=n<=2^k-1
(4)n개의 결점의 완전한 두 갈래 나무의 깊이 k=[log2n]+1, 여기서 이 기호[x]는 x와 같은 정수보다 작음을 나타낸다.(증명 과정, 상술한 n에 대한 부등식 취대수)
(5) n개의 결점이 있는 완전 이차수(깊이 ε㏒2nε+1)의 결점을 층별(1층에서 ㏒2n+1층)순으로 왼쪽에서 오른쪽으로 번호를 매기면 번호가 i(1≤i≤n)인 결점에 대해:
1. 만약에 i=1: 결점 i는 두 갈래 나무의 뿌리로 양친 결점이 없다.그렇지 않으면 i>1이 되면 양친 결점 번호는 [i/2]이다.2. 만약에 2i>n: 결점 i는 잎결점으로 왼쪽 아이가 없다.그렇지 않으면 왼쪽 아이의 결점 번호는 2i이다.3. 만약에 2i+1>n: 결점 i는 오른쪽 아이가 없다.그렇지 않으면 오른쪽 아이의 결점 번호는 2i+1이다. 
3, 두 갈래 나무의 저장 구조
1. 순차적 스토리지 구조:

typedef char ElemType;
typedef struct stree
{
    ElemType bitTree[MAX_SIZE];
    int pointer;   //number of points
}STree;
//init
void STree_Init(STree &T)
{
    for(int i=0;i=MAX_SIZE || i<0)
    {
        cout<=MAX_SIZE || i<0)
    {
        cout<=MAX_SIZE || i<0)
    {
        cout<=MAX_SIZE || i<0)
    {
        cout<

2, 세 가지 반복 방식: 전순, 중순, 후순
역귀 형식의 역행 방식

// 
void STree_Traver_1(STree &T,int i)
{
        cout<

비귀속 형식의 역행 방식

// 
int STree_Traver_1_no(STree &T)
{
    stack s({'0'});
    int p=1,q;
    if(STree_empty(T))
    {
        cout< s;
    int p=1;
    int b=1;
    /*
    if(STree_empty(T))
    {
        cout<

두 갈래 나무의 순서 저장 구조와 귀환 역행 방식, 그리고 비귀환 역행 방식에 대해 위쪽은 모두 실현 코드를 제시했고 다음 편은 체인식 저장 구조와 귀환 방식의 코드를 제시했다.