二叉树的操作集二叉树的定义，遍历

/**
    二叉树的操作集：
    bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
    void Traversal(BinTree BT);//遍历BT树；
    BinTree NewNode(int data) //新建一个结点
    void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
                                              //数据域修改为给定数据域。
    void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
    BinTree CreateBinTree();//创建一棵二叉树；
*/

    1)递归遍历

1.  
   /**
2.  
   二叉树的操作集：
3.  
   bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
4.  
   void Traversal(BinTree BT);//遍历BT树；
5.  
   BinTree NewNode(int data) //新建一个结点
6.  
   void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
7.  
   //数据域修改为给定数据域。
8.  
   void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
9.  
   BinTree CreateBinTree();//创建一棵二叉树；
10.  
    1)递归遍历
11.  
    */
12.  
     
13.  
     
14.  
    #include <iostream>
15.  
    #include <queue>
16.  
    using namespace std;
17.  
     
18.  
    typedef int ElementType;
19.  
    typedef struct TNode* BinTree;
20.  
    struct TNode
21.  
    {
22.  
    ElementType data;
23.  
    BinTree left;
24.  
    BinTree right;
25.  
    };
26.  
    typedef BinTree Position;
27.  
     
28.  
    bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
29.  
    void PreTraver(BinTree BT);//前序遍历
30.  
    void MidTraver(BinTree BT); //中序遍历
31.  
    void BehTraver(BinTree BT); //后序遍历
32.  
    void LayTraver(BinTree BT); //层次遍历 layer:层次，阶层
33.  
     
34.  
    void PrePrintLeaves(BinTree BT);//打印叶子结点
35.  
    int GetHeight(BinTree BT); //获得树的高度
36.  
     
37.  
    BinTree NewNode(int data); //新建一个结点
38.  
    void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
39.  
    //数据域修改为给定数据域。
40.  
    void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
41.  
    BinTree CreateBinTree(int data);//创建一棵二叉树；
42.  
     
43.  
    int main()
44.  
    {
45.  
    cout << "Hello world!" << endl;
46.  
    return 0;
47.  
    }
48.  
     
49.  
    bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
50.  
    {
51.  
    return (BT==NULL);
52.  
    }
53.  
     
54.  
    void PreTraver(BinTree BT) //前序遍历
55.  
    {
56.  
    if(BT)
57.  
    {
58.  
    printf("%d ",BT->data);
59.  
    PreTraver(BT->left);
60.  
    PreTraver(BT->right);
61.  
    }
62.  
    }
63.  
     
64.  
    void MidTraver(BinTree BT) //中序遍历
65.  
    {
66.  
    if(BT)
67.  
    {
68.  
    MidTraver(BT->left);
69.  
    printf("%d ",BT->data);
70.  
    MidTraver(BT->right);
71.  
    }
72.  
    }
73.  
     
74.  
    void BehTraver(BinTree BT) //后序遍历
75.  
    {
76.  
    if(BT)
77.  
    {
78.  
    BehTraver(BT->left);
79.  
    BehTraver(BT->right);
80.  
    printf("%d ",BT->data);
81.  
    }
82.  
    }
83.  
     
84.  
    void LayTraver(BinTree BT) //层次遍历
85.  
    {
86.  
    if(!BT)
87.  
    return;
88.  
    queue<BinTree> q;
89.  
    q.push(BT);
90.  
    BinTree top;
91.  
    while(!q.empty())
92.  
    {
93.  
    top=q.front();
94.  
    q.pop();
95.  
    printf("%d ",top->data);
96.  
    if(top->left)
97.  
    q.push(top->left);
98.  
    if(top->right)
99.  
    q.push(top->right);
100.  
     }
101.  
     }
102.  
      
103.  
     void PrePrintLeaves(BinTree BT) //打印叶子结点
104.  
     {
105.  
     if(BT)
106.  
     {
107.  
     if(!BT->left&&!BT->right)
108.  
     printf("%d ",BT->data);
109.  
     PrePrintLeaves(BT->left);
110.  
     PrePrintLeaves(BT->right);
111.  
     }
112.  
      
113.  
     }
114.  
      
115.  
     int GetHeight(BinTree BT) //获得树的高度
116.  
     {
117.  
     if(BT)
118.  
     return max(GetHeight(BT->left),GetHeight(BT->right)) 1;
119.  
     else
120.  
     return 0; //空树高度为0；
121.  
     }
122.  
      
123.  
     BinTree NewNode(int data) //新建一个结点
124.  
     {
125.  
     BinTree BT = (BinTree) malloc(sizeof(TNode));
126.  
     BT->data=data;
127.  
     BT->left=BT->right=NULL;
128.  
     return BT;
129.  
     }
130.  
      
131.  
     void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的
