二叉树各种遍历操作

小咪咪 2022-05-14 11:06 207阅读 0赞

**目录**

1 求二叉树深度

1.1 递归实现

1.2 非递归实现(队列)

1.3 非递归实现(栈)

2 求二叉树高度

3 二叉树先序遍历

3.1 递归版本

3.2 非递归版本

3.3 利用先序创建二叉树

4 二叉树中序遍历

4.1 递归版本

4.2 非递归版本

5 二叉树后序遍历

5.1 递归版本

5.2 非递归版本

6 二叉树层序遍历

7 二叉树深度优先遍历

8 二叉树广度优先遍历

9 求二叉树节点间最大距离

10 计算二叉树叶子节点数目

11 获取二叉树中根节点到指定节点的路径

12 获取两条路径的最后一个共同节点

13 获取两个结点的最近共同祖先

--------------------

本文总结关于二叉树的各种遍历算法

首先定义二叉树节点结构体

struct TreeNode {
        int val;
        struct TreeNode *left;
        struct TreeNode *right;
        TreeNode(int x) :
                val(x), left(NULL), right(NULL) {
        }
    };

# 1 求二叉树深度 #

## 1.1 递归实现 ##

*  如果一棵树只有一个结点，那么它的深度为1；
 *  如果根结点只有左子树没有右子树，那么树的深度是左子树的深度加1，加1是加上根节点这一层
 *  如果既有左子树又有右子树，那么树的深度应该是左、右子树中深度较大的值再加1

int TreeDepth(TreeNode* pRoot)
        {
         if(pRoot==NULL)
                return 0;
    
            int nleft = TreeDepth(pRoot->left);
            int nright = TreeDepth(pRoot->right);
    
            return (nleft>nright)?(nleft+1):(nright+1);
    
        }

## 1.2 非递归实现(队列) ##

*  每遍历一层，depth++;
 *  每一层，需使用一个变量`len`记录该层的结点个数，也就是队列的当前长度，然后依次在队列中访问该层的`len`个结点（将队列中`len`个元素出队列），并将下一层入队列。

int TreeDepth(TreeNode* pRoot)
        {
         queue<TreeNode*> q;
            if(!pRoot) return 0;
            q.push(pRoot);
            int level=0;
            while(!q.empty()){
                int len=q.size();
                level++;
                while(len--){
                    TreeNode* tem=q.front();
                    q.pop();
                    if(tem->left) q.push(tem->left);
                    if(tem->right) q.push(tem->right);
                }
            }
            return level;
        }

## 1.3 非递归实现(栈) ##

#include <iostream>
    #include <stack>
    using namespace std;
    typedef struct BinTree
    {
        int data;
        BinTree *lc;
        BinTree *rc;
    }BTNode,*BinTree;
    int max(int a,int b)
    {
        return (a>b)?a:b;
    }
    
    int BinTreeDepth(BinTree T)
    {
        stack<BinTree> s;
        BinTree p = T,r = NULL;
        int depth=0;
        while(p||!s.empty())
        {
            if(p)
            {    //从根节点向左边走
                s.push(p);
                int size = s.size();//获取栈的大小
                depth = max(depth,size);//替换最大值
                p = p->lc;
            }
            else
            {    //左边走不通向右走
                p = s.top();
                if(p->rc&&p->rc!=r)//如果右子树存在，且未被访问过
                {
                    p = p->rc;
                    s.push(p);
                    int size = s.size();//获取栈的大小
                    depth = max(depth,size);//替换最大值
                    p = p->lc;
                }else
                {
                    p=s.top();
                    s.pop();
                    cout<<p->data<<endl;
                    r=p;            //记录最近访问的节点
                    p=NULL;            //节点访问完之后，重置p指针,目的是为了防止再次将左孩子压栈
                }
            }
        }
        return depth;
    }

# 2 求二叉树高度 #

跟求深度一样，唯一的区别就是，对于根节点，深度为1，高度为0.

