歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

二叉樹的鏡像

輸入一棵二叉樹的根結點,求該樹的深度,從根結點到葉結點依次經過的結點(含根,葉結點)形成樹的一條路徑,最長路徑的長度為樹的深度

#include <iostream>
using namespace std;

struct BinaryTreeNode
{
 int data;
 struct BinaryTreeNode *lchild;
 struct BinaryTreeNode *rchild;
};

typedef struct BinaryTreeNode BinTreeNode;

//先序構造二叉樹
BinTreeNode* preOrderCreateTree(BinTreeNode *head)
{
 int tmp;
 cin >> tmp;
 if (tmp == 0)
  head = NULL;
 else
 {
  head = new BinTreeNode;
  head->data = tmp;
  head->lchild = preOrderCreateTree(head->lchild);
  head->rchild = preOrderCreateTree(head->rchild);
 }
 
 return head;
}

//先序遍歷二叉樹
void preVisitTree(const BinTreeNode *head)
{
 if (head == NULL)
  return;
 
 cout << head->data;
 preVisitTree(head->lchild);
 preVisitTree(head->rchild);
}

void freeTree(BinTreeNode *head)
{
 if (head == NULL)
  return;
 
 freeTree(head->lchild);
 freeTree(head->rchild);
 delete head;
}

BinTreeNode* getTreeReverse(BinTreeNode *head)
{
 if (head == NULL)
  return NULL;
 if (head->lchild || head->rchild)
 {
  BinTreeNode *tmp;
  tmp = head->lchild;
  head->lchild = head->rchild;
  head->rchild = tmp;
 }
 head->lchild = getTreeReverse(head->lchild);
 head->rchild = getTreeReverse(head->rchild);
 return head;
}

int main()
{
 BinTreeNode *root = NULL;
 root = preOrderCreateTree(root);
 preVisitTree(root);
 cout << endl;
 root = getTreeReverse(root);
 preVisitTree(root);
 cout << endl;  
 freeTree(root); 
 return 0;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm

Copyright © Linux教程網 All Rights Reserved