二叉樹的建立和周遊

二叉樹的定義在此不再贅述：

https://baike.so.com/doc/4343861-4548914.html

二叉樹的建立

首先，要先聲明一個樹的結構，也就是樹的結構體，要有資料域data，左指針域Lchild，右指針域Rchild,在此給結構重新起名，結點為TNode,指向結點的指針為BiTree

參考代碼：

typedef struct TNode
{
    int data;
    struct TNode * Lchild;
    struct TNode * Rchild;
}TNode,*BiTree;
           

其次，我們就要建立幾個結點，并将它們連結起來，實際上還是指針的指向性問題，指針指向誰，就将誰的位址指派給指針，先初始化幾個結點指針pi[i=1-5],對位址初始化，并給它們的值域賦一定的值。

假設樹的結構

之後将它們按照這個連接配接起來

BiTree p1,p2,p3,p4,p5;
    p1 = (BiTree)malloc(sizeof(TNode));
    p2 = (BiTree)malloc(sizeof(TNode));
    p3 = (BiTree)malloc(sizeof(TNode));
    p4 = (BiTree)malloc(sizeof(TNode));
    p5 = (BiTree)malloc(sizeof(TNode));
    memset(p1,0,sizeof(TNode));
    memset(p2,0,sizeof(TNode));
    memset(p3,0,sizeof(TNode));
    memset(p4,0,sizeof(TNode));
    memset(p5,0,sizeof(TNode));
    p1->data = 1;
    p2->data = 2;
    p3->data = 3;
    p4->data = 4;
    p5->data = 5;
    p1->Lchild = p2;
    p1->Rchild = p3;
    p2->Lchild = p4;
    p3->Lchild = p5;
           

二叉樹的周遊：

周遊采用遞歸算法，假如是先序周遊，就是根，左子樹，右子樹(DLR)

代碼：

void preTraverseBiTree(BiTree &T)
{
    if(T)
    {
        cout<<T->data<<" ";
        preTraverseBiTree(T->Lchild);
        preTraverseBiTree(T->Rchild);
    }
}
           

中序和後序性質相同，隻是根節點的周遊順序不同，但是三種方法沒有差別

具體程式實作代碼和遞歸建立二叉樹和通路二叉樹代碼，歡迎提議

#include <iostream>
#include <cstdlib>
#include <cstring>
using namespace std;

typedef struct TNode
{
    int data;
    struct TNode * Lchild;
    struct TNode * Rchild;
}TNode,*BiTree;

void preTraverseBiTree(BiTree &T)
{
    if(T)
    {
        cout<<T->data<<" ";
        preTraverseBiTree(T->Lchild);
        preTraverseBiTree(T->Rchild);
    }
}
int main()
{   BiTree p1,p2,p3,p4,p5;
    p1 = (BiTree)malloc(sizeof(TNode));
    p2 = (BiTree)malloc(sizeof(TNode));
    p3 = (BiTree)malloc(sizeof(TNode));
    p4 = (BiTree)malloc(sizeof(TNode));
    p5 = (BiTree)malloc(sizeof(TNode));
    memset(p1,0,sizeof(TNode));
    memset(p2,0,sizeof(TNode));
    memset(p3,0,sizeof(TNode));
    memset(p4,0,sizeof(TNode));
    memset(p5,0,sizeof(TNode));
    p1->data = 1;
    p2->data = 2;
    p3->data = 3;
    p4->data = 4;
    p5->data = 5;
    p1->Lchild = p2;
    p1->Rchild = p3;
    p2->Lchild = p4;
    p3->Lchild = p5;
    cout<<"所建立二叉樹的先根周遊順序為:"<<endl;
    preTraverseBiTree(p1);
    system("pause");
}
           

#include <iostream>
using namespace std;

typedef struct node {
	struct node* lchild;//左指針域
	struct node* rchild;//右指針域
	char data;//資料域
} BiTreeNode,*BiTree;

//按照前序順序建立二叉樹
//根
//左子樹
//右子樹
void createBiTree(BiTree &T)//&是節點指針的引用
{
	char c;
	cin>>c;
	if(c == '#') { //遇到"#" 令樹的根節點為NULL
		T = NULL;//根
	} else {
		T = new BiTreeNode;
		T->data = c;
		createBiTree(T->lchild);
		createBiTree(T->rchild);
	}
}

//前序周遊二叉樹并列印二叉樹
//思想依然是遞歸
void PreTraverse(BiTree T)
{
	if(T) {
		cout<<T->data<<" ";
		PreTraverse(T->lchild);
		PreTraverse(T->rchild);
	}
}

//中序周遊并列印
//左子樹
//根
//右子樹
void midTraverse(BiTree T)
{
	if(T) {
		midTraverse(T->lchild);
		cout<<T->data<<" ";
		midTraverse(T->rchild);
	}
}

//後根周遊
//左子樹
//右子樹
//根節點

void postTraverse(BiTree T)
{
	if(T) {
		postTraverse(T->lchild);
		postTraverse(T->rchild);
		cout<<T->data<<" ";
	}
}

int main()
{
	BiTree T;               //聲明一個指向二叉樹根節點的指針
	createBiTree(T);
	cout<<"二叉樹建立完成！"<<endl;
	cout<<"前序周遊二叉樹："<<endl;
	PreTraverse(T);
	cout<<endl;
	cout<<"中序周遊二叉樹："<<endl;
	midTraverse(T);
	cout<<endl;
	cout<<"後序周遊二叉樹："<<endl;
	postTraverse(T);
	return 0;
}