目錄

二叉樹的存儲結構

二叉樹結點的查找和修改

二叉樹結點的插入

二叉樹的創建

二叉樹的遍歷

先序遍歷

中序遍歷

后序遍歷

層序遍歷

重建二叉樹

二叉樹的靜態實現

二叉樹的存儲結構

一般來說，二叉樹使用鏈表來定義。和普通鏈表的區別是，由于二叉樹每個結點有兩條出邊，因此指針域變成了兩個---分別指向左子樹的根結點地址和右子樹根節點地址。如果某個子樹不存在，則指向NULL，其他地方和普通鏈表完全相同，因此又把這種鏈表叫做二叉鏈表，其定義如下：

struct node{typename data;node* lchild;node* rchild;
};

由于在二叉樹建樹前根節點不存在，因此其地址一般設為NULL。

node* root=NULL;

而如果需要新建結點（例如往二叉樹中插入結點的時候），就可以使用下面的函數：

//生成一個新結點，v為結點權值
node* newNode(int v){node* Node=new node;Node->data=v;Node->lchild=Node->right=NULL;return Node;
} 

二叉樹的常用操作有以下幾個：二叉樹的建立，二叉樹結點的查找、修改、插入與刪除，其中刪除操作對不同性質的二叉樹區別比較大，這里不做介紹。

二叉樹結點的查找和修改

查找操作是指在給定數據域的條件下，在二叉樹中找到所以數據域為給定數據域的結點，并將它們的數據域修改為給定的數據域。

需要使用遞歸來完成查找修改操作。在這里，遞歸式是指對當前結點的左子樹和右子樹分別進行遞歸，遞歸邊界是當前結點為空時到達死胡同。

void search(node* root,int x,int newdata){if(root==NULL){return;}if(root->data==x){root->data=newdata;}search(root->lchild,x,newdata);search(root->rchild,x,newdata);
}

二叉樹結點的插入

二叉樹結點的插入位置就是數據域在二叉樹中查找失敗的位置。而由于這個位置是確定的，因此在遞歸查找的過程中一定是只根據二叉樹的性質來選擇左子樹或右子樹中的一棵子樹進行遞歸，且最后到達空樹的地方就是查找失敗的地方。

void insert(node* &root,int x){if(root==NULL){root=newNode(x);return;}if(由二叉樹的性質，x應該插在左子樹){insert(root->lchild,x);}else{insert(root->rchild);}
}

二叉樹的創建

二叉樹的創建其實就是二叉樹結點的插入過程，而插入所需要結點的數據域一般都會由題目給出，因此比較常用的寫法是把需要插入的數據存儲在數組中，然后再將它們使用insert函數一個個插入二叉樹中，并最終返回根節點的指針root。

node* Create(int data[],int n){node* root=NULL;for(int i=0;i<n;i++){insert(root,data[i]);}return root;
}

二叉樹的遍歷

先序遍歷

void preorder(node* root){if(root==NULL){return;}printf("%d\n",root->data);preorder(root->lchild);preorder(root->rchild);
}

中序遍歷

void inorder(node* root){if(root==NULL){return;}inorder(root->lchild);printf("%d\n",root->data);inorder(root->rchild);
}

后序遍歷

void postorder(node* root){if(root==NULL){return;}postorder(root->lchild);postorder(root->rchild);printf("%d\n",root->data);
}

層序遍歷

void layerorder(node* root){queue<node*> q;//注意隊列里存地址 q.push(root);while(!q.empty()){node* now=q.front;q.pop();printf("%d",now->data);if(now->lchild!=NULL){q.push(now->lchild);}if(now->rchild!=NULL){q.push(now->rchild);}}
}

在這里使用node*型變量，這樣就可以通過訪問地址去修改原元素，如果使用node型，隊列中保存的只是元素的一個副本，因此如果隊列中直接存放node型，當需要修改隊首元素時，就無法修改

另外還需要指出，如果題目中要求計算出每個結點所處的層次，這時就需要在二叉樹結點的定義中添加一個記錄層次layer的變量：

struct node{int data;int layer;node* lchild;node* rchild;
};

需要在根節點入隊前就先令根節點的layer為1來表示根節點在第一層，之后在now->lchild和now->rchild入隊前，把它們的層號都記為當前結點now的層號加1