int Height(TreeNode *node)
    {
        if(node == NULL)
            return -1;
        else
            return 1 + Max(Height(node->left),Height(node->right));
    }

# 3 二叉树先序遍历 #

## 3.1 递归版本 ##

void preOrderTraverse(TreeNode *root) {  
            if (root != NULL) {  
                cout<<root->val<<endl;  
                preOrderTraverse(root->left);  
                preOrderTraverse(root->right);  
            }  
        }

## 3.2 非递归版本 ##

void PreOrder(TreeNode* pRoot)//前序遍历，非递归
    {
    	if (pRoot == NULL)
    		return;
    	stack<BiNode*> s;
    	TreeNode *p = pRoot;
    	while (p != NULL || !s.empty())
    	{
    		if (p != NULL)
    		{
    			cout << p->val << " ";
    			s.push_back(p);
    			p = p->left;
    		}
    		else
    		{
    			p = s.pop();
    			p = p->right;
    		}
    	}
    	cout << endl;
    }

## 3.3 利用先序创建二叉树 ##

//前序创建一颗二叉树
    void CreateBiTree(BiTree &T)
    {
    	char c;
    	cin >> c;
    	if ('#' == c)
    		T=NULL;
    	else
    	{
    		T = (BiNode* ) malloc(sizeof(BiNode));
    		T->val = c;
    		CreateBiTree(T->left);
    		CreateBiTree(T->right);
    	}
    }

# 4 二叉树中序遍历 #

## 4.1 递归版本 ##

void inOrderTraverse(TreeNode* root) {  
            if (root != NULL) {  
                inOrderTraverse(root->left);  
                cout<<root->val<<"  ";  
                inOrderTraverse(root->right);  
            }  
        }

## 4.2 非递归版本 ##

void inOrderTraverse(TreeNode* root) {  
            stack<TreeNode*> s;  
            TreeNode* pNode = root;  
            while (pNode != null || !stack.isEmpty()) {  
                if (pNode != null) {  
                    s.push(pNode);  
                    pNode = pNode->left;  
                } else { //pNode == null && !stack.isEmpty()  
                    TreeNode node = s.pop();  
                    cout<<node->val<<"  ";  
                    pNode = node->right;  
                }  
            }  
        }

# 5 二叉树后序遍历 #

## 5.1 递归版本 ##

public void postOrderTraverse(TreeNode root) {  
            if (root != null) {  
                postOrderTraverse(root.left);  
                postOrderTraverse(root.right);  
                System.out.print(root.val+"  ");  
            }  
        }

## 5.2 非递归版本 ##

void PostOrder(BiTree &T)//后序遍历（双栈法），非递归
    {
    	if (T == NULL)
    		return;
    	vector<BiNode*> S1,S2;
    	BiNode *p ;//当前指针所在结点
    	S1.push_back(T);
    	while (!S1.empty())
    	{
    		p = S1[S1.size() - 1];
    		S1.pop_back();
    		S2.push_back(p);
    		if (p->left)
    			S1.push_back(p->left);
    		if (p->right)
    			S1.push_back(p->right);
    	}
    	while (!S2.empty())
    	{
    		cout << S2[S2.size() - 1]->val << " ";
    		S2.pop_back();
    	}
    	cout << endl;
    }

# 6 二叉树层序遍历 #

void levelTraverse(TreeNode* root) {  
            if (root == NULL) {  
                return;  
            }  
            queue<TreeNode*> q;  
            queue.push_back(root);  
            while (!q.empty()) {  
                TreeNode* node = q.pop_front();  
                cout<<node->val<<"  ";  
                if (node->left != NULL) {  
                    q.push_back(node->left);  
                }  
                if (node->right != NULL) {  
                    q.push_back(node->right);  
                }  
            }  
        }

# 7 二叉树深度优先遍历 #

深度优先遍历就是先序遍历。

