二叉树的静态实现

  1 /*
  2     二叉树的静态实现
  3 */
  4 struct node{
  5     typename data;//数据域 
  6     int lchild;//指向左孩子的指针域 
  7     int rchild;//指向右孩子的指针域 
  8 }Node[maxn];//结点数组,maxn为结点上限个数 
  9 
 10 //二叉树的建立,函数返回根节点root的下标 
 11 int create(/*typename data[],int n*/){//每个节点所对应的值(当然了,也可以在设置为全局变量),以及总的结点个数 
 12     int root = -1;
 13     for(int i=0; i<n; i++){
 14         insert(root,data[i]);//将节点数据插入二叉树中 
 15     }
 16     return root;//返回二叉树的根节点下标 
 17 } 
 18 
 19 //插入,root为根节点在数组中的下标 
 20 void insert(int &root,typename x){//记得加引用 
 21     if(root == -1){//空树,查找失败,即也是插入的位置 
 22         root = newNode(x);//给root赋以新的结点 
 23         return;
 24     } 
 25     if(/*由二叉树的性质,x应该插在左子树*/){
 26         insert(Node[root].lchild,x);//往左子树搜索(递归式) 
 27     }else{
 28         insert(Node[root].rchild,x);//往右子树搜索(递归式) 
 29     }
 30 } 
 31 
 32 int index = 0;//1还是0,由题目意思决定,从零开始还是从一开始
 33 int newNode(typename v){//分配一个Node数组中的结点给新的结点,index为其下标 
 34     Node[index].data = v;//数据域 
 35     Node[index].lchild = -1;//-1或者maxn为空 
 36     Node[index].rchild = -1;
 37     return index++;
 38 } 
 39 
 40 //查找和修改,root为根节点在数组中的下标 
 41 void search(int root, typename x, typename newdata){
 42     if(root == -1){
 43         return;//边界 
 44     } 
 45     if(Node[root].data == x){
 46         //输出或者修改
 47         Node[root].data = newdata;
 48     }
 49     //递归搜索 
 50     search(Node[root].lchild,x,newdata); 
 51     search(Node[root].rchild,x,newdata);
 52 } 
 53 
 54 //关于二叉树的遍历
 55 //前序遍历
 56 void preorder(int root){
 57     if(root == -1){
 58         return;
 59     }
 60     cout << Node[root].data;
 61     preorder(Node[root].lchild);
 62     preorder(Node[root].rchild);
 63 } 
 64 
 65 //中序遍历
 66 void inorder(int root){
 67     if(root == -1){
 68         return;
 69     }
 70     inorder(Node[root].lchild);
 71     cout << Node[root].data;
 72     inorder(Node[root].rchild);
 73 }
 74 
 75 //后序遍历
 76 void postorder(int root){
 77     if(root == -1){
 78         return;
 79     }
 80     postorder(Node[root].lchild);
 81     postorder(Node[root].rchild);
 82     cout << Node[root].data;
 83 } 
 84 
 85 //层序遍历
 86 void layerOrder(int root){
 87     queue<int> q;
 88     q.psuh(root);
 89     while(!q.empty()){
 90         int now = q.front();
 91         q.pop();
 92         cout << Node[now].data << " ";
 93         if(Node[now].lchild != -1){
 94             q.push(Node[now].lchild);
 95         }
 96         if(Node[now].rchild != -1){
 97             q.push(Node[now].rchild);
 98         }
 99     }
100 }