void Layerorder(node* root){queue<node*> q;root->layer=1;q.push(root);while(!q.empty()){node* now=q.front();q.pop();printf("%d ",now->data);if(now->lchild!=NULL){now->lchild->layer=now->layer+1;q.push(now->lchild);}if(now->rchild!=NULL){now->rchild->layer=now->layer+1;q.push(now->rchild);}}
}

重建二叉樹

給定一棵二叉樹的先序遍歷序列和中序遍歷序列，重建這棵二叉樹。

根據二叉樹遍歷的性質，先序遍歷的第一個結點為二叉樹的根節點，中序遍歷的序列可以根據二叉樹的根節點將中序遍歷序列劃分為左子樹和右子樹。因此只需要在中序遍歷序列中找到根節點的位置，然后劃分為兩個子樹，然后再兩個子樹中分別遞歸執行上面的操作。

node* create(int prel,int prer,int inl,int inr){if(prel>prer){return NULL;}node* root=new node;root->data=pre[prel];int k;for(k=inl;k<=inr;k++){if(in[k]==pre[prel]){break;}}int numleft=k-inl;root->lchild=create(prel+1,prel+numleft,inl,k-1);root->rchild=create(prel+numleft+1,prer,k+1,inr);return root;
}

另外如果給定了后序序列和中序序列也可以構建一棵二叉樹，做法是一樣的。

例題：給出一棵樹的后序遍歷序列和中序遍歷序列，求這棵二叉樹的層次遍歷序列。

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn = 50;
struct node{int data;node* lchild;node* rchild;
};
int pre[maxn],in[maxn],post[maxn];
int n;
node* create(int postl,int postr,int inl,int inr){if(postl>postr){return NULL;}node* root=new node;root->data=post[postr];int k;for(k=inl;k<=inr;k++){if(in[k]==post[postr]){break;}}int numleft=k-inl;root->lchild=create(postl,postl+numleft-1,inl,k-1);root->rchild=create(postl+numleft,postr-1,k+1,inr);return root;
}
int num=0;
void bfs(node* root){queue<node*> q;q.push(root);while(!q.empty()){node* now=q.front();q.pop();printf("%d",now->data);num++;if(num<n){printf(" ");}if(now->lchild!=NULL){q.push(now->lchild);}if(now->rchild!=NULL){q.push(now->rchild);}}
}
int main(){scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d",&post[i]);}for(int i=0;i<n;i++){scanf("%d",&in[i]);}node* root=create(0,n-1,0,n-1);bfs(root);return 0;
}

二叉樹的靜態實現

可以使用數組來實現上面的操作，采用靜態二叉鏈表，結點的左右指針域使用int型代替，用來表示左右子樹的根節點在數組中的下標。為此需要建立一個大小為結點上限個數的node型數組，所有動態生成的結點都直接使用數組中的結點，所有對指針的操作都改為對數組下標的訪問。于是，結點node的定義變為如下：

struct node{typename data;int lchild;int rchild;
}Node[maxn];

在這樣的定義下，結點的動態生成就可以轉變為如下的靜態指定：

int index=0;
int newNode(int v){Node[index].data=v;Node[index].lchild=-1;Node[index].rchild=-1;return index++;
}

下面給出二叉樹的查找、插入、建立的代碼。

void search(int root,int x,int newdata){if(root==-1){return;}if(Node[root].data==x){Node[root].data=newdata;}search(Node[root].lchild,x,newdata);search(Node[root].rchild,x,newdata);
}
void insert(int &root,int x){if(root==-1){root=newNode(x);return;}if(由二叉樹的性質x應該插在左子樹){insert(Node[root].lchild,x);}else{insert(Node[root].rchild,x);}
}
int Create(int data[],int n){int root=-1;for(int i=0;i<n;i++){insert(root,data[i]);}return root;
}

關于二叉樹的先序遍歷、中序遍歷、后序遍歷、層次遍歷也做相應的轉換：

void Layerorder(int root){queue<int> q;q.push(root);while(!q.empty()){int now=q.front();q.pop();printf("%d ",Node[now].data);if(Node[now].lchild!=-1){q.push(Node[now].lchild);}if(Node[now].rchild!=-1){q.push(Node[now].rchild);}}
}