//深度优先遍历
    void depthFirstSearch(Tree root){
        stack<Node *> nodeStack; 
        nodeStack.push(root);
        Node *node;
        while(!nodeStack.empty()){
    	    node = nodeStack.top();
    		cout<<node->data;//遍历根结点
            nodeStack.pop();
            if(node->rchild){
                nodeStack.push(node->rchild);  //先将右子树压栈
            }
            if(node->lchild){
                nodeStack.push(node->lchild);  //再将左子树压栈
            }
        }
    }

# 8 二叉树广度优先遍历 #

广度优先其实就是层序遍历，利用队列很容易实现。

//广度优先遍历
    void breadthFirstSearch(Tree root){
        queue<Node *> nodeQueue;  //使用C++的STL标准模板库
        nodeQueue.push(root);
        Node *node;
        while(!nodeQueue.empty()){
            node = nodeQueue.front();
            nodeQueue.pop();
            cout<<node->data;//遍历根结点
            if(node->lchild){
                nodeQueue.push(node->lchild);  //先将左子树入队
            }
            if(node->rchild){
                nodeQueue.push(node->rchild);  //再将右子树入队
            }
        }
    }

# 9 求二叉树节点间最大距离 #

int GetMaxDistance(BiTree &T)//计算二叉树结点的最大距离，递归法
    {
    	if (T == NULL)
    		return 0;
    	int Distance = TreeDepth(T->left) + TreeDepth(T->right);
    	int l_Distance = GetMaxDistance(T->left);
    	int r_Distance = GetMaxDistance(T->right);
    	Distance = (Distance > r_Distance) ? Distance : r_Distance;
    	Distance = (Distance > l_Distance) ? Distance : l_Distance;
    	return Distance;
    }

# 10 计算二叉树叶子节点数目 #

int CountLeafNode(BiTree &T)//计算二叉树的叶子节点数目，递归法
    {
    	if (T == NULL)
    		return 0;
    	if (T->left == NULL&&T->right == NULL)
    		return 1;
    	return CountLeafNode(T->left)+CountLeafNode(T->right);
    }

# 11 获取二叉树中根节点到指定节点的路径 #

//获取二叉树中从根节点到指定节点的路径 
    void GetNodePath(BiNode* T, BiNode* Node, vector<BiNode*>& Path,int &found)
    {
    	if (T == NULL)
    		return;
    	Path.push_back(T);
    	if (T == Node)
    		found = 1;
    	if (!found)
    	{
    		GetNodePath(T->left, Node, Path, found);
    	}
    	if (!found)
    	{
    		GetNodePath(T->right, Node, Path, found);
    	}
    	if (!found)
    		Path.pop_back();
    	else
    		return;
    }

# 12 获取两条路径的最后一个共同节点 #

//获取两条路径的最后一个共同节点
    BiNode* GetLastCommonNode(const vector<BiNode*> Path1, const vector<BiNode*> Path2)
    {
    	vector<BiNode*>::const_iterator iter1 = Path1.begin();
    	vector<BiNode*>::const_iterator iter2 = Path2.begin();
    	BiNode *p = NULL;
    	while ( iter1 != Path1.end() && iter2 != Path2.end() && *iter1 != *iter2 )
    	{
    		if (*iter1 == *iter2)
    			p = *iter1;
    		iter1++;
    		iter2++;
    	}
    	return p;
    }

# 13 获取两个结点的最近共同祖先 #

//获取两个结点的最近共同祖先
    BiNode* GetLastCommonParent(BiNode* T, BiNode* Node1, BiNode* Node2)
    {
    	if (T == NULL || Node1 == NULL || Node2 == NULL)
    		return NULL;
    	vector<BiNode*> Path1, Path2;
    	int found1 = 0;
    	int found2 = 0;
    	GetNodePath(T, Node1, Path1,found1);
    	GetNodePath(T, Node2, Path2, found2);
    	return GetLastCommonNode(Path1,Path2);
    }