132.  
     //数据域修改为给定数据域。
133.  
     {
134.  
     if(BT) //递归边界
135.  
     {
136.  
     if(BT->data==x)
137.  
     BT->data=newdata;
138.  
     Search(BT->left,x,newdata);
139.  
     Search(BT->right,x,newdata);
140.  
     }
141.  
     }
142.  
      
143.  
     void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
144.  
     {
145.  
     if(root == NULL)
146.  
     root=NewNode(x);
147.  
     if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性
148.  
     Insert(root->left,x);
149.  
     else
150.  
     Insert(root->right,x);
151.  
     }
152.  
      
153.  
     BinTree CreateBinTree(int data) //创建一棵二叉树；
154.  
     {
155.  
     BinTree BT=NULL;
156.  
     Insert(BT,data);
157.  
     return BT;
158.  
     }

2)非递归遍历

///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
void BehTraver(BinTree BT)  //后序遍历
{
    BinTree top=BT,sec;
    stack<BinTree> st;
    while(top||!st.empty())
    {
        while(top)
        {
            st.push(top);
            st.push(top);
            top=top->left;
        }
        top=st.top();
        st.pop();
        if(!st.empty())
            sec=st.top();
        else
        {
            printf("%d ",top->data);
            break; //树根节点遍历后，可直接跳出循环，即结束程序
        }
        if(top==sec)
            top=top->right;
        else
        {
            printf("%d ",top->data);
            top=NULL;
        }
    }
}

1.  
   /**
2.  
   二叉树的操作集：
3.  
   bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
4.  
   void Traversal(BinTree BT);//遍历BT树；
5.  
   BinTree NewNode(int data) //新建一个结点
6.  
   void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
7.  
   //数据域修改为给定数据域。
8.  
   void Insert(BinTree *&root,int x); //在二叉树中插入一个数据域为x的新节点；
9.  
   BinTree CreateBinTree();//创建一棵二叉树；
10.  
    2)非递归遍历
11.  
    */
12.  
     
