二叉树相关题目

1、二叉树采用链式存储 求先序遍历序列中第k个元素

 1 //求先序遍历序列中第k个节点的值
 2 int i = 1;//全局变量 记录现在是第几个数
 3 int PreOrder_k(TreeNode* root, int k)
 4 {
 5     if (!root) return 0;//当前节点为空 返回二叉树值不可能存在的一个值 作为标记
 6     if (i == k)//如果当前是第k个 则返回第k个的值
 7         return root->val;
 8     else//当前节点不是第k个
 9     {
10         i++;//下一个节点
11         int val_left = PreOrder_k(root->left,k);//往左子树中寻找
12         if (val_left != 0) return val_left;//若在左子树中找到了 则返回
13         else return PreOrder_k(root->right, k);//否则返回右子树找到的值
14     }
15 }

2、对于树中每个元素值为x的结点 删除以他为根的子树 并释放相应的空间

 1 //删除树中每个值为x的节点的子树
 2 //层次遍历 删除节点值为x的所有子树 再接着层次遍历
 3 void Delete_x_child(TreeNode* root,int x)
 4 {
 5     queue<TreeNode*> que;//队列
 6     TreeNode* p;
 7     que.push(root);//先将根节点放入队列
 8     while (!que.empty())//队列不空
 9     {
10         p = que.front();//取出队头结点
11         que.pop();//将队头结点从队列中移除
12         if (p->left)//若p存在左子树
13         {
14             if (p->left->val == x)//若左子树的值为x
15             {
16                 Delete_child(p->left);//递归删除左子树及其孩子
17                 p->left = NULL;
18             }
19             else
20                 que.push(p->left);
21         }
22
23         if (p->right)//若p存在右子树
24             if (p->right->val == x)
25             {
26                 Delete_child(p->right);
27                 p->right = NULL;
28             }
29             else
30                 que.push(p->right);
31     }
32 }
33 //递归删除p的左右节点 并删除p
34 void Delete_child(TreeNode* p)
35 {
36     if (p)
37     {
38         Delete_child(p->left);
39         Delete_child(p->right);
40         free(p);
41     }
42 }

3、查找值为x的节点 打印出值为x的结点所有的祖先

 1 //查找值为val1的节点和值为val2的节点 的最近公共祖先节点
 2 //后根序遍历 找到一个节点后 将当前的栈暂存到另一个栈 然后再寻找另一个节点 最后两个栈从栈底到栈顶找最后一个相同的节点即为最近公共子节点
 3 int Get_Nearest_Ancestor(TreeNode* root, int val1,int val2)
 4 {
 5     if (!root)return 0;
 6     stack<TreeNode*> s;
 7     stack<TreeNode*> temp;
 8     TreeNode* p = root, * last_visit = NULL;
 9     while (p || !s.empty())
10     {
11         if (p)
12         {
13             s.push(p);
14             p = p->left;
15         }
16         else
17         {
18             p = s.top();
19             if (p->right && p->right != last_visit)
20             {
21                 s.push(p->right);
22                 p = p->right->left;
23             }
24             else
25             {
26                 s.pop();
27                 if ((p->val == val1|| p->val == val2)&& temp.empty())//找到第一个节点
28                 {
29                     temp = s;//暂存当前栈 当前栈的内容为第一个节点的所有祖先
30                 }
31                 else if ((p->val == val1 || p->val == val2) && !temp.empty())//找到第二个节点
32                 {
33                     break;//跳出while
34                 }
35                 last_visit = p;
36                 p = NULL;
37             }
38         }
39     }
40     vector<TreeNode*> v_s;
41     vector<TreeNode*> v_t;
42     //将栈s 与栈temp中的元素pop出来存在vector中 结点高的在前 低的在后
43     while (!s.empty()) { v_s.insert(v_s.begin(), s.top()); s.pop(); }
44     while (!temp.empty()) { v_t.insert(v_t.begin(), temp.top()); temp.pop(); }
45     int i=0;
46     for (; i < v_s.size()&&i<v_t.size(); i++)//依次向前比较 找到第一个不相同的 即为最近祖先结点
47         if (v_s[i] != v_t[i])
48             break;
49     if (i == 0) return 0;//若第一个就不相同 则无公共祖先结点
50     return v_s[i-1]->val;
51 }

4、求二叉树的宽度

 1 //求二叉树的宽度
 2 //层次遍历 标记每层最后一个节点 记录每层的个数 选出结点数最多的一层
 3 int getBiTreeWidth(TreeNode* root)
 4 {
 5     if (!root) return 0;
 6     queue<TreeNode*> que;
 7     int count = 0;
 8     int max = 0;
 9     TreeNode* p, * last=root;
10     que.push(root);
11     while (!que.empty())
12     {
13         count++;
14         p = que.front();
15         que.pop();
16         if (p->left)que.push(p->left);
17         if (p->right)que.push(p->right);
18         if (p == last)
19         {
20             if (que.empty()) break;
21             last = que.back();
22             if (max < count) max = count;
23             count = 0;
24         }
25     }
26     return max;
27 }