13.  
    /**
14.  
    #include <iostream>
15.  
    #include <stack>
16.  
    #include <queue>
17.  
    using namespace std;
18.  
     
19.  
    typedef int ElementType;
20.  
    typedef struct TNode* BinTree;
21.  
    struct TNode
22.  
    {
23.  
    ElementType data;
24.  
    BinTree left;
25.  
    BinTree right;
26.  
    };
27.  
    typedef BinTree Position;
28.  
     
29.  
    bool IsEmpty(BinTree BT);//BT为空，则返回true，否则返回false；
30.  
    void PreTraver(BinTree BT);//前序遍历
31.  
    void MidTraver(BinTree BT); //中序遍历
32.  
    void BehTraver(BinTree BT); //后序遍历
33.  
    void LevTraver(BinTree BT); //层次遍历
34.  
     
35.  
    BinTree CreateBinTree();//创建一棵二叉树；
36.  
    void PrePrintLeaves(BinTree BT);//打印叶子结点
37.  
     
38.  
    BinTree NewNode(int data); //新建一个结点
39.  
    void Search(BinTree BT,int x,int newdata);//在二叉树中将所有数据域为给定数据域的结点，并把他们的
40.  
    //数据域修改为给定数据域。
41.  
    void Insert(BinTree &root,int x); //在二叉树中插入一个数据域为x的新节点；
42.  
    BinTree CreateBinTree(int data);//创建一棵二叉树；
43.  
     
44.  
    int main()
45.  
    {
46.  
    stack<int> st;
47.  
    for(int i=0;i<3; i)
48.  
    st.push(i);
49.  
    cout << st.top() << endl;
50.  
    int top=st.top();
51.  
    top=5;
52.  
    cout << st.top() << endl;
53.  
    st.top()=6;
54.  
    cout << st.top() << endl;
55.  
    cout << "Hello world!" << endl;
56.  
    return 0;
57.  
    }
58.  
     
59.  
    bool IsEmpty(BinTree BT)//BT为空，则返回true，否则返回false；
60.  
    {
61.  
    return (BT==NULL);
62.  
    }
63.  
     
64.  
    void PreTraver(BinTree BT) //前序遍历
65.  
    {
66.  
    BinTree top=BT;
67.  
    stack<BinTree> st;
68.  
    while(top||!st.empty())
69.  
    {
70.  
    while(top)
71.  
    {
72.  
    printf("%d ",top->data);
73.  
    st.push(top);
74.  
    top=top->left;
75.  
    }
76.  
    top=st.top();
77.  
    st.pop();
78.  
    top=top->right;
79.  
    }
80.  
    }
81.  
     
82.  
    void MidTraver(BinTree BT) //中序遍历
83.  
    {
84.  
    BinTree top=BT;
85.  
    stack<BinTree> st;
86.  
    while(top||!st.empty())
87.  
    {
88.  
    while(top)
89.  
    {
90.  
    st.push(top);
91.  
    top=top->left;
92.  
    }
93.  
    top=st.top();
94.  
    st.pop();
95.  
    printf("%d ",top->data);
96.  
    top=top->right;
97.  
    }
98.  
    }
99.  
     
100.  
     ///后序遍历：由于是最后访问根节点，所以根节点需要两次入队，因为先访问左节点，
101.  
     ///然后访问右节点，而访问右节点需要由根节点进入右节点，所以还是需要两次根节点，
102.  
     ///或许你会认为右根节点只需要入栈一次，当访问右节点的时候，不需要出栈，只需要取栈顶元素，
103.  
     ///但是你怎么知道什么时候开始已经访问了该节点的右节点，此时返回的根节点是由左孩子进入的还是由右孩子
104.  
     ///进入的我们是不知道的，所以还是需要根节点两次入栈。解释得有点小绕！
105.  
     void BehTraver(BinTree BT) //后序遍历
106.  
     {
107.  
     BinTree top=BT,sec;
108.  
     stack<BinTree> st;
109.  
     while(top||!st.empty())
110.  
     {
111.  
     while(top)
112.  
     {
113.  
     st.push(top);
114.  
     st.push(top);
115.  
     top=top->left;
116.  
     }
117.  
     top=st.top();
118.  
     st.pop();
119.  
     if(!st.empty())
120.  
     sec=st.top();
121.  
     else
122.  
     {
123.  
     printf("%d ",top->data);
124.  
     break; //树根节点遍历后，可直接跳出循环，即结束程序
125.  
     }
126.  
     if(top==sec)
127.  
     top=top->right;
128.  
     else
129.  
     {
130.  
     printf("%d ",top->data);
131.  
     top=NULL;
132.  
     }
133.  
     }
134.  
     }
135.  
      
136.  
     void LevTraver(BinTree BT) //层次遍历
137.  
     {
138.  
     if(!BT)
139.  
     return;
140.  
     queue<BinTree> q;
141.  
     q.push(BT);
142.  
     BinTree top;
143.  
     while(!q.empty())
144.  
     {
145.  
     top=q.front();
146.  
     q.pop();
147.  
     printf("%d ",top->data);
148.  
     if(top->left)
149.  
     q.push(top->left);
150.  
     if(top->right)
151.  
     q.push(top->right);
152.  
     }
153.  
     }
154.  
      
155.  
     void PrePrintLeaves(BinTree BT) //打印叶子结点
156.  
     {
157.  
     if(BT)
158.  
     {
159.  
     if(!BT->left&&!BT->right)
160.  
     printf("%d ",BT->data);
161.  
     PrePrintLeaves(BT->left);
162.  
     PrePrintLeaves(BT->right);
163.  
     }
164.  
      
165.  
     }
166.  
      
167.  
     int GetHeight(BinTree BT) //获得树的高度
168.  
     {
169.  
     if(BT)
170.  
     return max(GetHeight(BT->left),GetHeight(BT->right)) 1;
171.  
     else
172.  
     return 0; //空树高度为0；
173.  
     }
174.  
      
175.  
     BinTree NewNode(int data) //新建一个结点
176.  
     {
177.  
     BinTree BT = (BinTree) malloc(sizeof(TNode));
178.  
     BT->data=data;
179.  
     BT->left=BT->right=NULL;
180.  
     return BT;
181.  
     }
182.  
      
183.  
     void Search(BinTree BT,int x,int newdata)//在二叉树中将所有数据域为给定数据域的结点，并把他们的
184.  
     //数据域修改为给定数据域。
185.  
     {
186.  
     if(BT) //递归边界
187.  
     {
188.  
     if(BT->data==x)
189.  
     BT->data=newdata;
190.  
     Search(BT->left,x,newdata);
191.  
     Search(BT->right,x,newdata);
192.  
     }
193.  
     }
194.  
      
195.  
     void Insert(BinTree &root,int x) //在二叉树中插入一个数据域为x的新节点；且root需定义为引用
196.  
     {
197.  
     if(root == NULL)
198.  
     root=NewNode(x);
199.  
     if(check(root->left,x)) // 如果x满足二叉树左孩子分支的特性
200.  
     Insert(root->left,x);
201.  
     else
202.  
     Insert(root->right,x);
203.  
     }
204.  
      
205.  
     BinTree CreateBinTree(int data) //创建一棵二叉树；
206.  
     {
207.  
     BinTree BT=NULL;
208.  
     Insert(BT,data);
209.  
     return BT;
210.  
     }
211.  
      
212.  
     */

这篇好文章是转载于：学新通技术网